Disambiguation of tabular date

• US 8,423,579 B2
• Filed: 10/29/2008
• Issued: 04/16/2013
• Est. Priority Date: 10/29/2008
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Melamed, Boris, Steinhart, Shlomo
• Primary Examiner(s): LE, THU NGUYET T
• Application Number:
  US12/260,707
• Publication Number:
  US 20100106750A1
• Time in Patent Office: 1,630 Days
• Field of Search: 707/793, 707/797, 707/791, 707803-804, 707/809, 707759-760
• US Class Current: 707/797
• CPC Class Codes: G06F 16/288 Entity relationship models

Abstract

Creating data tables by identifying paths in a tree of data entities and relationships, the tree including data entities and relationships between the entities, where each of the paths originates from the same data entity, includes a terminal data entity that is at the to-many end of a one-to-many or many-to-many relationship with another data entity along the path, and includes no other of the data entities that lie along any path descending from the terminal data entity and that is at the to-many end of a one-to-many or many-to-many relationship with another of the data entities that lie along the path descending from the terminal data entity, and creating on a computer-readable medium a separate table for each of the paths, where each of the tables includes a column per each of the data entities of the path for which the table was created.

Claims

1. A computer implemented method for creating tables of related data, the method comprising:

identifying in a single tree representing all of a plurality of data entities and all cardinal relationships between said data entities, and all of a plurality of core paths, wherein each of said core paths includes a plurality of said data entities and any of said cardinal relationships between any of said data entities of the related data, wherein

each of said core paths, originates from a common root data entity, wherein the common root data entity is the same one of said data entities, wherein

each of said core paths includes a terminal data entity, the terminal data entity being one of said data entities that terminates said core path, wherein said terminal data entity is at a to-many end of a many-to-many relationship with another of said data entities along said core path, and wherein

each of said core paths includes no other of said data entities that lie along any non-core path descending from said terminal data entities, and

creating on a computer-readable medium a separate table for each of said core paths, wherein each of said tables includes a column for each of said dam entities of said core path for which said table was created such that all of the data entities in all of the core paths are unambiguously presented in the tables.

2. The method according to claim 1 and further comprising:

including in any of said tables a column for other of said data entities that lie along any non-core path descending from said terminal data entity of said core path for which said table was created, such that the terminal data entity is not a leaf.

3. The method according to claim 1 and further comprising:

including in any of said tables a column for other of said data entities that lie along any singularity path descending from any of said data entities other than the terminal data entity in said core path for which said table was created, wherein said descending singularity path lies at least partially along paths other than said core path for which said table was created, and wherein said data entities that lie along said descending singularity path have one-to-one cardinality with any of said data entities along the entirety of said descending singularity path.

4. The method according to claim 1 and further comprising:

including any of said data entities that does not lie along any of said identified core paths in a plurality of said tables.

5. The method according to claim 1 and further comprising:

including any of said data entities that does not lie along any of said identified core paths in only one of said tables.

6. A tabular data disambiguation system comprising:

a computer processing device;

a core path identifier configured to identify any core path within a single tree of a plurality of data entities as, wherein

the core path originates from a common root data entity,

including a terminal data entity terminating said core path, wherein said terminal data entity is at a to-many end of a many-to-many relationship with any of said data entities along said core path, and wherein

the core path includes no other of said data entities that lie along any non-core path descending from said terminal data entity; and

a table creator configured to create on as computer-readable medium a separate table for of said core paths identified by said core path identifier, wherein each of said tables includes a column for each of said data entities of said core path for which said table was created such that all of the data entities in all of the core paths are unambiguously presented in the tables.

7. The system according to claim 6 and further comprising a tree constructor configured to construct a tree including all of the core paths in a path set, wherein all of said core paths in said path set originate from said common root data entity.

8. The system according to claim 6 wherein any of said core paths defines a traversal order from a first one of said data entities in said core path to a last one of data entity in said path.

9. The system according to claim 6 wherein each of said data entities, but the last data entity, in any of said core paths has a cardinal relationship with the data entity that immediately follows it.

10. The system of claim 6, further comprising including in any of said tables a column for other of said data entities that lie along any non-core path descending from said terminal data entity of said core path for which said table was created, such that the terminal data entity is not a leaf.

11. The system of claim 6, further comprising including in any of said tables a column for other of said data entities that lie along any singularity path descending from any of said data entities other than the terminal data entity in said core path for which said table was created, wherein said descending, singularity path lies at least partially along paths other than said core path for which said table was created, and wherein said data entities that lie along said descending singularity path have one-to-one cardinality with any of said data entities along the entirety of said descending singularity path.

12. A computer-implemented program embodied on a non-transitory computer-readable medium, the computer program comprising:

a code segment operative to identify, in a single tree representing a plurality of data entities and cardinal relationships between said data entities, a plurality of core paths, wherein each of said core paths includes a plurality of said data entities and any of said cardinal relationships between any of said data entities, wherein

each of said core paths originates from a common root data entity, wherein the common root data entity is the same one of said data entities, and wherein

each of said core paths includes a terminal data entity, the terminal data entity being one of said data entities that terminates said core path, wherein said terminal data entity is at a to-many end of a many-to-many relationship with another of said data entities along, said core path, and wherein

each of said core paths includes no other of said data entities that lie along any non-core path descending from said terminal data entity; and

a code segment operative to create on the non-transitory computer-readable medium a separate table for each of said core paths, wherein each of said tables includes a column for each of said data entities of said core path far which said table was created.

13. The computer program of claim 12, further comprising including in any of said tables a column for other of said data entities that lie along any non-core path descending from said terminal data entity of said core path for which said table was created, such that the terminal data entity is not a leaf.

14. The computer program of claim 12, further comprising including in any of said tables a column for other of said data entities that lie along any singularity path descending from any of said data entities other than the terminal data entity in said core path for which said table was created, wherein said descending singularity path lies at least partially along paths other than said core path for which said table was created, and wherein said data entities that lie along said descending singularity path have one-to-one cardinality with any of said data entities along the entirety of said descending singularity path.