鵝
歷
☌
←
→
⇡
24 Nov 2015

Local ambiguity and derived data update

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=282850&tag=1

A novel execution model for rule application in ac- tive databases is developed and applied to the problem of updating derived data in the context of semantic, object-based database models. The execu-tion model is based on the use of “limited ambiguity rules” (LARs), which permit disjunction in rule actions. The execution model essentially performs a breadth-first exploration of alternative extensions of a user-proposed update, and returns all “completions” of that update, where a “completion” is defined to be an extension of a user-proposed update that satisfies a family of natural conditions (e.g., that no constraints are violated). Given a semantic, object-based database model schema, integrity constraints as well asspecifications of derived classes and attributes are compiled into a family of LARS. A formal proof of the correctness of the system is described here.

Active databases are an emerging technology permitting the specification of database behavior in a largely declarative fashion [4, 16, 18].

We develop here a new paradigm for active databases that permits “locally ambiguous rules” (LARS), i.e., rules with disjunction in their actions.

The novel execution model … provides for the automated exploration of alternative extensions for user-proposed updates. This short paper describes an application of the LAR paradigm to the problem of supporting updates to derived data as arises in semantic database models [11, 12]

forward propagation of updates
In the traditional approach to modification, base data is updated explicitly by users, which may in turn cause updates to the derived data;
Calls for automatic backwards propagation of updates.

2 Motivating Example and Discussion

For example, suppose that the user proposes the update Δuser=

Application of this delta yields a database state that violates integrity constraints and derivation specifications; for this reason we view Δuser incompletely specified.

Using the simplistic example just given, we are now able to summarize the contributions of the research described here:

  1. the specification of a novel execution model for active databases, that permits locally ambiguous rules, and constructs a dag corresponding to alternative partial extensions of a user-proposed update;
  2. the specification of a mechanism for compiling GSDM schemas (including both derivation specifications and constraints into rule bases consisting of locally ambiguous rules;

4 Correct Update Propagation

This section presents the definition of “completion”, that captures an intuitively natural notion of “correct” propagation of a user-requested update.

A delta Δ is consistent if it satisfies all of the following
(a) Each insert or delete is type-correct.
(b) There is no pair +(x,y,z) and -(x,y,z) in Δ. (i.e., Δ cannot request that the same triplet be inserted and deleted.)
(c) There is no error or blockage triplet in Δ.

A consistent delta Δ is valid for DB if apply(DB, Δ) is a state, i.e., if it satisfies the derivation specifications and (explicit and implicit) constraints of S.

A user update is simply a delta. An extension of a user update Δuser, is a delta Δ such that Δuser ⊂ Δ.

A crucial issue is: what extensions of a user update are “appropriate” or “permissible”.

A completion of a user update Δuser is a consistent and valid extension of Δuser that satisfies an additional technical condition, called the Principle of Down-Up Propagation.

A completion Δ of Δuser for DB is minimal if
there is no completion Δ’ of Δuser for DB such that Δ’ ⊂ Δ and Δ’≠ Δ.
a correct propagation of a user update Δuser
is a minimal completion of Δuser.

Execution Model for LAR application
illustrated in Figure (above)…Execution of the system will lead to the construction of a rooted directed acyclic graph, called the Execution DAG, where each node is labeled by a delta that extends Δuser.The algorithm is essentially a straightforward construction of the Execution DAG, as dictated by the rules of R and their ordering.
If there is only one minimal completion, the execution concludes by outputting this completion and applying it. Otherwise, the execution reports ambiguity, inconsistency, or that it was unable to make a determination. In the case of ambiguity, the system allows the user to choose between the different minimal completions found.
A note on complexity
…
Active databases[4, 16, 18]
Speaking loosely, the work here extends the execution models of [4].
Compilation into active database rules [4, 19]
These and other works advocate the development of compilers to construct rule bases that capture schema properties.

reference