C H A P T E R  4
Open Logic Programs

4.1 Introduction

Logic programs as defined in the previous chapter are closed in that they fix the meaning of all relations in the program. In open logic programs, some of the relations (the inputs) are undefined, and other relations (the outputs) are defined in terms of these. The same program can be used with different input databases, yielding different output databases in each case.

One important use of open logic programs is in the area of deductive databases. A deductive database is a system consisting of an open logic program and a database. By applying the rules of the open logic program to the facts in the database, it is possible to infer additional facts, i.e. facts that are implicitly true but are not explicitly represented in the database itself.

We begin this chapter by showing how we can use open logic programs to define queries and integrity constraints in deductive databases. We then look at some of the properties of deductive databases.

4.2 Open Logic Programs

Logic programs as defined in the previous chapter are closed in that they fix the meaning of all relations in the program. In open logic programs, some of the relations (the inputs) are undefined, and other relations (the outputs) are defined in terms of these. The same program can be used with different input databases, yielding different output databases in each case.

Formally, an open logic program is a logic program together with a partition of the relation constants into two types - base relations (also called input relations) and view relations (also called output relations). View relations can appear anywhere in the program, but base relations can appear only in the subgoals of rules, not in their heads.

The input base for an open logic program is the set of all atoms that can be formed from the base relations of the program and the entities in the program's domain. An input model is an arbitrary subset of its input base.

The output base for an open logic program is the set of all atoms that can be formed from the view relations of the program and the entities in the program's domain. An output model is an arbitrary subset of its output base.

Given an open logic program P and an input model D, we define the overall model corresponding to D to be the minimal model of PD. The output model corresponding to D is the intersection of the overall model with the program's output base.

Finally, we define the meaning of an open logic program to be a function that maps each input model for the program into the corresponding output model.

As an example, consider the simple open logic program shown below. The universe of discourse is {a,b,c}, p and q are base relations; and r is a view relation.

r(X,Y) :- p(X,Y) & ~q(Y)

In this case, there are 212 input models, and for each there is a unique output model. The table below shows the output model for two of the possible input models.

Input ModelOutput Model
p(a,c)
q(b)
r(a,c)
p(a,c)
p(b,c)
r(a,c)
r(b,c)

4.3 Integrity Constraints

In our development thus far, we have assumed that the extension of an n-ary relation may be any set of n-tuples from the domain. This is rarely the case. Often, there are constraints that limit the set of possibilities. For example, a person cannot be his own parent. In some cases, constraints involve multiple relations. For example, all parents are adults; in other words, if an entity appears in the first column of the parent relation, it must also appear as an entry in the adult relation.

In many database texts, constraints are written in direct form - by writing rules that say, in effect, that if certain things are true in an extension, then other things must also be true. The inclusion dependency mentioned above is an example - if an entity appears in the first column of the parent relation, it must also appear as an entry in the adult relation.

In what follows, we use a slightly less direct approach - we encode limitations by writing rules that say when a database is not well-formed. We simply invent a new 0-ary relation, here called illegal, and define it to be true in any extension that does not satisfy our constraints.

This approach works particularly well for consistency constraints like the one stating that a person cannot be his own parent.

illegal :- parent(X,X)

It also works well for mutual exclusion constraints like the one below, which states that a person cannot be in both the male and the female relations.

illegal :- male(X) & female(X)

Using this technique, we can also write the inclusion dependency mentioned earlier. There is an error if an entity is in the first column of the parent relation and it does not occur in the adult relation.

illegal :- parent(X,Y) & ~adult(X)

Database management systems can use such constraints in a variety of ways. They can be used to optimize the processing of queries. They can also be used to check that updates do not lead to unacceptable extensions.

4.4 Queries

In practice, view definitions are usually stored in a deductive database for later use. However, another common use is to define one-shot queries on the database. Such

As a simple example, suppose we wanted to know all people who are grandparents of adults. We could ask this question by writing the query shown below.

query(Z) :- grandparent(art,Z) & adult(Z)

By including definitions for auxiliary temporary relations, we can also ask more complicate queries. For example, we might want to know all people who are parents of childless adults. We can ask this question by (1) defining a temporary relation isparent that is true of any person who has a parent and (2) adding this condition as a negative subgoal in the query.

query(X) :- parent(X,Y) & adult(Y) & ~isparent(Y)
isparent(Y) :- parent(Y,Z)

What makes these queries different from ordinary view definitions is that they are temporary - they last for the duration of a query and are then discarded. This avoids filling up the database with redundant information.

Exercises

Exercise 4.1: Consider a deductive database with a single binary base relation p. Without mentioning any specific object constants, write a set of constraints that is satisfied by a dataset if and only if the p is non-reflexive, i.e. the dataset does not contain any facts in which the same object constant appears in both the first and second position.

Exercise 4.2: Consider a deductive database with a single binary base relation p. Without mentioning any specific object constants, write a set of constraints that is satisfied by a dataset if and only if the p is antisymmetric, i.e. if there is a fact in the database with object constants in one order, then the database does not a fact with the object constants in the opposite order.

Exercise 4.3: Consider a deductive database with a single binary base relation p. Without mentioning any specific object constants, write a set of constraints that is satisfied by a dataset if and only if the p is symmetric, i.e. if there is a fact in the database with object constants in one order, then there is a fact with the object constants in the opposite order.

Exercise 4.4: Consider a deductive database with a single binary base relation p. Without mentioning any specific object constants, write a set of constraints that is satisfied by a dataset if and only if the p is transitive, i.e. whenever there is a fact in the database relating x and y and a fact relating y and z, then there is a fact relation x and z.

Exercise 4.5: Consider a deductive database with a single binary base relation p. Without mentioning any specific object constants, write a set of constraints that is satisfied by a dataset if and only if the p is acyclic, i.e. there is no sequence of pairs satisfying p that loops back on itself.