Patent US5535385A successfully refreshed from Google Patents.
US5535385A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dealing with side effects of transactions in data base systems using a multi-set algebra
Assignee: AT&T Inc
•
Filing: 1995-05-19
•
Granted: 1996-07-09
•
Expires: 2015-05-19
Abstract
Abstract Apparatus and methods for reducing the amount of computation required to determine the consequences of a side effect resulting from a transaction on a relation in a data base system. The apparatus and methods use equational reasoning based on a bag algebra representation of a class of transaction and the relation to produce a pre-expression which describes the side effect. The pre-expression is included in the data base system's data dictionary, and when a transaction of the class is received in the data base system, the pre-expression is used to determine the side effect. The pre-expression is formed with a strongly-minimal pair of delete and insert bags. The apparatus and methods may be used to maintain materialized views, to check for violation of constraints on the data base, and to activate triggers, monitors, and active queries.
Inventors
- 👤 Timothy G. Griffin
- 👤 Leonid Libkin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:38
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/23; G06F16/2365; G06F16/24; G06F16/245; G06F16/2455; G06F16/24564; G06F16/24565; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
86 words
A method employed in a data base system of determining a side effect on the data base system of a transaction on a relation in the data base system, the method comprising the steps of: receiving a description of the transaction in terms of the relation; transforming the description in accordance with a set of change propagation equations which correctly deal with duplicates to produce a pre-expression which specifies the side effect; and responding to the transaction by producing the side effect specified in the pre-expression.
Claim 2
Independent Claim
86 words
A method employed in a data base system of determining a side effect on the data base system of a transaction on a relation in the data base system, the method comprising the steps of: receiving a description of the transaction in terms of the relation; transforming the description in accordance with a set of change propagation equations which correctly deal with duplicates to produce a pre-expression which specifies the side effect; and responding to the transaction by producing the side effect specified in the pre-expression.
Claim 3
Dependent Claim
24 words
The method set forth in claim 1 wherein: the description, the change propagation equations, and the pre-expression are all modellable in a bag algebra.
Claim 4
Dependent Claim
36 words
The method set forth in claim 2 wherein: the data base system employs a query language to describe relations and transactions; and the description, the change propagation equations, and the pre-expression are in the query language.
Claim 5
Dependent Claim
27 words
The method set forth in claim 1 wherein: the step of transforming includes the step of computing a delete bag and an insert bag in the pre-expression.
Claim 6
Dependent Claim
33 words
The method set forth in claim 4 wherein: the step of computing a delete bag and an insert bag computes the delete bag and the insert bag such that they are strongly minimal.
Claim 7
Dependent Claim
42 words
The method set forth in claim 1 wherein: the transaction description in the step of receiving a transaction description describes a class of transactions; and the transaction in the step of responding to the transaction description is an instance of the class.
Claim 8
Dependent Claim
32 words
The method set forth in claim 6 wherein: the steps of making the description and transforming the description are performed prior to the receipt of the instance in the data base system.
Claim 9
Dependent Claim
18 words
The method set forth in claim 1 wherein: the step of transforming is applied recursively to the description.
Claim 10
Independent Claim
28 words
The method set forth in any of claims 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect is an update of a materialized view.
Claim 11
Dependent Claim
34 words
The method set forth in claim 9 wherein: the step of transforming the definition produces a pre-expression which defines how the transaction updates the materialized view in terms of elements of the base relation.
Claim 12
Independent Claim
34 words
The method set forth in any of claims 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
Claim 13
Dependent Claim
18 words
The method set forth in claim 11 wherein: the side effect is produced prior to performing the transaction.
Claim 14
Independent Claim
29 words
The method set forth in any of claims 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect activates a trigger in the data base system.
Claim 15
Independent Claim
29 words
The method set forth in any of claims 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect activates a monitor in the data base system.
Claim 16
Independent Claim
30 words
The method set forth in any of claims 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect activates an active query in the data base system.
Claim 17
Independent Claim
97 words
A method employed in a data base system of determining a side effect on the data base system of a transaction on a relation in the data base system, the method comprising the steps of: receiving a description of the transaction in terms of the relation; transforming the definition in accordance with a set of change propagation equations which deal correctly with sets to produce a pre-expression which specifies the side effect in terms of a strongly minimal delete bag and insert bag; and responding to the transaction by producing the side effect specified in the pre-expression.
Claim 18
Independent Claim
97 words
A method employed in a data base system of determining a side effect on the data base system of a transaction on a relation in the data base system, the method comprising the steps of: receiving a description of the transaction in terms of the relation; transforming the definition in accordance with a set of change propagation equations which deal correctly with sets to produce a pre-expression which specifies the side effect in terms of a strongly minimal delete bag and insert bag; and responding to the transaction by producing the side effect specified in the pre-expression.
Claim 19
Dependent Claim
18 words
The method set forth in claim 16 wherein: the side effect is an update of a materialized view.
Claim 20
Dependent Claim
34 words
The method set forth in claim 17 wherein: the step of transforming the definition produces a pre-expression which defines how the transaction updates the materialized view in terms of elements of the base relation.
Claim 21
Dependent Claim
24 words
The method set forth in claim 16 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
Claim 22
Dependent Claim
18 words
The method set forth in claim 28 wherein: the side effect is produced prior to performing the transaction.
Claim 23
Dependent Claim
19 words
The method set forth in claim 16 wherein: the side effect activates a trigger in the data base system.
Claim 24
Dependent Claim
19 words
The method set forth in claim 16 wherein: the side effect activates a monitor in the data base system.
Claim 25
Dependent Claim
20 words
The method set forth in claim 16 wherein: the side effect activates an active query in the data base system.
Claim 26
Dependent Claim
137 words
An improved data base system, the data base system being of the type which includes at least one relation and a definition of the relation and which performs a transaction on the relation and the improvement comprising: a pre-expression in the data base which specifies a side effect of the transaction on the data base, the pre-expression having been produced by steps including receiving a description of a class of transactions to which the transaction belongs in terms of the relation and transforming the description in accordance with a set of change propagation equations which correctly deal with duplicates to produce a pre-expression which specifies the side effect for transactions belonging to the class; and means responsive to the transaction and the pre-expression for responding to the transaction by producing the side effect specified in the pre-expression.
Claim 27
Dependent Claim
137 words
An improved data base system, the data base system being of the type which includes at least one relation and a definition of the relation and which performs a transaction on the relation and the improvement comprising: a pre-expression in the data base which specifies a side effect of the transaction on the data base, the pre-expression having been produced by steps including receiving a description of a class of transactions to which the transaction belongs in terms of the relation and transforming the description in accordance with a set of change propagation equations which correctly deal with duplicates to produce a pre-expression which specifies the side effect for transactions belonging to the class; and means responsive to the transaction and the pre-expression for responding to the transaction by producing the side effect specified in the pre-expression.
Claim 28
Dependent Claim
29 words
The data base system set forth in claim 24 wherein: the step of transforming includes the step of computing a delete bag an an insert bag in the pre-expression.
Claim 29
Dependent Claim
35 words
The data base system set forth in claim 25 wherein: the step of computing a delete bag and an insert bag computes the delete bag and the insert bag such that they are strongly minimal.
Claim 30
Dependent Claim
25 words
The data base system set forth in any of claims 24, 25 or 26 wherein: the side effect is an update of a materialized view.
Claim 31
Dependent Claim
31 words
The data base system set forth in any of claims 24, 25 or 26 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
Claim 32
Dependent Claim
26 words
The data base system set forth in any of claims 24, 25 or 26 wherein: the side effect activates a trigger in the data base system.
Claim 33
Dependent Claim
26 words
The data base system set forth in any of claims 24, 25 or 26 wherein: the side effect activates a monitor in the data base system.
Claim 34
Dependent Claim
29 words
The data base system set forth in any of claims 18, 19, 24, 25 or 26 wherein: the side effect activates an active query in the data base system.
Claim 35
Dependent Claim
141 words
An improved data base system, the data base system being of the type which includes at least one relation and a definition of the relation and which performs a transaction on the relation and the improvement comprising: a pre-expression in the data base which specifies a side effect of the transaction on the data base, the pre-expression having been produced by steps including receiving a description of a class of transactions to which the transaction belongs in terms of the relation and transforming the definition in accordance with a set of change propagation equations which deal correctly with sets to produce a pre-expression which specifies the side effect in terms of a strongly minimal delete bag and insert bag; means responsive to the transaction and the pre-expression for responding to the transaction by producing the side effect specified in the pre-expression.
Claim 36
Dependent Claim
141 words
An improved data base system, the data base system being of the type which includes at least one relation and a definition of the relation and which performs a transaction on the relation and the improvement comprising: a pre-expression in the data base which specifies a side effect of the transaction on the data base, the pre-expression having been produced by steps including receiving a description of a class of transactions to which the transaction belongs in terms of the relation and transforming the definition in accordance with a set of change propagation equations which deal correctly with sets to produce a pre-expression which specifies the side effect in terms of a strongly minimal delete bag and insert bag; means responsive to the transaction and the pre-expression for responding to the transaction by producing the side effect specified in the pre-expression.
Claim 37
Dependent Claim
20 words
The data base system set forth in claim 325 wherein: the side effect is an update of a materialized view.
Claim 38
Dependent Claim
26 words
The data base system set forth in claim 32 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
Claim 39
Dependent Claim
21 words
The data base system set forth in claim 32 wherein: the side effect activates a trigger in the data base system.
Claim 40
Dependent Claim
21 words
The data base system set forth in claim 32 wherein: the side effect activates a monitor in the data base system.
Claim 41
Dependent Claim
22 words
The data base system set forth in claim 32 wherein: the side effect activates an active query in the data base system.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-09 | 2000-01-08 | 2000-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-09 | 2004-01-08 | 2004-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-09 | 2008-01-08 | 2008-07-09 | $7700.00 | Window Closed / Lapsed |