DISAMBIGUATION OF TABULAR DATA

• US 20100106750A1
• Filed: 10/29/2008
• Published: 04/29/2010
• Est. Priority Date: 10/29/2008
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Steinhart, Shlomo, Melamed, Boris
• Granted Patent: US 8,423,579 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• 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 method for creating tables of data, the method comprising:

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

originates from the same one of said data entities,

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

includes no other of said data entities that lie along any path descending from said terminal data entity and that is at the to-many end of either of a one-to-many relationship and a many-to-many relationship with another of said data entities that lie along said path descending from said terminal data entity; and

creating on a computer-readable medium a separate table for each of said paths, wherein each of said tables includes a column per each of said data entities of said path for which said table was created.

2. A method according to claim 1 and further comprising including in any of said tables a column for any of said data entities that lie along any path descending from said terminal data entity of said path for which said table was created.

3. A method according to claim 1 and further comprising including in any of said tables a column for any of said data entities that lie along any path descending from any of said data entities in said path for which said table was created, wherein said descending path lies at least partially along paths other than said path for which said table was created, and wherein said data entities that lie along said descending path have one-to-one cardinality with any of said data entities along the entirety of said descending path.

4. A method according to claim 1 and further comprising including any of said data entities that does not lie along any of said identified paths in a plurality of said tables.

5. A method according to claim 1 and further comprising including any of said data entities that does not lie along any of said identified paths in only one of said tables.

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

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

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

6. A tabular data disambiguation system comprising:

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

originating from a common root data entity,

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

including no other of said data entities that lie along any path descending from said terminal data entity and that is at the to-many end of either of a one-to-many relationship and a many-to-many relationship with any of said data entities that lie along said path descending from said terminal data entity; and

a table creator configured to create on a computer-readable medium a separate table for of said paths identified by said core path identifier, wherein each of said tables includes a column per each of said data entities of said path for which said table was created.

10. A computer-implemented program embodied on a computer-readable medium, the computer program comprising:

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

originates from the same one of said data entities,

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

includes no other of said data entities that lie along any path descending from said terminal data entity and that is at the to-many end of either of a one-to-many relationship and a many-to-many relationship with another of said data entities that lie along said path descending from said terminal data entity; and

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