Data recovery system and method in a resource description framework environment

• US 8,938,456 B2
• Filed: 10/22/2010
• Issued: 01/20/2015
• Est. Priority Date: 10/23/2009
• Status: Active Grant

• Current Assignee: Intellidimension Inc.
• Original Assignee: Intellidimension Inc.
• Inventors: Chappell, Geoffrey, Repchick, Derrish
• Primary Examiner(s): Lin, Shew-Fen
• Assistant Examiner(s): MINCEY, JERMAINE A
• Application Number:
  US12/910,440
• Publication Number:
  US 20110099174A1
• Time in Patent Office: 1,551 Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

A method of optimizing data recovery in an RDF data system in which the occurrence of data values across one or more of subject, predicate, and object are ranked, a handle is assigned to each of one or more of the ranked data values wherein the handle is directly based on the ranking. The rank-based handle can then be used to index the RDF statements. An RDF data recovery system includes an RDF statement processor configured to rank data values and assign handles to data values based on ranking.

Claims

1. A computer implemented method of optimizing data recovery in a resource description framework data system, the method comprising:

ranking the occurrence of data values across one or more of the subject data values, predicate data values, and object data values for a plurality of resource description framework data statements;

and further wherein said ranking includes ranking a frequency of occurrence of subject data values in a predicate and object of other resource description framework data statements;

assigning a handle to one or more of the ranked data values, the handle replacing each of the ranked data values with a shortcut value that utilizes less storage space than the corresponding data value, each shortcut value representing the rank of the corresponding data value relative to the ranked data values in the resource description framework data system;

wherein one or more unranked data values prior to said ranking are assigned one or more handles;

wherein the handles assigned to the unranked data values are assigned based upon a predetermined procedure;

storing each handle in a library with an indication of the corresponding data value;

and indexing the plurality of resource description framework data statements in an ordered index, the ranked and unranked data values of each of the plurality of resource description framework data statements being replaced in the ordered index with the corresponding handle.

2. The method according to claim 1, further comprising deleting said one or more unranked handles after said assigning a handle.

3. The method according to claim 1, wherein said unranked handles are maintained in a memory after said assigning a handle.

4. The method according to claim 1, wherein said assigning a handle includes assigning a handle to all data values in the plurality of resource description framework data statements.

5. The method according to claim 1, wherein said assigning a handle includes assigning a handle to only the data values that are ranked.

6. The method according to claim 1, wherein said assigning a handle includes assigning a handle to ranked data values and data values that are not ranked.

7. The method according to claim 1, wherein said indexing includes an indexing process selected from the group consisting of a self-balancing binary search tree, a hash table, and any combinations thereof.

8. The method according to claim 1, wherein said indexing includes a self-balancing binary search tree process.

9. The method according to claim 1, wherein said indexing includes:

determining a search key set of a plurality of ranking relationships for the subject, predicate, and object for the plurality of resource description framework data statements;

generating a single nodal index including a node for each of the plurality of resource description framework data statements, each node including an identifier of the node, and

assigning to each node of the single nodal index a plurality of rank tracking indicators, the plurality of rank tracking indicators for each node including a position indicator for each of the plurality of ranking relationships, each of the position indicators representing the relative position of the corresponding resource description framework data statement in the corresponding ranking relationship, the single nodal index including the relative position of each node in all of the plurality of ranking relationships in the search key set.

10. The method according to claim 9, wherein each of the position indicators includes a left child node indicator and a right child node indicator.

11. The method according to claim 9, wherein the plurality of ranking relationships includes two or more ranking relationships selected from the group consisting of a subject-predicate-object ranking relationship, a predicate-object-subject ranking relationship, an object-subject-predicate ranking relationship, and any combinations thereof.

12. The method according to claim 1, further comprising converting data that is not in the form of a resource description framework data statement into a resource description framework data statement form prior to said ranking.

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

submitting a query to the resource description framework data system;

applying the query to the ordered index;

using the ordered index to return a set of results for the query via an output device.

14. A machine readable storage medium containing machine executable instructions for implementing a method of optimizing data recovery in a resource description framework data system, the instructions comprising:

a set of instructions for ranking the occurrence of data values across one or more of the subject data values, predicate data values, and object data values for a plurality of resource description framework data statements;

and further wherein said set of instruction for ranking includes a set of instructions for ranking frequency of occurrence of subject data values in a predicate and object of other resource description framework data statements;

a set of instructions for assigning a handle to one or more of the ranked data values, the handle replacing each of the ranked data values with a shortcut value that utilizes less storage space than the corresponding data value, each shortcut value representing the rank of the corresponding data value relative to the ranked data values in the resource description framework data system;

wherein one or more unranked data values prior to said ranking are assigned one or more handles;

wherein the handles assigned to the unranked data values are assigned based upon a predetermined procedure;

a set of instructions for storing each handle in a library with an indication of the corresponding data value; and

a set of instructions for indexing the plurality of resource description framework data statements in an ordered index, the ranked and unranked data values of each of the plurality of resource description framework data statements being replaced in the ordered index with the corresponding handle.

15. The machine readable storage medium according to claim 14, wherein said set of instructions for indexing includes a set of instructions for a self-balancing binary search tree process.

16. The machine readable storage medium according to claim 14, wherein said set of instructions for assigning a handle includes a set of instructions for assigning a handle to all data values in the plurality of resource description framework data statements.

17. The machine readable storage medium according to claim 14, wherein said set of instructions for assigning a handle includes a set of instructions for assigning a handle to only the data values that are ranked.

18. The machine readable storage medium according to claim 14, wherein said set of instructions for assigning a handle includes a set of instructions for assigning a handle to ranked data values and data values that are not ranked.

19. The machine readable storage medium according to claim 14, wherein said set of instructions for indexing includes:

a set of instructions for determining a search key set of a plurality of ranking relationships for the subject, predicate, and object for the plurality of resource description framework data statements;

a set of instructions for generating a single nodal index including a node for each of the plurality of resource description framework data statements, each node including an identifier of the node, and

a set of instructions for assigning to each node of the single nodal index a plurality of rank tracking indicators, the plurality of rank tracking indicators for each node including a position indicator for each of the plurality of ranking relationships, each of the position indicators representing the relative position of the corresponding resource description framework data statement in the corresponding ranking relationship, the single nodal index including the relative position of each node in all of the plurality of ranking relationships in the search key set.

20. The machine readable storage medium according to claim 14, further comprising a set of instructions for converting data that is not in the form of a resource description framework data statement into a resource description framework data statement form prior to ranking the occurrence of data values across one or more of the subject data values, predicate data values, and object data values.

21. A data recovery system for resource description framework data, the system comprising:

an RDF statement processor including one or more connections to one or more databases, said RDF statement processor ranking the occurrence of data values in resource description framework data statements representing data in said one or more databases such that the ranking occurs across one or more of the subject data values, predicate data values, and object data values for the resource description framework data statements, said RDF statement processor assigning a handle to one or more of the ranked data values, the handle replacing each of the ranked data values with a shortcut value that utilizes less storage space than the corresponding data value, each shortcut value representing the rank of the corresponding data value relative to the ranked data values in the one or more databases;

and further wherein said ranking includes ranking frequency of occurrences of subject data values in a predicate and object of other resource description framework data statements;

wherein one or more unranked data values prior to said ranking are assigned one or more handles;

wherein the handles assigned to the unranked data values are assigned based upon a predetermined procedure;

a memory for storing each of the handles in a library with an indication of the corresponding data value; and

an indexing processor for indexing the resource description framework data statements in an ordered index, the ranked data values of each of the resource description framework data statements being replaced in the ordered index with the corresponding handle.

22. The data recovery system according to claim 21, further comprising a query processor for receiving a query and applying the query to the ordered index.