13.1 Introduction

In the preceding chapter, we looked at the process of updating datasets in response to inputs. In this chapter, we look at a special case of this more general process, one where the inputs are additions and deletions of specific facts.

In order to specify such inputs, we use two new operations, viz. add and delete. add takes a ground atom as argument and signifies a request that the specified atom be added to the current dataset. delete takes a ground atom as argument and signifies a request that the specified atom be deleted from the current dataset.

Note that a system may or may not act upon the requests it receives. It may also add or delete facts not specified in the input. Operation rules allow the programmer to specify exactly how the database should change in response to inputs.

In this chapter, we look first at the use of operation definitions to ensure that dataset constraints remain satisfied after updates. In the subsequent section, we look at the use of operation definitions to update materialized views. And then we look at the use of operation definitions to specify updates to base relations when given requests for updates to view relations.

13.2 Update With Constraints

Consider a database system with constraints, and suppose the database system receives an update request that, if executed literally, would lead to a dataset that violates the constraints.

One course of action in this situation is for the system to simply reject the request, possibly with an indication of the possible problems.

An alternative is for the system to repair the update set by augmenting it with additions and deletions in such a way that the resulting update set leads to a dataset that reflects the requested updates and satisfies all constraints.

The bad news is that there is no method of repair that is satisfactory in all applications. The good news is that, using operation definitions, an administrator can specify how to make repairs in such situations.

As an example of this mechanism in action, consider the rules shown below. The first directs the system to remove a sentence of the form male(X) whenever the user adds a sentence of the form female(X) (in addition to adding male(X)). The second rule is analogous to the first with male and female reversed. Together, these two rules enforce the mutual exclusion on male and female.

Similarly, we can enforce an "inclusion dependency" on parent and adult by writing the following rule. If the user requests the system to add a sentence of the form parent(X,Y), then the system also adds a sentence of the form adult(X).

Note that not all constraints can be enforced using update rules. For example, if a user suggests adding the sentence parent(art,art) to the database in our kinship example, there is nothing the system can do to repair this error; and, if it wants to maintain consistency, it must reject the update.

A separate problem arises when there are multiple possible repairs and none seems better than the others. For example, we might have a constraint saying that every person is either male or female. If the user specifies a person fact involving a new person but does not specify the gender of that person, there may be no way for the system to decide that gender for itself. In such cases, the system could reject the request; it could collect additional information; or it could make an arbitrary choice and allow the user to modify the dataset using additional updates.

13.3 Maintaining Materialized Views

A materialized view is a defined relation that is stored explicitly in the database. The benefit of materializing views is that a system can simply look up answers to questions about the materialized view rather than having to compute answers from other stored relations. The downside is that we need to keep such relations up-to-date as changes are made to the underlying base relations. Operation definitions can help here by enabling automatic updates to materialized views.

Suppose, for example, we had a database with parent and male as base relations; suppose we were to define father as a view of parent and male: and suppose we were to materialize the father relation. Then we could write update rules to maintain this materialized view. According to the first rule below, the system should add a sentence of the form father(X,Y) whenever the user adds parent(X,Y) and male(X) is known to be true. The other rules cover the other cases.

This approach works, but it can be a little tedious to write such update rules. Fortunately, there are some alternatives. (1) First of all, it is possible to build a program that differentiates view definitions and produces such operation definitions automatically. (2) Second, it is possible to build differential update processing of this sort directly into a system's update engine. In this second case, explicit operation definitions are unnecessary. However, they remain useful in explaining how the system processes update requests.

13.4 Update Through Views

In the preceding section, we discussed the process of updating views as a result of changes to the base relations in a dataset. In this section, we discuss the reverse of this process, viz. updating base relations when given changes to views of those relations. This process is often called update through views.

Updating views given changes to base relations is simple because there is a functional relationship between the views and the base relations in terms of which they are defined. The challenge in update through views is that there may be many extensions of the base relations that give rise to the same view extension. As a result, a change to a view relation can sometimes be accomplished in various ways, i.e. the update can be ambiguous.

As an example, consider a deductive database in which we are storing the p relation and the q relation, and suppose we are given the following definition of the r in terms of p and q.

Suppose now that the user asks us to add the fact r(a). How should we modify our dataset so that this conclusion holds? Should we add p(a) or q(a) or both?

Of course, a system could simply reject an update in the face of ambiguity. But in some cases the programmer might prefer that the system make a choice and leave it to the user to correct that choice if it is in error.

The beauty of operation definitions is that they allow the programmer to specify which of various possible base relation updates is appropriate given a change to an update to the view relations in a logic program.

As an example, in the case mentioned above, the programmer might choose to record p(a) (e.g. if there are far more p objects than q objects). In this case, he could specify this policy by writing the following operation definition.

Exercises

Exercise 13.1: Let us assume that the likes relation is symmetric, i.e. if one person likes another, then the second person likes the first. Define the add and delete operations to update the likes relation in a way that enforces the symmetry.

Exercise 13.2: Parenthood is an asymmetric relation. It is not possible for a person to be his own parent. Define the add operation in such a way that it enforces the asymmetry of parent when the user requests the addition of a parent fact.

Exercise 13.3: Assume that the q relation is defined as shown below. Define add and delete to update the r relation properly when a user requests the system to add or delete a p or q factoid.

Exercise 13.4: Assume that the t relation is defined as shown below. Define add and delete to update the t relation properly when a user requests the system to add or delete a p or q factoid.

Exercise 13.5: Given the view definition shown below, there are three general ways to update the p and q relations when given a request to add or delete an atom involving the r relation. Define add and delete for each of these possibilities.