US5987449A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Queries on distributed unstructured databases
Assignee: AT&T Inc
•
Filing: 1997-08-12
•
Granted: 1999-11-16
•
Expires: 2017-08-12
Abstract
Abstract A method and apparatus for applying a query to a database that is distributed into first portions. The query is first partially performed by terminals each containing one of the first portions. The results of the partial queries are recombined in such a way as to minimize the traffic among the terminals connected across networks. Paths of an edge-labeled tree representing the database connecting the first portions are expanded into subpaths corresponding to all the states of an automaton modeling the query. The database is distributed into second portions based on the automaton. Non-existing subpaths are ignored based on the automaton and which of the second portions the paths exit. Thus, the data transferred among first portions are minimized and the query process is optimized.
Inventors
- 👤 Dan Suciu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:53
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2471; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
119 words
A method for applying a query to a distributed database that may be represented by an edge-labeled tree and that is decomposed into first portions, comprising: identifying paths of the edge-labeled tree that represents the distributed database, each of the paths exiting from one of the first portions and entering another one of the first portions, paths that exit one of the first portions being exiting paths and paths that enter one of the first portions being entering paths, each of the exiting paths correspond to one of the entering paths; decomposing the query into sub-queries; applying at least one of the sub-queries to the entering paths; and combining results of the sub-queries into a result of the query.
Claim 2
Independent Claim
119 words
A method for applying a query to a distributed database that may be represented by an edge-labeled tree and that is decomposed into first portions, comprising: identifying paths of the edge-labeled tree that represents the distributed database, each of the paths exiting from one of the first portions and entering another one of the first portions, paths that exit one of the first portions being exiting paths and paths that enter one of the first portions being entering paths, each of the exiting paths correspond to one of the entering paths; decomposing the query into sub-queries; applying at least one of the sub-queries to the entering paths; and combining results of the sub-queries into a result of the query.
Claim 3
Dependent Claim
54 words
The method of claim 1, wherein the decomposing the query step comprises: modeling the query as an automaton having a plurality of states, the automaton having a root state; and defining a plurality of sub-automatons corresponding to each of the states of the automaton, each of the sub-automatons corresponding to one of the sub-queries.
Claim 4
Dependent Claim
40 words
The method of claim 2, wherein the defining step comprises: selecting a state of the automaton; defining the selected state as a root state of one of the sub-automatons; and deleting all states and transitions prior to the selected state.
Claim 5
Dependent Claim
20 words
The method of claim 2, wherein the applying step comprises applying all the sub-queries to each of the entering paths.
Claim 6
Dependent Claim
74 words
The method of claim 2, wherein the applying step comprises: decomposing the distributed database into second portions, each of the second portions corresponding to one of the sub-queries; determining information regarding from which of the second portions each of the exiting paths exits; selecting a sub-query that corresponds to the second portions for each of the exiting paths; and applying selected sub-queries to respective entering paths that correspond to each of the exiting paths.
Claim 7
Dependent Claim
73 words
The method of claim 5, wherein the determining step comprises: determining whether each of the exiting paths may be traced to a root of the edge-labeled tree; identifying which of the second portions immediately precedes each of the exiting paths if each of the exiting paths is traceable to the root; and identifying all the second portions as corresponding to an exiting path if the exiting path is not traceable to the root.
Claim 8
Dependent Claim
48 words
The method of claim 5, wherein the decomposing the distributed database step comprises assigning to one of the second portions of the distributed database all the edges and nodes of the edge-labeled tree that may be traversed without transitioning out of one of the states of the automaton.
Claim 9
Dependent Claim
46 words
The method of claim 5, further comprising: transferring results of the determining step to terminals processing entering paths; selecting sub-queries based on transferred results; applying only selected sub-queries to the corresponding entering paths; and applying all sub-queries to entering paths that have no corresponding selected sub-queries.
Claim 10
Dependent Claim
32 words
The method of claim 8, wherein the transferring step begins at a terminal that contains the root of the edge-labeled tree, then each of the terminals transferring the information to other terminals.
Claim 11
Independent Claim
151 words
An apparatus that applies a query to a distributed database that may be represented by an edge-labeled tree and that is decomposed into first portions, comprising: a network; a plurality of terminals coupled to the network, each of the terminals containing one of the first portions, wherein paths of the edge-labeled tree that represents the distributed database exiting from one of the first portions contained in one of the terminals and entering another one of the first portions contained in another of the terminals, paths that exit one of the first portions being exiting paths and paths that enter one of the first portions being entering paths, each of the exiting paths correspond to one of the entering paths, the plurality of terminals: decomposing the query into sub-queries; applying at least one of the sub-queries to the entering paths; and combining results of the sub-queries into a result of the query.
Claim 12
Independent Claim
151 words
An apparatus that applies a query to a distributed database that may be represented by an edge-labeled tree and that is decomposed into first portions, comprising: a network; a plurality of terminals coupled to the network, each of the terminals containing one of the first portions, wherein paths of the edge-labeled tree that represents the distributed database exiting from one of the first portions contained in one of the terminals and entering another one of the first portions contained in another of the terminals, paths that exit one of the first portions being exiting paths and paths that enter one of the first portions being entering paths, each of the exiting paths correspond to one of the entering paths, the plurality of terminals: decomposing the query into sub-queries; applying at least one of the sub-queries to the entering paths; and combining results of the sub-queries into a result of the query.
Claim 13
Dependent Claim
18 words
The apparatus of claim 10, wherein the terminals applies all the sub-queries to each of the entering paths.
Claim 14
Dependent Claim
43 words
The apparatus of claim 10, wherein the terminals generate the sub-queries based on an automaton that models the query, the automaton having a plurality of states and a root state, each of the sub-queries corresponding to one of the states of the automaton.
Claim 15
Dependent Claim
48 words
The apparatus of claim 12, wherein the terminals generate the sub-queries by: selecting a state of the automaton; defining the selected state as a root state of a sub-automaton; deleting all states and transitions prior to the selected state; and generating a sub-query that corresponds to the sub-automaton.
Claim 16
Dependent Claim
70 words
The apparatus of claim 12, wherein the terminals: decompose the distributed database into second portions, each of the second portions corresponding to one of the sub-queries; determine from which of the second portions each of the exiting paths exits; select a sub-query that corresponds to the second portions for each of the exiting paths; and applies selected sub-queries to respective entering paths that correspond to each of the exiting paths.
Claim 17
Dependent Claim
85 words
The apparatus of claim 14, wherein the terminals determine from which of the second portions each of the exiting paths exits by: determining whether each of the exiting paths may be traced to a root of the edge-labeled tree; identifying which of the second portions immediately precedes each of the exiting paths if each of the exiting paths is traceable to the root; and identifying all the second portions as corresponding to an exiting path if the exiting path is not traceable to the root.
Claim 18
Dependent Claim
48 words
The apparatus of claim 14, wherein the terminals decompose the distributed database by assigning to one of the second portions of the distributed database all the edges and nodes of the edge-labeled tree that may be traversed without transitioning out of one of the states of the automaton.
Claim 19
Dependent Claim
76 words
The apparatus of claim 14, wherein each of the terminals: transfers information regarding which of the second portions each of the exiting paths contained in each of the terminals exits to other terminals that are processing corresponding entering paths; selects sub-queries based on transferred results received from other terminals; applies only selected sub-queries to corresponding entering paths contained in each of the terminals; and applies all sub-queries to entering paths that have no corresponding selected sub-queries.
Claim 20
Dependent Claim
35 words
The apparatus of claim 17, wherein one of the terminals that contains the root of the edge-labeled tree begins transferring the information and then each of the terminals may transfer the information to other terminals.
References Cited (Backward Citations)
GB2172130A
Cited
EP0320266A2
Cited
US5519857A
Cited
US5418942A
Cited
US5564119A
Cited
US5442784A
Cited
US5495605A
Cited
US5606690A
Cited
US5590319A
Cited
US5574900A
Cited
US5600831A
Cited
US5524240A
Cited
US5598559A
Cited
US5600829A
Cited
US5694591A
Cited
US5864842A
Cited
US5701460A
Cited
US5873075A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |