Updating derived relations: detecting irrelevant and autonomously computable updates

• view update 2
• view 20

http://dl.acm.org/citation.cfm?id=68015

ABSTRACT. This paper gives sufficient and necessary conditions for detecting when an update of a base relation cannot affect a derived relation (an irrelevant update), and for detecting when a derived relation can be correctly updated using no data other than the derived relation itself and the given update operation (an autonomously computable update).

Testing the conditions eventually requires testing the satistiability of certain Boolean expressions, which, in general, is an NP-complete problem.

a database scheme D = (D, S)

consisting of a set of base relation schemes D = {R1, R2,…,Rm} and a set of derived relation definitions S = {E1,E2,…,En}

U

is posed against the database d on D specifying an update of base relation r, on R ∈ D.

Buneman and Clemons [8] proposed using views (that is, virtual derived relations) for the support of alerters. An alerter monitors the database and reports when a certain state (defined by the view associated with the alerter) has been reached. Hammer and Sarin [13] proposed a method for detecting violations of integrity constraints.

If the update is autonomously computable, then the derived relation can be correctly updated locally without requiring data from remote sites. … provide a starting point for devising a general mechanism for database snapshot refresh [1, 7, 15]

2. NOTATION AND BASIC ASSUMPTIONS

A derived relation v(Ei, d) is a relation instance resulting from the evaluation of a relational algebra expression Ei against the database d.

• a relational algebra expression constructed from any combination of project, select and join operations, called a PSJ-expression.
• very valid PSJ-expression without self- joins can be transformed into an equivalent expression in a standard form consisting of a Cartesian product, followed by a selection, followed by a projection.
• update operations considered

3. IRRELEVANT UPDATES

Definition 3.1. (The update operation U is irrelevant to E)

Let d be an instance on the set on relation schemes D, and let d’ be the resulting instance after applying the update operation U to d. Let E = (A, R, G) be a derived relation definition. The update operation U is irrelevant to E if v(E, d’) = v(E, d) for all instances d.

reference

• [8] BUNEMAN, 0. P., AND CLEMONS, E. K. Efficiently monitoring relational databases. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 368-382.
• [13] HAMMER, M., AND SARIN, S. K. Efficient monitoring of database assertions. In Supplement Proceedings ACM SZGMOD International Conference on Management of Data (Austin, Tex., 1978), 159.