Patent US6052686A successfully refreshed from Google Patents.
US6052686A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database processing using schemas
Assignee: AT&T Inc
•
Filing: 1997-09-18
•
Granted: 2000-04-18
•
Expires: 2017-09-18
Abstract
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.
Inventors
- 👤 Maria F. Fernandez
- 👤 Dan Suciu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 01:24
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/2448; G06F16/21; G06F16/211; G06F16/212; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24562; G06F16/28; G06F16/289; G06F16/90; G06F16/95; G06F16/951; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/959; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
64 words
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.
Claim 2
Independent Claim
64 words
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.
Claim 3
Dependent Claim
41 words
The method of claim 1, wherein the identifying step comprises: generating an automaton based on the desired information; generating the composite automaton by combining a schema of the database with the automaton; and analyzing the composite automaton to identify broken paths.
Claim 4
Dependent Claim
24 words
The method of claim 2, further comprising selecting portions of the automaton that does not correspond to the broken paths of the composite automaton.
Claim 5
Dependent Claim
31 words
The method of claim 3, wherein the processing step comprises: identifying paths of the selected portions of the automaton; and traversing the edge-labeled tree according to each of the identified paths.
Claim 6
Dependent Claim
28 words
The method of claim 4, wherein each node of the edge-labeled tree corresponding to each state of the schema along the each of the identified paths are traversed.
Claim 7
Dependent Claim
33 words
The method of claim 2, wherein the generating an automaton step comprises: generating an expression for the desired information based on the edge-labeled tree; and constructing the automaton that corresponds to the expression.
Claim 8
Dependent Claim
51 words
The method of claim 2, wherein the generating a composite automaton step comprises: generating product states, each of the product states corresponding to a state from the schema and a state from the automaton; and connecting the product states together with transitions based on transitions of the schema and the automaton.
Claim 9
Dependent Claim
48 words
The method of claim 2, wherein the analyzing step comprises: identifying at least one path of the composite automaton that does not terminate in a state that corresponds to a terminal state of the automaton; and identifying the at least one path as one of the broken paths.
Claim 10
Dependent Claim
70 words
A database processing device processing a database modeled as an edge-labeled tree, comprising: a memory; a controller coupled to the memory, the controller identifying at least one path of the edged-labeled tree that does not contain 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.
Claim 11
Dependent Claim
70 words
A database processing device processing a database modeled as an edge-labeled tree, comprising: a memory; a controller coupled to the memory, the controller identifying at least one path of the edged-labeled tree that does not contain 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.
Claim 12
Dependent Claim
39 words
The device of claim 9, wherein the controller generates an automaton based on the desired information, generates the composite automaton by combining a schema of the database with the automaton, and analyzes the composite automaton to identify broken paths.
Claim 13
Dependent Claim
25 words
The device of claim 10, wherein the controller selects portions of the automaton that does not correspond to the broken paths of the composite automaton.
Claim 14
Dependent Claim
29 words
The device of claim 11, wherein the controller identifies paths of the selected portions of the automaton; and traverses the edge-labeled tree according to each of the identified paths.
Claim 15
Dependent Claim
28 words
The device of claim 12, wherein each node of the edge-labeled tree corresponding to each state of the schema along the each of the identified paths are traversed.
Claim 16
Dependent Claim
24 words
The device of claim 10, wherein the controller receives an expression for the desired information and constructs the automation that corresponds to the expression.
Claim 17
Dependent Claim
47 words
The device of claim 10, wherein the controller generates product states, each of the product states corresponding to a state from the schema and a state from the automaton, the controller connecting the product states together with transitions based on transitions of the schema and the automaton.
Claim 18
Dependent Claim
46 words
The device of claim 10, wherein the controller identifies at least one path of the composite automaton that does not terminate in a state that corresponds to a terminal state of the automaton and identifies the at least one path as one of the broken paths.
Claim 19
Independent Claim
72 words
A method for processing a database modeled as an edge-labeled tree to obtain desired information, comprising: identifying at least one node within the edge-labeled tree as a starting node; bypassing a portion of the edge-labeled tree that precedes the starting node; and processing the database with a composite automation which includes a schema having known structure and unknown structure, in a forward direction starting at the starting node for the desired information.
Claim 20
Independent Claim
72 words
A method for processing a database modeled as an edge-labeled tree to obtain desired information, comprising: identifying at least one node within the edge-labeled tree as a starting node; bypassing a portion of the edge-labeled tree that precedes the starting node; and processing the database with a composite automation which includes a schema having known structure and unknown structure, in a forward direction starting at the starting node for the desired information.
Claim 21
Dependent Claim
52 words
The method of claim 17, wherein the identifying step comprises: generating the composite automaton; pruning the composite automaton; selecting at least one state of the pruned composite automaton; and identifying at least one node of the edge-labeled tree corresponding to the selected state of the pruned composite automaton as the starting node.
Claim 22
Dependent Claim
60 words
The method of claim 18, wherein the generating a composite automaton step comprises: generating product states, each of the product states corresponding to a state from a schema of the database and a state from an automaton that corresponds to the desired information; and connecting the product states together with transitions based on transitions of the schema and the automaton.
Claim 23
Dependent Claim
36 words
The method of claim 18, wherein the pruning step comprises: identifying broken paths of the composite automaton; and generating the pruned automaton by removing portions of the composite automaton that corresponds only to the broken paths.
Claim 24
Dependent Claim
48 words
The method of claim 20, wherein the selecting step comprises: forming a hybrid automaton based on a state of the pruned automaton and a schema of the database; simulating the hybrid automaton against the pruned automaton; and selecting the state based on a result of the simulating step.
Claim 25
Dependent Claim
65 words
The method of claim 21, wherein the forming a hybrid automaton step comprises: connecting a state in the schema that corresponds to the state in the automaton with an ε edge; and combining a path of the schema from an initial state of the schema to the state that corresponds to the state in the automaton with all paths of the automaton below the state.
Claim 26
Dependent Claim
88 words
The method of claim 21, wherein the simulating step comprises: identifying an initial state and terminal states of the hybrid automaton and an initial state and terminal states of the automaton; generating hybrid strings by traversing the hybrid automaton from the initial state to anyone of the terminal states; generating strings by traversing the automaton from the initial state to anyone of the terminal states; and verifying that each of the strings of the hybrid automaton is identical to a unique one of the strings of the automaton.
Claim 27
Dependent Claim
15 words
The method of claim 23 wherein the simulation exists if the verifying step is successful.
Claim 28
Dependent Claim
17 words
The method of claim 21, wherein the selecting step selects the state only if a simulation exists.
Claim 29
Dependent Claim
77 words
A database processing device processing a database modeled as an edge-labeled tree, comprising: a memory; a controller coupled to the memory, the controller identifying at least one node within the edge-labeled tree as a starting node, bypassing a portion of the edge-labeled tree preceding the at least one node, and processing the database with a composite automation which includes a schema having known structure and unknown structure starting at the at least one node for desired information.
Claim 30
Dependent Claim
77 words
A database processing device processing a database modeled as an edge-labeled tree, comprising: a memory; a controller coupled to the memory, the controller identifying at least one node within the edge-labeled tree as a starting node, bypassing a portion of the edge-labeled tree preceding the at least one node, and processing the database with a composite automation which includes a schema having known structure and unknown structure starting at the at least one node for desired information.
Claim 31
Dependent Claim
50 words
The device of claim 26, wherein the controller generates the composite automaton, prunes the composite automaton, selects at least one state of the pruned composite automaton, and identifies at least one node of the edge-labeled tree corresponding to the selected state of the pruned composite automaton as the starting node.
Claim 32
Dependent Claim
56 words
The device of claim 27, wherein the controller generates product states, each of the product states corresponding to a state from a schema of the database and a state from an automaton that corresponds to the desired information, the controller connecting the product states together with transitions based on transitions of the schema and the automaton.
Claim 33
Dependent Claim
34 words
The device of claim 27, wherein the controller identifies broken paths of the composite automaton, and generates the pruned automaton by removing portions of the composite automaton that corresponds only to the broken paths.
Claim 34
Dependent Claim
46 words
The device of claim 29, wherein the controller forms a hybrid automaton based on a state of the pruned automaton and a schema of the database, simulates the hybrid automaton against the pruned automaton, and selects the state based on a result of the simulating step.
Claim 35
Dependent Claim
60 words
The device of claim 30, wherein the controller connects a state in the schema that corresponds to the state in the automaton with an ε edge, and combines a path of the schema from an initial state of the schema to the state that corresponds to the state in the automaton with all paths of the automaton below the state.
Claim 36
Dependent Claim
86 words
The device of claim 30, wherein the controller identifies an initial state and terminal states of the hybrid automaton and an initial state and terminal states of the automaton, generates hybrid strings by traversing the hybrid automaton from the initial state to anyone of the terminal states, generates strings by traversing the automaton from the initial state to anyone of the terminal states, and verifies that each of the strings of the hybrid automaton is identical to a unique one of the strings of the automaton.
Claim 37
Dependent Claim
30 words
The device of claim 32, wherein the simulation exists if each of the strings of the hybrid automaton is identical to a unique one of the strings of the automaton.
Claim 38
Dependent Claim
16 words
The device of claim 30, wherein the controller selects the state only if a simulation exists.
Claim 39
Dependent Claim
15 words
The device of claim 26, wherein the database represents the information contained in a network.
Claim 40
Dependent Claim
23 words
The device of claim 35, wherein the network is the Internet and the database represents home pages and information within the home pages.
References Cited (Backward Citations)
US5418942A
Cited
US5564119A
Cited
US5495605A
Cited
US5606690A
Cited
US5590319A
Cited
US5600831A
Cited
US5600829A
Cited
US5758353A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-04-18 | 2003-10-18 | 2004-04-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-04-18 | 2007-10-18 | 2008-04-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-04-18 | 2011-10-18 | 2012-04-18 | $7700.00 | Window Closed / Lapsed |