Indexing, rewriting and efficient querying of relations referencing semistructured data
AssigneedeCODE Genetics ehf.
InventorsAgust Sverrir Egilsson, Hakon Gudbjartsson
Life of this patent
Estimating the term…
Abstract
The invention discloses methods and apparatus that facilitate efficient querying of tables referencing semistructured data such as digraphs and other domains with complex grouping structure. The invention methods enable meaningful indexing of the tables as well as rewriting of queries with respect to the structures. Dynamic schema extraction using proper coloring algorithms is disclosed that structures the semistructured data in such a way that complex set operations and grouping are replaced with traditional relational joins. This enables a relational database system to harness its entire query optimizing capability when querying tables referencing semistructured data.
Claims33
A method for facilitating efficient querying, of a relation in semistructured data, comprising:
- extracting schema information, in a database system, from semistructured data;
- and
- using a given set valued function which references the semistructured data and using said semistructured data, building a schema structure including the extracted schema information, so that queries conditioned on said set valued function may be evaluated using said, schema structure joined with the relation, instead of said set valued function.
A method of indexing, in a database system, to facilitate efficient querying, of a relation, conditioned on a set valued function referencing digraphs, comprising:
- dynamically evaluating said set valued function and using said evaluations to dynamically build and supply said database system with bitmap arrays, providing pointers for a node in said digraph to all rows, in said relation, containing nodes from the output set of said set valued function when applied to said node.
An apparatus for extracting schema structure, in a database system, from semistructured data for facilitating efficient querying, of a relation, conditioned on a set valued function referencing said data, said apparatus comprising using said set valued function and said semistructured data to build said schema structure so that queries conditioned on said set valued function may be evaluated using said, joined, schema structure and relation instead of said set valued function.
An apparatus for indexing, in a database system, to facilitate efficient querying, of a relation, conditioned on a set valued function referencing digraphs, comprising dynamically evaluating said set valued function and using said evaluations to dynamically build and supply said database system with bitmap arrays, providing pointers for a node in said digraph to all rows, in said relation, containing nodes from the output set of said set valued function when applied to said node.
An article of manufacture comprising a program storage medium readable by a computer and tangibly embodying at least one program of instructions executable by said computer to perform method steps for extracting schema structure, in a database system, from semistructured data for facilitating efficient querying, of a relation, conditioned on a set valued function referencing said data, said method comprising using said set valued function and said semistructured data to build said schema structure so that queries conditioned on said set valued function may be evaluated using said, joined, schema structure and relation instead of said set valued function.
An article of manufacture comprising a program storage medium readable by a computer and tangibly embodying at least one program of instructions executable by said computer to perform method steps for indexing, in a database system, to facilitate efficient querying, of a relation, conditioned on a set valued function referencing digraphs, comprising dynamically evaluating said set valued function and using said evaluations to dynamically build and supply said database system with bitmap arrays, providing pointers for a node in said digraph to all rows, in said relation, containing nodes from the output set of said set valued function when applied to said node.
Dependencies are inferred from the claim text.