US5999926A
Expired / Lapsed
US
⏱️ 0.0 years remaining
View maintenance for unstructured databases
Assignee: AT&T Inc
•
Filing: 1997-08-12
•
Granted: 1999-12-07
•
Expires: 2017-08-12
Abstract
Abstract A method and apparatus provides for efficient view maintenance of query of a database. The database is represented by an edge-labeled tree which is decomposed into a plurality of portions based on an automaton modeling an original query. When an addition to the database occurs, it is first determined which portion of the database the addition is made. Then an update query is performed on the added portion. The update query is determined by selecting a state corresponding to a portion as a root state and ignoring all previous states and transitions. The update query is applied to the portion of the database that the addition is made. The result of the update query is incorporated with the results of the query to produce an updated view.
Inventors
- 👤 Dan Suciu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 19:08
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99951; Y10S707/99952
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
111 words
A method for updating a view of a database that may be represented by an edge-labeled tree, comprising: applying an update query to an added part of the unstructured database; adding the results of the update query to the view to generate an updated view; decomposing the unstructured database into a plurality of unstructured database portions based on a query; decomposing the query into a plurality of update queries, each of the update queries corresponding to one of the unstructured database portions; identifying one of the database portions that contains the added part; and applying one of the update queries that corresponds to an identified database portion as the update query.
Claim 2
Independent Claim
111 words
A method for updating a view of a database that may be represented by an edge-labeled tree, comprising: applying an update query to an added part of the unstructured database; adding the results of the update query to the view to generate an updated view; decomposing the unstructured database into a plurality of unstructured database portions based on a query; decomposing the query into a plurality of update queries, each of the update queries corresponding to one of the unstructured database portions; identifying one of the database portions that contains the added part; and applying one of the update queries that corresponds to an identified database portion as the update query.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein each of the update queries corresponds to one of the unstructured database portions.
Claim 4
Dependent Claim
67 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; replacing the root state of the automaton with an update root state; and defining a plurality of update automatons corresponding to each state of the automaton, each of the update automatons corresponding to one of the update queries.
Claim 5
Dependent Claim
41 words
The method of claim 3, wherein the defining step comprises: selecting a state of the automaton; defining the selected state as a root state of one of the update automatons; and deleting all states and edges prior to the selected state.
Claim 6
Dependent Claim
19 words
The method of claim 3, wherein each of the plurality of update automatons models one of the update queries.
Claim 7
Dependent Claim
47 words
The method of claim 3, wherein the decomposing the unstructured database step comprises: modeling the query as an automaton having a plurality of states; and assigning all the edges and nodes of the edge-labeled tree that may be traversed without transitioning out of one of the states.
Claim 8
Dependent Claim
31 words
The method of claim 6, wherein one of the unstructured database portions and one of the update queries that correspond to a same state of the automaton correspond to each other.
Claim 9
Independent Claim
128 words
An apparatus that maintains a view generated by a query of an unstructured database, comprising: a memory that contains the unstructured database; and a controller coupled to the memory, wherein the controller applies an update query to an added part of the unstructured database and adds the result of the update query to the view to generate an updated view; decomposes the unstructured database into a plurality of unstructured database portions based on the query; decomposes the query into a plurality of update queries each of the update queries corresponding to one of the unstructured database portions; identifies one of the unstructured database portions that contains the added part; and applies one of the update queries that corresponds to an identified unstructured database portion as the update query.
Claim 10
Independent Claim
128 words
An apparatus that maintains a view generated by a query of an unstructured database, comprising: a memory that contains the unstructured database; and a controller coupled to the memory, wherein the controller applies an update query to an added part of the unstructured database and adds the result of the update query to the view to generate an updated view; decomposes the unstructured database into a plurality of unstructured database portions based on the query; decomposes the query into a plurality of update queries each of the update queries corresponding to one of the unstructured database portions; identifies one of the unstructured database portions that contains the added part; and applies one of the update queries that corresponds to an identified unstructured database portion as the update query.
Claim 11
Dependent Claim
19 words
The apparatus of claim 8, wherein each of the update queries corresponds to one of the unstructured database portions.
Claim 12
Dependent Claim
55 words
The apparatus of claim 8, wherein the controller decomposes the query by: modeling the query as an automaton having a plurality of states, the automaton having a root state; replacing the root state of the automaton with an update root state; and defining a plurality of update automatons corresponding to each state of the automaton.
Claim 13
Dependent Claim
46 words
The apparatus of claim 10, wherein the controller defines the plurality of update automatons by: selecting a state of the automaton; defining the selected state as a root state of one of the update automatons; and deleting all states and edges prior to the selected state.
Claim 14
Dependent Claim
19 words
The apparatus of claim 10, wherein each of the plurality of update automatons models one of the update queries.
Claim 15
Dependent Claim
47 words
The apparatus of claim 10, wherein the controller decomposes the unstructured database by: modeling the query as an automaton having a plurality of states; and assigning all the edges and nodes of the edge-labeled tree that may be traversed without transitioning out of one of the states.
Claim 16
Dependent Claim
31 words
The apparatus of claim 13, wherein one of the unstructured database portions and one of the update queries that correspond to a same state of the automaton correspond to each other.
References Cited (Backward Citations)
US5519857A
Cited
US5564119A
Cited
US5418942A
Cited
US5442784A
Cited
US5495605A
Cited
US5606690A
Cited
US5590319A
Cited
US5574900A
Cited
US5600831A
Cited
US5724567A
Cited
US5524240A
Cited
US5598559A
Cited
US5600829A
Cited
US5694591A
Cited
US5701460A
Cited
US5870760A
Cited
US5892843A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-06 | 2003-06-07 | 2003-12-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-06 | 2007-06-07 | 2007-12-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-06 | 2011-06-07 | 2011-12-07 | $7700.00 | Window Closed / Lapsed |