Lattice data set-based methods and apparatus for information storage and retrieval

• US 8,195,712 B1
• Filed: 04/17/2009
• Issued: 06/05/2012
• Est. Priority Date: 04/17/2008
• Status: Active Grant

• Current Assignee: Lattice Engines, Inc. (Dun & Bradstreet Corp.)
• Original Assignee: Lattice Engines, Inc. (Dun & Bradstreet Corp.)
• Inventors: McCormick, Kent
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Weinrich, Brian E.
• Application Number:
  US12/425,926
• Time in Patent Office: 1,145 Days
• Field of Search: 707/803, 707/809, 707/769
• US Class Current: 707/803
• CPC Class Codes: G06F 16/212 with details for data modelling support

Abstract

In one aspect, an apparatus according to the invention comprises a lattice data set with a partial order of concepts (LDSWPOC) including a plurality of data elements, each of which belongs to exactly one associated concept. The set of concepts carries the structure of a partial order. Each data elements associated with a concept may be linked to one or more other data elements associated with one or more other concepts. The links define (i) a path between data elements directly linked thereby and/or (ii) a portion of a path between data elements linked by intermediate subsets of data elements. The paths define a relationship between the data elements in accord with the partial order of the concepts with which they are associated, such that selected conditions and/or constraints (collectively, “conditions”) are satisfied.

Claims

1. A lattice database management system comprising:

a computer including a lattice data set and a mechanism to identify a subset of lattice data elements associated with a particular concept from the lattice data set;

wherein the lattice data set comprises;

A. a plurality of data elements, each of which is associated with a concept from a set of concepts having a partial order structure, wherein that set is hereinafter referred to as a partial order of concepts (POC),

B. a plurality of paths between one or more data elements associated with a concept and one or more other data elements associated with another concept, the plurality of paths defining a relationship between data elements in accord with the partial order of the concepts with which the data elements are associated, such that;

(i) when data element a is associated with concept A, data element b is associated with concept B, and there is a path (a, b) between a and b, A<

B in the partial order of concepts, and

(ii) when there exists a path from a first data element associated with a first concept to a second data element associated with a second concept, all paths from the first data element to the second concept terminate on the second data element,

C. wherein the lattice data set is referred to hereinafter as a lattice data set with a partial order of concepts (LDSWPOC); and

D. wherein the plurality of paths define a relationship between data elements in the lattice data set such that;

(iii) for data elements a, b, c, when;

a is associated with concept A,

b is associated with concept B,

c is associated with concept C,

there exists a path (a, b) from a to b;

there exists a path (a, c) from a to c; and

the inequality B<

C is defined in the partial order of concepts,

there exists a path (b, c) from b to c.

2. The lattice database management system of claim 1, wherein the plurality of paths define a relationship between data elements in the lattice data set such that:

(iv) for data elements a, b, c and concepts A, B, C, where;

C<

A,

C<

B,

a is associated with concept A,

b is associated with concept B, and

c is associated with concept C,

and where there exists paths from;

c to a, and

c to b,

then for each concept X such that X<

A and X<

B and such that there does not exist a concept Y such that X<

Y and Y<

A and Y<

B, there exists an element ab associated with concept X such that there exists paths from

c to ab,

ab to a, and

ab to b.

3. The lattice database management system of claim 2, wherein

A. the partial order of concepts is a meet semi-lattice of concepts wherein for any two concepts A, B there exists another concept C in the partial order such that C is a unique greatest lower bound for A and B in the partial order, and

B. wherein the lattice data set is referred to hereinafter as a lattice data set with meet semi-lattice of concepts (LDSWMSOC).

4. The lattice database management system of claim 3, wherein the plurality of paths define a relationship between data elements in the lattice data set such that:

(v) for any two concepts A and B in the LDSWMSOC, the minimal upper bound (A V B) of those two concepts always exists and is unique, and

(vi) a maximal concept, obtained by taking the join of all concepts, has at least one data element (ALL) to which each data element in the LDSWMSOC maps.

5. The lattice database management system claim 4, wherein

A. the partial order of concepts satisfies conditions for a lattice, and

B. wherein the lattice data set is referred to hereinafter as a lattice data set with lattice of concepts (LDSWLOC).

6. The lattice database management system of claim 5, further comprising any of a creation/update module and a query engine including operator functionality that associates at least one of a meet operator and a join operator with the lattice data set to identify subsets having a semi-lattice or lattice structure.

7. The lattice database management system of claim 6, wherein the meet and join operators, when restricted to a subset of data elements associated with a single concept, are set intersection and set union operators.

8. The lattice database management system of claim 7, wherein the operator functionality effects said meet and join operators according to one or more selected rules.

9. The lattice database management system of claim 8, wherein the selected rules include, for any LDSWLOC in which A1 is a subset of data elements of concept A, and B1 is a subset of data elements of concept B:

(i) the concept associated with A1Λ

B1 is AΛ

B,

(ii) the subset associated with AΛ

B that corresponds to A1Λ

B1 is the largest subset, such that for all elements ab in that subset, there is a path from data element ab to a data element a1 in subset A1, and there is also a path from the data element ab to data element b1 in subset B1,

(iii) the concept associated with A V B is the minimal concept in the lattice of concepts of the LDSWLOC that satisfies A V B≧

A V B and for all elements a1 in A1 there exists an element xa in the concept A V B such that there is a path from a1 to xa, and for all elements b1 in B1 there exists an element xb in A V B such that there is a path from b1 to xb, and

(iv) the subset A1 V B1 of A V B is the smallest subset that satisfies the conditions of (iii).

10. A method for creating a lattice data set using a computer, comprising:

A. associating each of a plurality of data elements with one or more concepts from a set of concepts having a partial order structure, wherein that set is hereinafter referred to as a partial order of concepts (POC),

B. defining a plurality of paths between one or more data elements associated with a concept and one or more other data elements associated with another concept, the plurality of paths defining a relationship between data elements in accord with the partial order of the concepts with which the data elements are associated, such that;

(i) when data element a is associated with concept A, data element b is associated with concept B, and there is a path (a, b) between a and b, A<

B in the partial order of concepts, and

(ii) when there exists a path from a first data element associated with a first concept to a second data element associated with a second concept, all paths from the first data element to the second concept terminate on the second data element,

C. wherein the lattice data set is referred to hereinafter as a lattice data set with a partial order of concepts (LDSWPOC); and

D. wherein the plurality of paths define a relationship between data elements in the lattice data set such that;

(iii) for data elements a, b, c, when;

a is associated with concept A,

b is associated with concept B,

c is associated with concept C,

there exists a path (a, b) from a to b,

there exists a path (a, c) from a to c, and

the inequality B<

C is defined in the partial order of concepts,

there exists a path (b, c) from b to c.

11. The method of claim 10, including creating the POC.

12. The method of claim 10, wherein the POC is created from a relational context (RC).

13. The method of claim 12, wherein the RC comprises any of:

i. a set of relations,

ii. a set of cardinality constraints on those relations,

iii. a set of column identifications associated with the relations,

iv. a set of primary keys identified on those relations,

v. a set of many-to-one constraints on pairs of sets of columns in a relation,

vi. a set of independent relational paths that are considered as equivalent, and

vii. a set of declarations that specify that certain columns should be or should not be considered discrete-valued.

14. The method of claim 13, comprising:

A. creating, from the RC, the POC and a data set where each data element is associated with one of the concepts in the POC,

B. defining zero or more links between said data elements,

C. wherein a collection of said data elements, concepts, and links is referred to hereinafter as a linked concept data set (LCDS).

15. The method of claim 14, wherein the creating step includes generating any of an error log, link errors, events and/or alerts in response to data identified as being absent from or as being inconsistent in the LCDS.

16. The method of claim 14, comprising creating a set of constructed concepts (SCC) from a LCDS.

17. The method of claim 16, comprising creating the SCC using relation, copy, assert, and function-to-concept operators.

18. The method of claim 17, comprising creating a lattice of concepts (LOC) from a POC, an optional SCC, an optional set of LOCs, and an optional set of lattice identifications and inequalities (SLIIs).

19. The method of claim 18, wherein the LOC is created by extending the partial order of concepts with meet and join operators.

20. The method of claim 18, wherein multiple lattices are combined by specifying a set of identifications of concepts from one lattice to concepts in another lattice.

21. The method of claim 18, comprising creating a lattice data set with a lattice of concepts (LDSWLOC) from a LOC, an optional set of lattice constraints (SLC), and a LDSWPOC.

22. The method of claim 21, comprising generating any of logs of data, link errors, events and/or alerts about missing or inconsistent data in the LDSWPOC.

23. The method of claim 18, comprising creating a lattice data set with a lattice of concepts (LDSWLOC) wherein the partial order of concepts is also a meet semi-lattice of concepts (LDSWMSOC), wherein for any two concepts A, B there exists another concept C in the partial order such that C is a unique greatest lower bound for A and B in the partial order.

24. The method of claim 23, wherein the plurality of paths define a relationship between data elements in accord with the partial order of the concepts with which the data elements are associated, such that:

(iv) for any two concepts A and B in the LDSWMSOC, the minimal upper bound (A V B) of those two concepts always exists and is unique, and

(v) a maximal concept, obtained by taking the join of all concepts, has at least one data element (ALL) to which each data element in the LDSWMSOC maps.

25. The method of claim 24, wherein a lattice data set having a partial order of concepts that satisfies the conditions for a lattice comprises a lattice data set with a lattice of concepts (LDSWLOC).

26. The method of claim 25, comprising creating a set of functions on a LDSWLOC (SFOLDSWLOC) from an optional set of expressions, an optional set of aggregation rules, an optional set of lambda expressions, a LDSWLOC, an optional SFOLDSWLOC, and an optional LCDS.

27. The method of claim 25, comprising creating a LDSWLOC from a LDSWLOC, an optional set of injection assertions (SIA), an optional SLC, an optional set of functions on a LDSWLOC (SFOLDSWLOC), and an optional SCC.

28. The method of claim 27, comprising any of generating logs of data, link errors, events and/or alerts about missing or inconsistent data in the LDSWPOC.

29. The method of claim 25, comprising meet and join operators that endow with a lattice structure a set constructed by, first, taking the powerset of data elements for each concept and, then, constructing the union of those powersets for all concepts in the lattice data set.

30. The method of claim 29, wherein the meet and join operators are set intersection and set union operators when both arguments of the operator are subsets of data elements from the same concept.

31. The method of claim 30, comprising generating a LCDS from an optional LDSWLOC, an optional SFOLDSWLOC, an optional SCC, and an optional LCDS.

32. The method of claim 30, wherein the meet and join operators are implemented according to one or more selected rules.

33. The method of claim 32, wherein the selected rules include for any LDSWLOC in which A1 is a subset of data elements of concept A, and B1 is a subset of data elements of concept B:

(i) the concept associated with A1Λ

B1 is AΛ

B,

(ii) the subset associated with AΛ

B that corresponds to A1Λ

B1 is the largest subset, such that for all elements ab in that subset, there is a path from data element ab to data element a1 in subset A1, and there is a path from ab to data element b1 in subset B1 for some k,

(iii) the concept associated with A1 V B1 is the minimal concept, X, in the LOC that satisfies X≧

A V B and for all elements a1 in A1 there exists an element x in X such that there is a path from a1 to x, and for all elements b1 in B1 there exists an element x in X such that there is a path from b1 to x,

(iv) the subset of X assigned to A1 V B1 is the smallest such subset that for all elements a1 in A1 there exists a path to some element x in A1 V B1 and for all elements b1 in B1 there exists a path to some element x in A1 V B1.

34. The method of claim 33, comprising retrieving information from any of a lattice data set with a partial order of concepts (LDSWPOC), an optional associated set of functions on a LDSWPOC (SFOLDSWPOC), and an optional cache of previous results.

35. A method of querying a lattice data set using a computer, comprising:

I. defining a query comprising a lattice element identifier and a set of one or more functions, the lattice element identifier specifying any of (1) a lattice element and (2) a plurality of lattice elements and one or more operators that act thereon,

II. retrieving information from the lattice data set based upon the query and an inferred relationship between concepts represented by the lattice element identifier, where that relationship is not explicit in the lattice data set itself, and

III. any of storing, transmitting, and displaying the retrieved information,

wherein the lattice data set comprises;

A. a plurality of data elements, each of which is associated with a concept from a set of concepts having a partial order structure, wherein that set is hereinafter referred to as a partial order of concepts (POC),

B. a plurality of paths between one or more data elements associated with a concept and one or more other data elements associated with another concept, the plurality of paths defining a relationship between data elements in accord with the partial order of the concepts with which the data elements are associated, such that;

(i) when data element a is associated with concept A, data element b is associated with concept B, and there is a path (a, b) between a and b, A<

B in the partial order of concepts, and

(ii) when there exists a path from a first data element associated with a first concept to a second data element associated with a second concept, all paths from the first data element to the second concept terminate on the second data element,

C. wherein the lattice data set is referred to hereinafter as a lattice data set with a partial order of concepts (LDSWPOC); and

D. wherein the plurality of paths define a relationship between data elements in the lattice data set such that;

(iii) for data elements a, b, c, when;

a is associated with concept A,

b is associated with concept B,

c is associated with concept C,

there exists a path (a, b) from a to b;

there exists a path (a, c) from a to c; and

the inequality B<

C is defined in the partial order of concepts,

there exists a path (b, c) from b to c.

36. The method of claim 35, comprising a mechanism whereby all components of a system specification including relational contexts (RCs), sets of constructed concepts (SCCs), linked concept data sets (LCDS), sets of lattice identifications and inequalities (SLII), lattices of concepts (LOC), sets of lattice constraints (SLCs), lattice data sets with partial orders of concepts (LDSWPOC), lattice data sets with lattices of concepts (LDSWLOC), functions, queries, and sources of underlying data sets themselves may be independently or collectively managed by a versioning system so that queries can reference any combination of valid versions of system specification and data set versions.

37. The method of claim 35, comprising a step of creating a set of functions on a lattice data set with a partial order of concepts (SFOLDSWPOC) from any of expressions, aggregations, lambda expressions, LDSWPOC, SFOLDSWPOC, and a linked concept data set (LCDS).

38. The method of claim 35, comprising a step of creating a set of functions on a lattice data set with a lattice of concepts (SFOLDSWLOC) from any of expressions, aggregations, and lambda expressions, on a lattice data set with a lattice of concepts (LDSWLOC), SFOLDSWLOC, and a linked concept data set (LCDS).

39. The method of claim 35, wherein step (II) comprises retrieving information from any of a lattice data set with a partial order of concepts (LDSWPOC), an optional associated set of functions on a lattice data set with a lattice of concepts (SFOLDSWLOC), and an optional cache of previous results.

40. The method of claim 39, comprising updating the cache of previous results with either results of the current query or with any intermediate calculations performed therein.

41. The method of claim 39, wherein any of the query, functions, and lattice elements are evaluated lazily.