US 6,052,686 A · Database processing using schemas

Abstract

An apparatus and method for efficiently processing a database. A structure of the database is constructed into a schema which only includes those structures of the database that are known. Desired information to be extracted from the database is specified using path expressions and an automaton models the path expression. A composite automaton is generated based on the automaton and the schema. The composite automaton is pruned and portions of the database corresponding to the pruned automaton is searched to obtain the desired information. Points within the database may be identified to begin searching for the desired information. These points correspond to states of the composite automaton. A hybrid automaton may be formed for each set of possible starting states to determine completeness by simulating the hybrid automaton against the composite automaton.

Claims36

Dependent claims

A method for processing a database modeled as an edged-labeled tree to obtain desired information, comprising:

identifying at least one path of the edged-labeled tree that does not contain the desired information;
and
processing the database with a composite automation which includes a schema having known structure and unknown structure, to retrieve the desired information without processing the identified path of the edge-labeled tree.

Dependencies are inferred from the claim text.

Database processing using schemas

Life of this patent

Database processing using schemas

Life of this patent

Abstract

Claims36