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

• US 20030158841A1
• Filed: 11/21/2002
• Published: 08/21/2003
• Est. Priority Date: 07/27/2001
• Status: Active Grant

• Current Assignee: Objectstore Incorporated
• Original Assignee: Metatomix, Inc. (ESW Capital, LLC)
• Inventors: Kumar, Ashok, Britton, Colin P., Bigwood, David, Greenblatt, Howard, DeFusco, Anthony J.
• Granted Patent: US 6,925,457 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 schema, comprising:

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

generating from the first query a second query that specifies RDF triples to be identified in the data store and that reflects the first storage schema;

applying the second query to the data store for identification of the specified RDF triples.

2. The method of claim 1, further comprising;

examining the first query for one or more tokens that represent data to be used in generating the second query; and

dispatching context-specific grammar events containing that data.

3. The method of claim 2, wherein each of the events represents any of a declaration and a constraint specified in the first query.

4. The method of claim 3, wherein the declaration specifies one or more RDF documents from which triples to be identified are contained.

5. The method of claim 3, wherein the constraint specifies RDF triples to be identified.

6. The method of claim 1, further comprising:

extracting statement data from the first query; and

associating that statement data with at least a portion of the second query.

7. The method of claim 6, further comprising:

generating the second query in the form of an SQL SELECT statement.

8. The method of claim 7, wherein the associating step includes associating statement data with one or more of a SELECT clause, a FROM clause, a WHERE clause and a ORDER-BY clause of an SQL statement.

9. The method of claim 1, wherein the RDF triples store uses a hashed by origin schema.

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; and

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.

11. The method of claim 10, wherein dispatching events further comprises generating any of a logical condition event, a selection term declaration event, and a triple declaration event.

12. The method of claim 11, where generating a logical condition event comprises generating an event containing data which, when applied to the relational database via the output query, identifies RDF triples according to a Boolean condition.

13. The method of claim 11, where generating a selection term declaration event comprises generating an event containing data which, when applied to the relational database via the output query, identifies RDF triples including a specified term.

14. The method of claim 11, further where generating a triple declaration event comprises generating an event containing data which, when applied to the relational database via the output query, identifies RDF triples according to a specified subject, predicate and object.

15. The method of claim 10, wherein the first language is any of SQL-like and XML-like.

16. The method of claim 10, further comprising generating the output query as an SQL Select statement.

17. The method of claim 10, wherein the RDF triples are stored in a hashed with origin schema.

18. A digital system for searching an RDF triples data store having a storage schema, comprising:

a parser component that examines a schema-less, first query specifying one or more RDF triples to be identified, the parser component examines the first query for one or more tokens that represent data to be used in generating a second query and that dispatches context-specific grammar events containing that data;

an event-processing component coupled to the parser component, the event-processing component extracts statement data from one or more events;

a statement management/generation component coupled to the event-processing component, the statement management/generation component generates the second query so as to identify the same RDF triples identified in the schema-less, first query and so as to reflect the storage schema of the RDF triples data store.

19. The digital system of claim 18, wherein events represent any of a declaration, constraint and sorting order.

20. The digital system of claim 19, wherein a declaration event specifies RDF documents to be searched for those RDF triples to be identified.

21. The digital system of claim 19, wherein the constraint event specifies RDF triples to be identified that match an associated constraint.

22. The digital system of claim 19, wherein the associated constraint is any of a Boolean expression and a literal.

23. The digital system of claim 19, wherein a sorting order event specifies an order in which identified RDF triples are to be sorted for presentation to a user.