Sheaf data model

• US 6,917,943 B2
• Filed: 05/11/2001
• Issued: 07/12/2005
• Est. Priority Date: 05/12/2000
• Status: Expired due to Fees

• Current Assignee: Limit Point Systems Incorporated
• Original Assignee: Limit Point Systems Incorporated
• Inventors: Butler, David M.
• Primary Examiner(s): Wassum, Luke S
• Assistant Examiner(s): PHAM, KHANH B
• Application Number:
  US09/852,781
• Publication Number:
  US 20020095561A1
• Time in Patent Office: 1,523 Days
• Field of Search: 707/100, 707/101, 707/102, 707/103.R, 707/103.Z, 703/2, 706/55
• US Class Current: 1/1
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A data model including a first table to represent an entity type with a column in the table for a respective attribute of the entity type, and having rows entered with attribute data. The data model also includes a row graph which represents an ordering relationship between the rows of the first table, and a column graph which represents an ordering relationship between columns of the first table. Further, the column graph is a row graph from a second table.

Claims

1. A computer-implemented method of representing data on a computer as a collection of finite distributive lattices for facilitating information retrieval in response to a query, comprising the steps of:

selecting one or more entity types within an application, each entity type being a single entity type;

constructing a distinct table to represent each entity type selected in said selecting step, such that there is a one-to-one correspondence between respective tables and entity types;

for each table executing steps of

constructing a column in the table for a respective attribute of the entity type, such that there is a one-to-one correspondence between columns and attributes of the entity type;

constructing a row in the table for each entity of the entity type, such that there is a one-to-one correspondence between rows and entities;

entering attribute data into rows of the table;

specifying a row graph which represents an externally specified ordering relationship between the rows of the table; and

defining a finite distributive lattice (FDL) from the row graph to have a member for each row and each distinct combination of the rows of the table,

wherein two combinations of rows are distinct if they do not represent a same ordering relationship.

2. The method according to claim 1, wherein the table includes one row for each primary entity of the entity type.

3. The method according to claim 1, wherein a first entity is included in a second entity if and only if there is a path in the graph from a node corresponding to the first entity to a node corresponding to the second entity.

4. The method according to claim 1, wherein the ordering relationship of the rows of the table comprises a partially ordered relationship.

5. The method according to claim 1, further comprising the step of:

querying the row graph to determine distinct combinations of the rows of the table,

wherein two different combinations of members are distinct if they do not represent a same ordering relationship.

6. The method according to claim 1, further comprising the step of:

executing a command indicative of an operation a₁≦

a₂ to determine if and only if there is a path in the graph from a₁ to a₂, where a₁ and a₂ are nodes in the row graph.

7. The method according to claim 1, further comprising the step of:

executing a command indicative of an operation DOWN(a) in which a resultant table and graph is returned including all rows of the table and nodes and links of the row graph which are less than or equal to “

a”

, where “

a”

is a specified node in the row graph.

8. The method according to claim 1, wherein the attribute data comprises at least one of simulation data, spatial data, object-orientated data, and relational data.

9. The method according to claim 1, further comprising the step of:

executing a command indicative of an operation JOIN(1₁, 1₂, . . . 1_n) to determine a smallest member of the FDL which is greater than or equal to the inputs 1₁, 1₂, . . . 1_n.

10. The method according to claim 1, further comprising the step of:

executing a command indicative of an operation MEET(1₁, 1₂, . . . 1_n) to determine a largest member of the FDL which is less than or equal to the inputs 1₁, 1₂, . . . 1_n.

11. The method according to claim 1, wherein any node in the row graph below and connected to another node is included in the other node.

12. The method according to claim 1, further comprising the step of:

executing a command indicative of the operation n-ary Cartesian product L1×

L2×

. . . ×

Ln, to generate a resultant FDL with columns equal to the disjoint union of the columns of L1, L2, . . . Ln, where L1, L2, . . . Ln represents any collection of FDLs,

wherein the row-graph is any partial order.

13. The method according to claim 1, further comprising the step of:

executing a command indicative of the operation of SELECTION(L, c) to generate a resultant FDL comprising the table rows that satisfy c, the row graph that satisfy c, and all columns of L, where L is a FDL and c is a condition on the rows of L.

14. The method according to claim 1, further comprising the step of:

executing a command indicative of the operation PROJECTION(L, c) to generate a resultant FDL comprising all columns of L that satisfy c, and all table rows and the entire graph of L, where L is a FDL and c is a condition on the columns of L.

15. The method according to claim 1, further comprising the step of:

executing a command indicative of the operation UNION(L1, L2) to generate a resultant FDL containing the rows of L1 and the rows of L2, a row graph which is the reflexive, transitive reduction of the union of the row graphs of L1 and L2, and the columns of L1, where L1 and L2 are FDLs with the same columns.

16. The method according to claim 1, further comprising the step of:

executing a command indicative of the operation INTERSECTION(L1, L2) to generate a resultant FDL containing those rows of L1 which are the same as rows in L2, a row graph which is the reflexive, transitive reduction of the intersection of the row graphs of L1 and L2, and the columns of L1, where L1 and L2 are FDLs with the same columns.

17. The method according to claim 1, further comprising the step of:

executing a command indicative of RENAME(L, new₁₃ name) to change the name of L to new₁₃ name, where L is a FDL and new₁₃ name is a name.

18. The method according to claim 1, further comprising the step of:

executing a command indicative of the operator CREATE_JIM(L) to create a new row in the table of L and a new node in the row graph of L, where L is a FDL.

19. The method according to claim 1, further comprising the step of:

executing a command indicative of DELETE_JIM(L, JIM_ID) to remove a row from the table of L and to remove the corresponding node and any connecting links in the row graph of L, where L is a FDL and JIM_ID identifies a row in L.

20. The method according to claim 1, further comprising the step of:

executing a command indicative of the operator CREATE_LINK(L, LESSER_ID, GREATER_ID) to create a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a FDL and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

21. The method according to claim 1, further comprising the step of:

executing a command indicative of the operator DELETE_LINK(L, LESSER_ID, GREATER_ID) to remove a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a FDL and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

22. A computer implemented data model for facilitating information retrieval via a query, comprising:

a first table and other tables respectively configured to represent a single entity type from a group of entity types such that there is a one-to-one correspondence between respective tables and entity types, said first table having

a column for a respective attribute of the entity type such that there is a one-to-one correspondence between columns and respective attributes of the entity type, and

a different row for each entity of the entity types such that there is a one-to-one correspondence between rows and respective entities, wherein each row is externally specified and includes attribute data for an entity that corresponds with the row;

a row graph which represents an ordering relationship between the rows of the first table; and

a finite distributive lattice (FDL) defined from the first table to have distinct combinations of the rows of the first table, wherein two different combinations of members are distinct if they do not represent a same ordering relationship.

23. The data model according to claim 22, wherein the first table includes one row for each primary entity of the entity type.

24. The data model according to claim 22, wherein a first entity is included in a second entity if and only if there is a path in the graph from a node corresponding to the first entity to a node corresponding to the second entity.

25. The data model according to claim 22, wherein the ordering relationship of the rows of the first table comprises a partially ordered relationship.

26. The data model according to claim 22, wherein distinct combination of the rows of the first table are determined by querying the row graph, and

wherein two different combinations of members are distinct if they do not represent a same ordering relationship.

27. The data model according to claim 22, further comprising:

a command indicative of an operation a₁≦

a₂ to determine if and only if there is a path in the graph from a₁ to a₂, where a₁ and a₂ are nodes in the row graph.

28. The data model according to claim 22, further comprising:

a command indicative of an operation DOWN(a) in which a resultant table and graph is returned including all rows of the first table and nodes and links of the row graph which are less than or equal to “

a”

, where “

a”

is a specified node in the row graph.

29. The data model according to claim 22, wherein the attribute data comprises at least one of simulation data, spatial data, object-orientated data, and relational data.

30. The data model according to claim 22, further comprising:

a command indicative of an operation JOIN(1₁, 1₂, . . . 1_n) to determine a smallest member of the FDL which is greater than or equal to the inputs 1₁, 1₂, . . . 1_n.

31. The data model according to claim 22, further comprising:

a command indicative of an operation MEET(1₁, 1₂, . . . 1_n) to determine a largest member of the FDL which is less than or equal to the inputs 1₁, 1₂, . . . 1_n.

32. The data model according to claim 22, wherein any node in the row graph below and connected to another node is included in the other node.

33. The data model according to claim 22, further comprising:

a command indicative of the operation n-ary Cartesian product L1×

L2×

. . . ×

Ln, to generate a resultant FDL with columns equal to the disjoint union of the columns of L1, L2, . . . Ln, where L1, L2, Ln represents any collection of FDLs,

wherein the row-graph is any partial order.

34. The data model according to claim 22, further comprising:

a command indicative of the operation of SELECTION(L, c) to generate a resultant FDL comprising the table rows of L that satisfy c, the row graph that satisfy c, and all columns of L, where L is a FDL and c is a condition on the rows of L.

35. The data model according to claim 22, further comprising:

a command indicative of the operation PROJECTION(L, c) to generate a resultant FDL comprising all columns of L that satisfy c, and all table rows and the entire graph of L, where L is a FDL and c is a condition on the columns of L.

36. The data model according to claim 22, further comprising:

a command indicative of the operation UNION(L1, L2) to generate a resultant FDL containing the rows of L1 and the rows of L2, a row graph which is the reflexive, transitive reduction of the union of the row graphs if L1 and L2, and columns of L1, where L1 and L2 are FDLs with the same columns.

37. The data model according to claim 22, further comprising:

a command indicative of the operation INTERSECTION(L1, L2) to generate a resultant FDL containing those rows of L1 which are the same as rows in L2, a row graph which is the reflexive, transitive reduction of the intersection of the row graphs of L1 and L2, and the columns of L1, where L1 and L2 are FDLs with the same columns.

38. The data model according to claim 22, further comprising:

a command indicative of RENAME(L, new_name) to change the name of L to new_name, where L is a FDL and new_name is a name.

39. The data model according to claim 22, further comprising:

a command indicative of the operator CREATE_JIM(L) to create a new row in the table of L and a new node in the row graph of L, where L is a FDL.

40. The data model according to claim 22, further comprising:

a command indicative of DELETE_JIM(L, JIM_ID) to remove a row from the table of L and to remove the corresponding node and any connecting links in the row graph of L, where L is a FDL and JIM_ID identifies a row in L.

41. The data model according to claim 22, further comprising:

a command indicative of the operator CREATE_LINK(L, LESSER_ID, GREATER_ID) to create a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a FDL and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

42. The data model according to claim 22, further comprising:

a command indicative of the operator DELETE_LINK(L, LESSER_ID, GREATER_ID) to remove a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a FDL and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

43. A computer-implemented method of representing data on a computer as a collection of finite sheaves for facilitating information retrieval in response to a query, comprising the steps of:

selecting one or more entity types within an application, each entity type being a single entity type;

constructing a distinct table to represent an entity type selected in said selecting step, such that there is a one-to-one correspondence between respective tables and entity types;

for each table executing steps of;

selecting another table, hereafter referred to as the schema table of the current table;

constructing a column in the current table for each row of the respective schema table, such that there is a one-to-one correspondence between columns in the current table and rows in the schema table;

interpreting each column of the table as an attribute of the associated entity type;

interpreting a row graph of the schema table as a column graph of the current table, said column graph representing an ordering relationship between the columns of the current table;

constructing a row in the current table for each entity of the associated entity type, such that there is a one-to-one correspondence between rows and entities;

entering attribute data into rows of the current table;

specifying a row graph which represents an externally specified ordering relationship between the rows of the current table;

defining a finite distributive lattice (FDL) from the row graph to have a member for each row and each distinct combination of the rows of the current table, wherein two combinations of rows are distinct if they do not represent a same ordering relationship; and

defining a finite sheaf from the table, row graph and column graph.

44. The method according to claim 43, wherein a first entity is included in a second entity if and only if there is a path in the graph from a node corresponding to the first entity to a node corresponding to the second entity.

45. The method according to claim 43, wherein the ordering relationship of the rows of the first table comprises a partially ordered relationship.

46. The method according to claim 43, further comprising the step of:

querying the row graph to determine distinct combinations of the rows of the first table,

wherein two different combinations of members are distinct if they do not represent a same ordering relationship.

47. The method according to claim 43, further comprising the step of:

executing a command indicative of an operation a1<

a2 to determine if and only if there is a path in the graph from a1 to a2, where a1 and a2 are nodes in the row graph.

48. The method according to claim 43, further comprising the step of:

executing a command indicative of an operation DOWN(a) in which a resultant table and graph is returned including all rows of the first table and nodes and links of the row graph which are less than or equal to “

a”

, where “

a”

is a specified node in the row graph.

49. The method according to claim 43, wherein the attribute data comprises at least one of simulation data, spatial data, object-orientated data, and relational data.

50. The method according to claim 43, further comprising the step of:

executing a command indicative of an operation JOIN(11, 12, . . . 1n) to determine a smallest member of the sheaf which is greater than or equal to the inputs 11, 12, . . . 1n.

51. The method according to claim 43, further comprising the step of

executing a command indicative of an operation MEET(11, 12, . . . 1n) to determine a largest member of the sheaf which is less than or equal to the inputs 11, 12, . . . 1n.

52. The method according to claim 43, further comprising the step of:

executing a command indicative of an operation EXP(L) to generate a resultant sheaf with a column graph corresponding to the row graph of L, where L is a sheaf.

53. The method according to claim 43, further comprising the step of:

executing a command indicative of an operation LOG(L) to determine the schema sheaf of L, where L is a sheaf.

54. The method according to claim 43, further comprising the step of:

executing a command indicative of an operation RESTRICT L TO S to determine a projection of the sheaf onto columns in the down set of S, where S is a member of the schema of L and L is a sheaf.

55. The method according to claim 43, wherein any node in the row graph below and connected to another node is included in the other node.

56. The method according to claim 43, further comprising the step of:

executing a command indicative of the operation n-ary Cartesian product L1×

L2×

. . . ×

Ln, to generate a resultant sheaf with a schema sheaf equal to the union of the schema of L1, L2, . . . Ln, where L1, L2, . . . Ln represents any collection of sheaves.

57. The method according to claim 43, further comprising the step of:

executing a command indicative of the operation of SELECTION(L, c) to generate a resultant sheaf comprising the table rows that satisfy c, the row graph that satisfy c, and the entire column graph and all columns of L, where L is a sheaf and c is a condition on the rows of L.

58. The method according to claim 43, further comprising the step of:

executing a command indicative of the operation PROJECTION(L, c) to generate a resultant sheaf comprising the column graph and columns of L that satisfy c, and all table rows, and the entire row graph of L, where L is a sheaf and c is a condition on the columns of L.

59. The method according to claim 43, further comprising the step of:

executing a command indicative of the operation UNION(L1, L2) to generate a resultant sheaf containing the rows of L1 and the rows of L2, a row graph which is the reflexive, transitive reduction of the union of the row graphs of L2 and L2, and the column graph of L1, where L1 and L2 are sheaves with the same column graph.

60. The method according to claim 43, further comprising the step of:

executing a command indicative of the operation INTERSECTION(L1, L2) to generate a resultant sheaf containing those rows of L1 which are the same as rows in L2, a row graph which is the reflexive, transitive reduction of the intersection of the row graphs of L1 and L2, and the column graph of L1, where L1 and L2 are sheaves with the same column graph.

61. The method according to claim 43, further comprising the step of:

executing a command indicative of RENAME(L, new_name) to change the name of L to new_name, where L is a sheaf and new_name is a name.

62. The method according to claim 43, further comprising the step of:

executing a command indicative of the operator CREATE_JIM(L) to create a new row in the table of L and a new node in the row graph of L, where L is a sheaf.

63. The method according to claim 43, further comprising the step of:

executing a command indicative of DELETE_JIM(L, JIM_ID) to remove a row from the table of L and to remove the corresponding node and any connecting links in the row graph of L, where L is a sheaf and JIM_ID identifies a row in L.

64. The method according to claim 43, further comprising the step of:

executing a command indicative of the operator CREATE_LINK(L, LESSER_ID, GREATER_ID) to create a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a sheaf and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

65. The method according to claim 43, further comprising the step of:

executing a command indicative of the operator DELETE_LINK(L, LESSER_ID, GREATER_ID) to remove a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a sheaf and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

66. A data model encoded on a computer-readable medium as a collection of finite sheaves for facilitating information retrieval in response to a query, comprising:

a first table and other tables respectively configured to represent a single entity type from a group of entity types, such that there is a one-to-one correspondence between respective tables and entity types, said first table having;

an association with a second table, hereafter referred to as the schema table of the first table;

a column for each row of the respective schema table, such that there is a one-to-one correspondence between columns in the first table and rows in the schema table;

each said column corresponding to an attribute of the entity type associated with the first table;

a column graph defined to be a row graph of the respective schema table, said column graph representing an ordering relationship between the columns of the current table;

a row for each entity of the associated entity type, such that there is a one-to-one correspondence between rows and entities;

attribute data included in the rows;

a row graph which represents an externally specified ordering relationship between the rows of the first table;

a finite distributive lattice (FDL) defined from the row graph to have a member for each row and each distinct combination of the rows of the first table, wherein two combinations of rows are distinct if they do not represent a same ordering relationship; and

a finite sheaf corresponding to the table, row graph and column graph.

67. The data model according to claim 66, wherein a first entity is included in a second entity if and only if there is a path in the graph from a node corresponding to the first entity to a node corresponding to the second entity.

68. The data model according to claim 66, wherein the ordering relationship of the rows of the first table comprises a partially ordered relationship.

69. The data model according to claim 66, wherein distinct combination of the rows of the first table are determined by querying the row graph, and

wherein two different combinations of members are distinct if they do not represent a same ordering relationship.

70. The data model according to claim 66, further comprising:

a command indicative of an operation a1<

a2 to determine if and only if there is a path in the graph from a1 to a2, where a1 and a2 are nodes in the row graph.

71. The data model according to claim 66, further comprising:

a command indicative of an operation DOWN(a) in which a resultant table and graph is returned including all rows of the first table and nodes and links of the row graph which are less than or equal to “

a”

, where “

a”

is a specified node in the row graph.

72. The data model according to claim 66, wherein the attribute data comprises at least one of simulation data, spatial data, object-orientated data, and relational data.

73. The data model according to claim 66, further comprising:

a command indicative of an operation JOIN(l1, l2, . . . ln) to determine a smallest member of the sheaf which is greater than or equal to the inputs l1, l2, . . . ln.

74. The data model according to claim 66, further comprising:

a command indicative of an operation MEET(l1, l2, . . . ln) to determine a largest member of the sheaf which is less than or equal to the inputs l1, l2, . . . ln.

75. The data model according to claim 66, further comprising:

a command indicative of an operation EXP(L) to generate a resultant sheaf with a column graph corresponding to the row graph of L, where L is a sheaf.

76. The data model according to claim 66, further comprising:

a command indicative of an operation LOG(L) to determine the schema sheaf of L, where L is a sheaf.

77. The data model according to claim 66, further comprising:

a command indicative of an operation RESTRICT L TO S to determine a projection of L onto columns in the down set of S, where S is a member of the schema of L and L is a sheaf.

78. The data model according to claim 66, wherein any node in the row graph below and connected to another node is included in the other node.

79. The data model according to claim 66, further comprising:

a command indicative of the operation n-ary Cartesian product L1×

L2×

. . . ×

Ln, to generate a resultant sheaf with a schema sheaf equal to the union of the schema of L1, L2, . . . Ln, where L1, L2, . . . Ln represents any collection of sheaves.

80. The data model according to claim 66, further comprising:

a command indicative of the operation of SELECTION(L, c) to generate a resultant sheaf comprising the table rows that satisfy c, the row graph that satisfy c, and the entire column graph and all columns of L, where L is a sheaf and c is a condition on the rows of L.

81. The data model according to claim 66, further comprising:

a command indicative of the operation PROJECTION(L, c) to generate a resultant sheaf comprising the column graph and columns of L that satisfy c, and all table rows, and the entire row graph of L, where L is a sheaf and c is a condition on the columns of L.

82. The data model according to claim 66, further comprising:

a command indicative of the operation UNION(L1, L2) to generate a resultant sheaf containing the rows of L1 and the rows of L2, a row graph which is the reflexive, transitive reduction of the union of the row graphs of L1 and L2, where L1 and L2 are sheaves with the same column graph.

83. The data model according to claim 66, further comprising:

a command indicative of the operation INTERSECTION(L1, L2) to generate a resultant sheaf containing those rows of L1 which are the same as rows in L2, a row graph which is the reflexive, transitive reduction of the intersection of the row graphs of L1 and L2, and the column graph of L1, where L1 and L2 are sheaves with the same column graph.

84. The data model according to claim 66, further comprising:

a command indicative of RENAME(L, new_name) to change the name of L to new_name, where L is a sheaf and new_name is a name.

85. The data model according to claim 66, further comprising:

a command indicative of the operator CREATE_JIM(L) to create a new row in the table of L and a new node in the row graph of L, where L is a sheaf.

86. The data model according to claim 66, further comprising:

a command indicative of DELETE_JIM(L, JIM_ID) to remove a row from the table of L and to remove the corresponding node and any connecting links in the row graph of L, where L is a sheaf and JIM_ID identifies a row in L.

87. The data model according to claim 66, further comprising:

a command indicative of the operator CREATE_LINK(L, LESSER_ID, GREATER_ID) to create a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a sheaf and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.

88. The data model according to claim 66, further comprising:

a command indicative of the operator DELETE_LINK(L, LESSER_ID, GREATER_ID) to remove a link between the node corresponding to LESSER_ID and the node corresponding to GREATER_ID in the row graph of L, where L is a sheaf and LESSER_ID and GREATER_ID identify the lesser and greater rows, respectively, of the ordering relationship represented by the link.