IDEA at Bonn:
Update Propagation
Update propagation is one of the key tasks a deductive database system
is expected to automatically perform. To propagate an update basically
means to determine all logical consequences which a physical update of
some explicitly stored (base) data induces on any derived data. A
single change of some base data may affect various deductive rules.
Induced updates themselves may in turn affect rules too, so that the
process of propagation constitutes a complex multi-stage inference
process.
Classically, there are at least two reasons why induced updates have to
be computed. On the one hand, certain derived data might be
permanently materialized in view of enhancing efficiency of query
evaluation. If so, each update affecting a materialized concept has to
be propagated by incrementally modifying the materialized data
according to the rule(s) involved. On the other hand, in presence of
integrity constraints, knowledge about the implicit, logical
consequences of a physical update have to be computed in order to be
able to check constraints involving derived concepts. There are other
less central, but nevertheless important and interesting motivations
for an update propagation facility. Materialization as well as
integrity checking can very conveniently be used as mechanisms for
implementing schema design and manipulation tools (e.g., in order to
check model-inherent constraints defining correct application
schemas).
Chimera's object-oriented data model and data manipulation language
introduce a couple of new and non-trivial problems with respect to
formulating and implementing update propagation methods. Among others
problems arise from
- the model-inherent assumptions which are implicit in the definitions
of deductive concepts,
- from additional data manipulation primitives (eg object migration)
not known in relational databases, and
- from the possibility to specify class hierarchies and to redefine
derived attributes.
Update propagation to be realized within the IDEA project makes use of
Chimera triggers. The motivation for doing so is twofold: on the one
hand, each propagation step can be very naturally interpreted as being
driven by an update to be propagated, and as causing the creation of a
follow-up modification of a rule-defined concept. The specific
conditions under which the propagation step is performed make up the
condition part of a trigger. On the other hand, using a
system-component which exists anyway - in this case a trigger
interpreter - for implementing other services of the database system is
likely to reduce size and complexity of the resulting overall system.
The proposed approach to update propagation has been practically
implemented as the Propagation Rule Compiler (PROP)
which is available for free download as well as our
publications on this topic.
[IDEA at Bonn]