Methods and apparatus for querying a relational data store using schema-less queries

• US 6,925,457 B2
• Filed: 11/21/2002
• Issued: 08/02/2005
• Est. Priority Date: 07/27/2001
• Status: Expired due to Term

• Current Assignee: Objectstore Incorporated
• Original Assignee: Metatomix, Inc. (ESW Capital, LLC)
• Inventors: Kumar, Ashok, Britton, Colin P., Bigwood, David, Greenblatt, Howard, DeFusco, Anthony J.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Abel-Jalil, Neveen
• Application Number:
  US10/302,764
• Publication Number:
  US 20030158841A1
• Time in Patent Office: 985 Days
• Field of Search: 707 1- 10, 707/500, 707/513, 707/104.1, 705/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The invention provides, in one aspect, a method of searching an RDF triples data store of the type in which the triples are maintained in accord with a first storage schema. The method includes inputting a first query specifying RDF triples that are to be identified in the data store. That first query assumes either (i) that the triples are stored in a schema-less manner (i.e., with no storage schema) or (ii) that the triples are maintained in accord with a second storage schema that differs from the first. The method further includes generating, from the first query, a second query that specifies those same RDF triples, yet, that reflects the first storage schema. That second query can be applied to the RDF triples data store in order to identify and/or retrieve the desired data.

Claims

1. A method for searching an RDF triples data store having a first storage scheme, comprising:

inputting a first query specifying one or more RDF triples to be identified in the data store, where the first query reflects any of a second storage schema or no storage schema, where such second storage scheme differs from the first storage schema,

generating from the first query a second query that specifies one or more RDF triples to be identified in the data store responsive to the first query and that reflects the first storage schema,

where the second query comprises

a single SQL SELECT statement with a WHERE clause containing three or more logical conditions limiting triples to be considered for retrieval from the RDF triples data store, where each logical condition specifies one or more RDF triples according to a Boolean condition;

applying the single SQL SELECT statement to the data store for identification of the one or more RDF triples responsive to the first query,

where the RDF triples data store comprises

a triples table that maintains one record for each stored triple,

a resources table that maintains one record for each unique subject, predicate or resource-type object, and

literals table that maintains one record for each unique literal-type object.

2. The method of claim 1, wherein each record of triples table comprises a hash code for each of the subject, predicate and object that make up the respective triple.

3. The method of claim 2, wherein each record of the triples tables comprises an indicator of whether the object of the respective triple is a resource type or literal type object.

4. The method of claim 2, wherein each record of triples table further comprises hash code identifying the document object with which the respective triple is associated.

5. The method of claim 1, wherein each record of the resources table comprises a value of the respective resource, along with its associate hash code, and wherein the resources table is indexed on that associated code.

6. The method of claim 1, wherein the RDF triples store further comprises a namespaces table that maintains one record for each unique portion of a subject, predicate or resource-type object that is common to multiple records in the resources table.

7. The method of claim 6, wherein each record of namespace table comprises a value of that namespace and its associated hash code, and wherein the namespace table is indexed on that associated hash code.

8. The method of claim 1, wherein each record of literals table comprises a value of the respective literal-type object, along with its associated hash code, and wherein the literals table is indexed on that associated hash code.

9. The method of claim 1, wherein the RDF data store further comprises a models table that maintains one record for each RDF document object from which the triples were parsed.

10. A method for translating a schema-less input query in a first language to an output query in a second language, comprising:

examining the schema-less input query for one or more tokens that represent data to be used in generating the output query;

dispatching context-specific grammar events containing that data;

populating portions of the output query according to the events and data;

generating the output query in the second language comprising those populated portions, wherein the output query represents a schema of a relational database storing RDF triples and wherein the output query comprises

a single SQL SELECT statement with a WHERE clause containing three or more logical conditions limiting triples to be considered for retrieval from the RDF triples data store, where each logical condition specifies one or more RDF triples according to Boolean condition,

where the relational database comprises

a triples table that maintains one record for each stored triple,

a resources table that maintains one record for each unique subject, predicate or resource-type object, and

literals table that maintains one record for each unique literal-type object.

11. The method of claim 10, wherein each record of triples table comprises a hash code for each of the subject, predicate and object that make up the respective triple.

12. The method of claim 11, wherein each record of the triples tables comprises an indicator of whether the object of the respective triple is a resource type or literal type object.

13. The method of claim 11, wherein each record of triples table further comprises hash code identifying the document object with which the respective triple is associated.

14. The method of claim 10, wherein each record of the resources table comprises a value of the respective resource, along with its associate hash code, and wherein the resources table is indexed on that associated code.

15. The method of claim 10, wherein the Relational database further comprises a namespaces table that maintains one record for each unique portion of a subject, predicate or resource-type object that is common to multiple records in the resources table.

16. The method of claim 15, wherein each record of namespaces table comprises a value of that namespace and its associated hash code, and wherein the namespace table is indexed on that associated hash code.

17. The method of claim 10, wherein each record of literals table comprises a value of the respective literal-type object, along with its associated hash code, and wherein the literals table is indexed on that associated hash code.

18. The method of claim 10, wherein the RDF data store further comprises a models table that maintains one record for each RDF document object from which the triples were parsed.