SCALABLE, SCHEMALESS DOCUMENT QUERY MODEL

• US 20140280047A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Li, Yu, Yuan, Thota, Shireesh Kumar, Budiu, Mihai Dan, Shukla, Dharma, Gajendran, Madhan, Bradley, Quetzalcoatl
• Granted Patent: US 9,230,040 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Query models for document sets (such as XML documents or records in a relational database) typically involve a schema defining the structure of the documents. However, rigidly defined schemas often raise difficulties with document validation with even inconsequential structural variations. Additionally, queries developed against schema-constrained documents are often sensitive to structural details and variations that are not inconsequential to the query, resulting in inaccurate results and development complications, and that may break upon schema changes. Instead, query models for hierarchically structured documents that enable “twig” queries specifying only the structural details of document nodes that are relevant to the query (e.g., students in a student database having a sibling named “Lee” and a teacher named “Smith,” irrespective of unrelated structural details of the document). Such “twig” query models may enable a more natural query development, and continued accuracy of queries in the event of unrelated schema variations and changes.

Claims

1. A method of applying, on a device having a processor, queries to a document set comprising at least one document, respective documents comprising at least one node comprising a node name and a node path from a root node of the document, the method comprising:

executing on the processor instructions configured to, upon receiving a query specifying a query node path comprising at least one query node identifier;

identify at least one matching document having at least one matching node comprising, for respective query node identifiers, at least one path node in the node path of the matching node that matches the query node identifier; and

present at least a portion of the at least one matching document in response to the query.

2. The method of claim 1, respective nodes specified in a JavaScript Object Notation format.

3. The method of claim 1:

the query node path specifying a first query node identifier followed by a second query node identifier; and

identifying the matching documents comprising;

identifying at least one matching document having at least one matching node comprising, in the node path of the matching node;

a first path node matching the first query node identifier; and

a second path node following the first path node in the node path of the matching node and matching the second query node identifier.

4. The method of claim 1:

the query node path specifying at least query node identifier set comprising at least two alternative query node identifiers; and

identifying the matching documents comprising;

identifying at least one matching document having at least one matching node comprising, for respective query node identifier sets, at least one path node in the node path of the matching node that matches at least one of the alternative query node identifiers.

5. The method of claim 1:

at least one node of at least one document further comprising a node value;

the query node path specifying at least one query node value; and

identifying the matching documents comprising;

identifying at least one matching document having at least one matching node comprising, for respective query node values of the query, at least one path node in the node path of the matching node that matches the query node identifier and a node value matching the query node value.

6. The method of claim 5:

the query node path specifying a query node value range; and

identifying the matching documents comprising;

identifying at least one matching document having at least one matching node comprising, for respective query node values of the query, at least one path node in the node path of the matching node that matches the query node identifier and a node value within the query node value range.

7. The method of claim 1:

the query specifying;

a first query node identifier, and

a second query node identifier having a second node path having a relationship with a first node path of a matching node that matches the first query node identifier; and

identifying the matching documents comprising;

identifying at least one matching document having at least one matching node comprising;

a first matching node that matches the first query node identifier; and

a second matching node that matches the second query node identifier and a second node path satisfying the relationship with the first node path of the first matching node.

8. The method of claim 1:

the query comprising;

a query selection selecting a query node subset of respective documents; and

identifying the matching documents comprising;

selecting a node subset comprising the nodes of the document within the query node subset; and

applying a remainder of the query to only the node subset.

9. The method of claim 8, the query node subset specified as child nodes descending from a matching node.

10. The method of claim 1:

at least one node of at least one document further comprising a node value;

the query node path requesting at least one node value to be returned for matching nodes; and

presenting the at least one matching document comprising;

for respective matching nodes of respective matching documents, presenting the node value of the matching node.

11. The method of claim 1:

the query requesting at least one child node that descends from a matching node; and

presenting the at least one matching document comprising;

for respective matching nodes of respective matching documents, presenting at least one child node that descends from the matching node.

12. The method of claim 1:

the query requesting a set of query results; and

the instructions further comprising;

partitioning the query results into query result ranges;

returning the query results within a first query result range; and

upon receiving a request to return a second query result range, return the query results within the second query result range.

13. The method of claim 1:

the query further comprising at least one script to be applied to at least one matching document; and

the instructions further configured to, upon identifying a matching document, applying the script to the matching document.

14. The method of claim 1:

the instructions further configured to, upon receiving a document, index the document in a document index according to, for respective nodes, the node path; and

identifying the at least one matching document comprising;

for respective query node identifiers, examine the document index to identify the matching documents having at least one matching node comprising, for respective query node identifiers, at least one query node in the node path of the matching node that matches the query node identifier.

15. The method of claim 14:

at least one node of at least one document further comprising a node value; and

indexing the documents further comprising;

indexing the document in a document index according to, for respective nodes, the node path and the node value of the node.

16. The method of claim 14, the document index comprising a reverse index indicating, for respective query node paths, the at least one matching documents having at least one matching node comprising, for respective query node identifiers, at least one query node in the node path of the matching node that matches the query node identifier.

17. The method of claim 14, generating the document index further comprising:

for at least two matching nodes matching a query node path through different node paths, consolidating the nodes in the document index.

18. The method of claim 17, consolidating the nodes further comprising:

identifying a similarity degree of the different node paths of the matching nodes; and

consolidating the matching nodes in the document index only if the similarity degree of the different node paths exceeds a similarity degree threshold.

19. A nonvolatile computer-readable storage device comprising instructions that, when executed on a processor of a device, apply queries to a document set comprising at least one document, respective documents comprising at least one node comprising a node name and a node path from a root node of the document, by:

upon receiving a query specifying a query node path comprising at least one query node identifier;

identifying at least one matching document having at least one matching node comprising, for respective query node identifiers, at least one path node in the node path of the matching node that matches the query node identifier; and

presenting at least a portion of the at least one matching document in response to the query.

20. A system of applying, on a device having a processor and a memory, queries to a document set comprising at least one document, respective documents comprising at least one node comprising a node name and a node path from a root node of the document, the system comprising:

a document index indicating, for respective query node paths, at least one matching document respectively having at least one matching node comprising, for respective query node identifiers, at least one path node in the node path of the matching node that matches the query node identifier;

a document indexing component comprising instructions stored in the memory that, when executed on the processor, upon receiving a document, index the document in the document index according to, for respective nodes, the node path; and

a query processing component comprising instructions stored in the memory that, when executed on the processor, upon receiving a query specifying a query node path comprising at least one query node identifier;

examine the document index to identify at least one matching document having at least one matching node comprising, for respective query node identifiers, at least one path node in the node path of the matching node that matches the query node identifier; and

present at least a portion of the at least one matching document in response to the query.