US5978790A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for restructuring data in semi-structured databases
Assignee: AT&T Inc
•
Filing: 1997-05-28
•
Granted: 1999-11-02
•
Expires: 2017-05-28
Abstract
Abstract An apparatus and method for restructuring a database modeled by an edge-labeled tree. Portions of an output tree is generated by matching patterns of tree elements of a starting tree. Portions of the output tree are combined to form a complete output tree which may be restructured again until a final output tree presents a desired "view" of the starting database. If the pattern matches used in restructuring the starting tree is restricted to attributes of tree elements that only includes preceding edge information, successive tree restructuring may be composed into a single restructuring process that optimizes the restructuring by taking advantage of restructuring results of each of the original restructuring processes.
Inventors
- 👤 Peter Buneman
- 👤 Susan B. Davidson
- 👤 Dan Suciu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:35
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/21; G06F16/211; G06F16/212; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
85 words
A method of processing an unstructured database that is structured by an edge-labeled tree forming a semi-structured database, comprising: modeling the semi-structured database as a first edge-labeled tree; selecting at least a first portion of the first edge-labeled tree based on at least one pattern of at least one tree element of the first edge-labeled tree; generating at least one portion of a second edge-labeled tree; and constructing the second edge-labeled tree based on the generated at least one portion of the second edge-labeled tree.
Claim 2
Independent Claim
85 words
A method of processing an unstructured database that is structured by an edge-labeled tree forming a semi-structured database, comprising: modeling the semi-structured database as a first edge-labeled tree; selecting at least a first portion of the first edge-labeled tree based on at least one pattern of at least one tree element of the first edge-labeled tree; generating at least one portion of a second edge-labeled tree; and constructing the second edge-labeled tree based on the generated at least one portion of the second edge-labeled tree.
Claim 3
Dependent Claim
25 words
The method of claim 1, wherein the tree element of the first edge-labeled tree includes an attribute of an edge of the first edge-labeled tree.
Claim 4
Dependent Claim
56 words
The method of claim 2, wherein the attribute includes at least one of an edge-label, a type of the edge-label, an edge-label of an edge that precedes the edge, an edge-label of an edge that follows the edge, a marker of an edge, and a marker of an edge that either precedes or follows the edge.
Claim 5
Dependent Claim
12 words
The method of claim 3, wherein the edge is an empty edge.
Claim 6
Dependent Claim
56 words
The method of claim 1, further comprising matching a specified pattern of at least one tree element with the at least one tree element of the first edge-labeled tree, wherein the second edge-labeled tree generated by the matching step remains the same independent of an order that the matching step proceeds through the first edge-labeled tree.
Claim 7
Dependent Claim
24 words
The method of claim 5, wherein the matching step proceeds in either a recursive order or a parallel order through the first edge-labeled tree.
Claim 8
Dependent Claim
68 words
The method of claim 1, wherein the generating step comprises: selecting a second portion of the first edge-labeled tree, the second portion being identified by the pattern of the at least one tree element of the first edge-labeled tree; and combining the second portion of the first edge-labeled tree with at least one specified tree element to form the at least one portion of the second edge-labeled tree.
Claim 9
Dependent Claim
25 words
The method of claim 7, wherein the at least one specified tree element includes at least a modified tree element of the first edge-labeled tree.
Claim 10
Dependent Claim
28 words
The method of claim 7, wherein the at least one specified tree element includes at least one of an edge having a specified edge-label, markers, and a subtree.
Claim 11
Dependent Claim
46 words
The method of claim 9, wherein the markers label a beginning and ending of edges of a plurality of subtrees that are generated by the generating step, the combining step connecting edges of the subtrees by matching a same marker of corresponding edges of the subtrees.
Claim 12
Dependent Claim
22 words
The method of claim 10, wherein subtrees that are unreachable from a root node of the second edge-labeled tree are not processed.
Claim 13
Dependent Claim
41 words
The method of claim 7, wherein a plurality of portions of the second edge-labeled tree are formed by the combining step, the plurality of portions of the second edge-labeled tree are combined by an union to construct the second edge-labeled tree.
Claim 14
Dependent Claim
82 words
The method of claim 1, further comprising constructing a third edge-labeled tree starting with the second edge-labeled tree, wherein the third edge-labeled tree is constructed by: selecting at least a portion of the second edge-labeled tree based on at least one pattern of at least one tree element of the second edge-labeled tree; generating at least one portion of the third edge-labeled tree; and constructing the third edge-labeled tree based on the generated at least one portion of the third edge-labeled tree.
Claim 15
Dependent Claim
35 words
The method of claim 13, wherein the third edge-labeled tree is constructed starting with the first edge-labeled tree by composing the selecting, generating and constructing steps for constructing the second and the third edge-labeled trees.
Claim 16
Dependent Claim
69 words
The method of claim 14, wherein composing is performed by: eliminating non-reachable portions of the third edge-labeled tree before processing the first edge-labeled tree; generating at least one portion of the third edge-labeled tree based on anticipated results of both generating steps for constructing the second and the third trees; and constructing the third edge-labeled tree based on the generated at least one portion of the third edge-labeled tree.
Claim 17
Dependent Claim
117 words
A database processing device processing an unstructured database using an edge-labeled tree forming a semi-structured database, comprising: a memory containing a first semi-structured database ordered into a first edge-labeled tree; an expression processor; and a controller coupled to the memory and the expression processor, wherein the expression processor generates a second semi-structured database ordered as a second edge-labeled tree by: selecting at least a first portion of the first edge-labeled tree based on at least one pattern of at least one tree element of the first edge-labeled tree; generating at least one portion of a second edge-labeled tree; and constructing the second edge-labeled tree based on the generated at least one portion of the second edge-labeled tree.
Claim 18
Dependent Claim
117 words
A database processing device processing an unstructured database using an edge-labeled tree forming a semi-structured database, comprising: a memory containing a first semi-structured database ordered into a first edge-labeled tree; an expression processor; and a controller coupled to the memory and the expression processor, wherein the expression processor generates a second semi-structured database ordered as a second edge-labeled tree by: selecting at least a first portion of the first edge-labeled tree based on at least one pattern of at least one tree element of the first edge-labeled tree; generating at least one portion of a second edge-labeled tree; and constructing the second edge-labeled tree based on the generated at least one portion of the second edge-labeled tree.
Claim 19
Dependent Claim
25 words
The device of claim 16, wherein the tree element of the first edge-labeled tree is an attribute of an edge of the first edge-labeled tree.
Claim 20
Dependent Claim
56 words
The device of claim 17, wherein the attribute includes at least one of an edge-label, a type of the edge-label, an edge-label of an edge that precedes the edge, an edge-label of an edge that follows the edge, a marker of an edge, and a marker of an edge that either precedes or follows the edge.
Claim 21
Dependent Claim
12 words
The device of claim 18, wherein the edge is an empty edge.
Claim 22
Dependent Claim
56 words
The device of claim 16, wherein the expression processor matches a specified pattern of at least one tree element with at least one tree element of the first edge-labeled tree, the second edge-labeled tree generated by the expression processor remaining the same independent of an order that the matching step proceeds through the first edge-labeled tree.
Claim 23
Dependent Claim
24 words
The device of claim 20, wherein the expression processor proceeds in either a recursive order or a parallel order through the first edge-labeled tree.
Claim 24
Dependent Claim
69 words
The device of claim 16, wherein the expression processor selects a second portion of the first edge-labeled tree, the second portion being identified by the pattern of the at least one tree element of the first edge-labeled tree, the expression processor combining the second portion of the first edge-labeled tree with at least one specified tree element to form the at least one portion of the second edge-labeled tree.
Claim 25
Dependent Claim
25 words
The device of claim 22, wherein the at least one specified tree element includes at least a modified tree element of the first edge-labeled tree.
Claim 26
Dependent Claim
28 words
The device of claim 22, wherein the at least one specified tree element includes at least one of an edge having a specified edge-label, markers, and a subtree.
Claim 27
Dependent Claim
46 words
The device of claim 24, wherein the markers label a beginning and ending of edges of a plurality of subtrees that are generated by the expression processor, the expression processor connecting edges of the subtrees by matching a same marker of corresponding edges of the subtrees.
Claim 28
Dependent Claim
26 words
The device of claim 25, wherein subtrees that are unreachable from a root node of the second edge-labeled tree are not processed by the expression processor.
Claim 29
Dependent Claim
29 words
The device of claim 22, wherein the expression processor combines a plurality of portions of the second edge-labeled tree by a union operation to construct the second edge-labeled tree.
Claim 30
Dependent Claim
86 words
The device of claim 16, wherein the expression processor constructs a third edge-labeled tree starting with the second edge-labeled tree, wherein the expression processor constructs the third edge-labeled tree by: selecting at least a portion of the second edge-labeled tree based on at least one pattern of at least one tree element of the second edge-labeled tree; generating at least one portion of the third edge-labeled tree; and constructing the third edge-labeled tree based on the generated at least one portion of the third edge-labeled tree.
Claim 31
Dependent Claim
18 words
The device of claim 28, wherein the expression processor constructs the third edge-labeled tree by a composing process.
Claim 32
Dependent Claim
70 words
The method of claim 29, wherein the expression processor composes by: eliminating non-reachable portions of the third edge-labeled tree before processing the first edge-labeled tree; generating at least one portion of the third edge-labeled tree based on anticipated results of both generating steps for constructing the second and the third trees; and constructing the third edge-labeled tree based on the generated at least one portion of the third edge-labeled tree.
References Cited (Backward Citations)
US5151697A
Cited
US5379419A
Cited
US5581756A
Cited
US5555403A
Cited
US5644740A
Cited
US5721904A
Cited
US5625815A
Cited
US5740421A
Cited
US5812134A
Cited
US5737591A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |