Sheaf data model

• US 20020095561A1
• Filed: 05/11/2001
• Published: 07/18/2002
• Est. Priority Date: 05/12/2000
• Status: Active Grant

• Current Assignee: Limit Point Systems Incorporated
• Original Assignee: Limit Point Systems Incorporated
• Inventors: Butler, David M.
• Granted Patent: US 6,917,943 B2
• Time in Patent Office: Days
• US Class Current: 712/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 method of representing data on a computer, comprising the steps of:

constructing a first table to represent an entity type with a column in the table for a respective attribute of the entity type;

entering attribute data into rows of the first table;

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

generating a finite distributive lattice (FDL) 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.

2. The method according to claim 1, wherein the first 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 first 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 first 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 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.

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 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 to name of L 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 data model, comprising:

a first table to represent an entity type having a column in the table for a respective attribute of the entity type, and having rows entered with attribute data;

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

a finite distributive lattice (FDL) generated 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 date 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 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 to 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 method of representing data on a computer, comprising the steps of:

constructing a first table to represent an entity type with a column in the table for a respective attribute of the entity type;

entering attribute data into rows of the first table;

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

generating a finite distributive lattice (FDL) 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;

assigning a column graph which represents an ordering relationship between columns of the first table, the column graph being a row graph from a second table; and

interpreting the table, row graph and column graph as a finite sheaf.

44. The method according to claim 43, wherein the first table includes one row for each primary entity of the entity type.

45. 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.

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

47. 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.

48. The method according to claim 43, 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.

49. 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.

50. 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.

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

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

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

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

53. 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.

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

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

55. 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 the sheaf.

56. 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.

57. 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 lattice equal to the union of the schema of L1, L2, . . . Ln, where L1, L2, . . . Ln represents any collection of sheaves.

58. 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 an sheaf and c is a condition on the rows of L.

59. 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.

60. 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.

61. 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.

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

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

63. 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.

64. 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.

65. 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.

66. 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.

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

69. The date model according to claim 67, 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.

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

71. The data model according to claim 67, 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.

72. The data model according to claim 67, 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.

73. The data model according to claim 67, 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.

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

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

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

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

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

77. The data model according to claim 67, 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.

78. The data model according to claim 67, further comprising:

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

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

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 the sheaf.

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

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

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

L2×

. . . ×

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

82. The data model according to claim 67, 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.

83. The data model according to claim 67, 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.

84. The data model according to claim 67, 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.

85. The data model according to claim 67, 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.

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

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

87. The data model according to claim 67, 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.

88. The data model according to claim 67, 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.

89. The data model according to claim 67, 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.

90. The data model according to claim 67, 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.

67. A data model, comprising:

a first table to represent an entity type having a column in the table for a respective attribute of the entity type, and having rows entered with attribute data;

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

a finite distributive lattice (FDL) generated 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;

a column graph which represents an ordering relationship between columns of the first table, the column graph being a row graph from a second table; and

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