Data Recovery System and Method In A Resource Description Framework Environment

• US 20110099174A1
• Filed: 10/22/2010
• Published: 04/28/2011
• Est. Priority Date: 10/23/2009
• Status: Active Grant

• Current Assignee: Intellidimension Inc.
• Original Assignee: Intellidimension Inc.
• Inventors: Repchick, Derrish, Chappell, Geoffrey
• Granted Patent: US 8,938,456 B2
• Time in Patent Office: 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;

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;

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 data values of each of the plurality of resource description framework data statements being replaced in the ordered index with the corresponding handle.

2. A method according to claim 1, wherein said ranking includes ranking the frequency of occurrence of subject data values in a predicate and/or object of other resource description framework data statements.

3. A method according to claim 1, wherein one or more data values prior to said ranking include one or more unranked handles that were assigned without consideration of ranking.

4. A method according to claim 3, further comprising deleting said one or more unranked handles after said assigning a handle.

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

6. A 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.

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

8. A 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.

9. A 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.

10. A method according to claim 1, wherein said indexing includes a self balancing binary search tree process.

11. A 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.

12. A method according to claim 11, wherein each of the position indicators includes a left child node indicator and a right child node indicator.

13. A method according to claim 11, 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.

14. A 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.

15. A 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.

16. 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;

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;

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 data values of each of the plurality of resource description framework data statements being replaced in the ordered index with the corresponding handle.

17. A machine readable storage medium according to claim 16, wherein said set of instructions for ranking includes a set of instructions for ranking the frequency of occurrence of subject data values in a predicate and/or object of other resource description framework data statements.

18. A machine readable storage medium according to claim 16, wherein said set of instructions for indexing includes a set of instructions for a self balancing binary search tree process.

19. A machine readable storage medium according to claim 16, 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.

20. A machine readable storage medium according to claim 16, 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.

21. A machine readable storage medium according to claim 16, 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.

22. A machine readable storage medium according to claim 16, 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.

23. A machine readable storage medium according to claim 16, 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.

24. 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;

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.

25. A data recovery system according to claim 24, further comprising a query processor for receiving a query and applying the query to the ordered index.