Parent-Child Query Indexing for XML Databases
AssigneeMark Logic Corporation
InventorsChristopher Lindblad, Paul Pedersen
Life of this patent
Estimating the term…
Abstract
A method for processing queries for a document of elements is provided. The document includes a plurality of subsections where each subsection includes at least a portion of elements in the document. The method comprises: receiving a query for a path of elements in the document of elements; determining a plurality of step queries from the query, each step query including at least a part of the path of elements; for each step query in the plurality of step queries, determining one or more subsections that include elements that correspond to a step query; and determining at least one subsection that includes the path of elements of the query. A result for the query is generated using the at least one subsection.
Claims18
A computer-implemented method of searching a structured document for text having relevance to a given set of terms, using a processor, the method comprising:
- receiving a node set corresponding to at least one fragment of the structured document, wherein the fragment includes at least a portion of text of the structured document and at least one corresponding pre-computed step query;
- receiving at least one search term;
- receiving a pre-computed lookup index with entries corresponding to the fragments, each entry having an associated subtree identifier;
- searching the lookup index with the search terms;
- returning a set of resulting step queries indicated by the lookup index and corresponding to the search terms;
- assessing an intersection of the resulting step queries with the given set of terms, wherein the resulting step queries each have an associated subtree identifier;
- and
- retrieving a node set associated with the intersection and corresponding to a fragment.
A computer-implemented method of pre-computing at least a portion of an index used in performing a full-text search of a document, using a processor, the method comprising:
- receiving a plurality of input query values, wherein each input query value is a fundamental search pattern specification;
- receiving at least one query operator configured to specify a relationship between input query values;
- assembling an application of the at least one query operator across input query values, the assembly configured to be a query function;
- applying at least one query function to the input query values;
- and
- returning an output query value specifying a search configured to apply the associated query functions in an interrelated fashion across a set of input argument query values, wherein the output query value is at least a portion of a full-text search pattern.
A computer-implemented method of detecting a false positive in a multistep query across a plurality of step queries, using a processor, the method comprising:
- receiving a multistep query prescribing a sequence of step queries;
- determining an intersection of the sequence of step queries with the plurality of step queries, the intersection having a corresponding plurality of subtree identifiers;
- selectively retrieving a subtree fragment corresponding to one of the plurality of subtree identifiers, the subtree fragment containing a set of step queries corresponding to at least a portion of the sequence of step queries, wherein the set of step queries is at least a portion of the plurality of step queries;
- traversing the subtree fragment by querying the set of step queries according to the portion of the sequence of step queries;
- and
- indicating a false positive if the query of the set of step queries does not traverse the subtree fragment.
A pre-processor for generating a computer-readable database of step queries and step query results, wherein the step queries and step query results are for a collection of structured documents, each structured document comprising one or more document elements, the pre-processor comprising:
- a step query generator that generates step queries from patterns from hierarchical structures of elements in structured documents in the collection;
- a canonicalizer, coupled to the step query generator and having input to receive step queries from the step query generator, and having logic to reduce step queries to their canonical forms;
- a hash key generator, coupled to receive canonical form step queries from the canonicalizer and having logic to generate hash keys for canonical forms that may be used for indexing results for step queries;
- storage for an index of hash keys generated by the hash key generator;
- a step query result generator, coupled to the hash key generator and having an input for document elements, for generating step query results based on the collection of structured documents, using the hierarchical structures;
- and
- storage for results of the step queries, usable for future queries.
Dependencies are inferred from the claim text.