## 1. Introduction
Programming systems in this way has multiple benefits. In writing or reading or modifying logic programs, programmers can get by with little or no knowledge of the capabilities and limitations of the systems executing those programs. As a result, logic programs are easier to produce than traditional programs; they are easier to understand; and they are easier to modify. Logic programs are more versatile than traditional programs - they can be used in multiple ways for multiple purposes without modification. And they are more amenable to programmatic analysis and optimization. Over the years, numerous variations of Logic Programming have been explored (e.g. Disjunctive Logic Programming, Constraint Logic Programming, Abductive Logic Programming, Inductive Logic Programming, and Answer Set Programming), and a variety of languages have been developed (e.g. Datalog and Prolog and Golog). In this paper, we focus on the most basic form of Logic Programming, called This paper is a brief introduction to Basic Logic Programming. In the first section, we talk about sentential databases, i.e. sets of simple facts. After that, we introduce basic logic programs, i.e. definitions of relations in terms of other relations, and we show how to combine datasets and view definitions to form deductive databases. Finally, we introduce transition rules and dynamic logic programs, and we show how they can be used to specify behavioral information. ## 2. Sentential DatabasesWhen we think about the world, we usually think in terms of objects and relationships among these objects. Objects include things like people and offices and buildings. Relationships include things like the parenthood, ancestry, office assignments, office locations, and so forth. In sentential databases, we encode each instance of a relationship in the form of a The A A As an example of these concepts, consider a small interpersonal database. The terms in this case represent people. The relation constants name properties of these people and their relationships with each other. In our example, we use the binary relation constant
The
We can express gender with two unary relation constants
As an example of a ternary relation, consider the data shown below. Here, we use
Note that the order of arguments in such sentences is important. Given the meaning of the ## 3. View DefinitionsThe language of logic programs includes the language of sentential databases but provides some additional features that make it more expressive. One key difference is the inclusion of a new type of symbol, called a An A A
Semantically, a rule is something like a reverse implication. It is a statement that the head of the rule is true whenever the subgoals are true. For example, the rule above states that The expressive power of rules is greatly enhanced through the use of variables. Consider, for example, the rule shown below. This is a more general version of the rule shown above. Instead of applying to just the specific objects
A The principal use of rules is to define new relations in terms of existing relations. The new relations defined in this way are often called To illustrate the use of rules in defining views, consider once again the world of interpersonal relations. Starting with the base relations, we can define various interesting view relations. As an example, consider the sentences shown below. The first sentence defines the
The rule below defines the grandparent relation in terms of the parent relation. A person
Note that the same relation can appear in the head of more than one rule. For example, the
A person
A childless person is one who has no children. We can define the property of being childless with the rules shown below. The first rule states that a person
Note the use of the helper relation In addition to writing definitions of common relations, rules are frequently used to write one-off queries on databases, including cases where the queries do not correspond to common relations. 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.
Another use of rules is encoding constraints on databases. Such constraints often limit the set of possible databases. For example, a person cannot be his or her own parent. In some cases, constraints involve multiple relations. For example, all parents are adults; in other words, if a person appears as the first argument of a 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 In what follows, we use a slightly less direct approach - we encode limitations by writing rules that say when a database is This approach works particularly well for consistency constraints like the one stating that a person cannot be his own parent. It also works well for Using this technique, we can also write the
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. Operation DefinitionsIn the preceding chapter, we saw how to write rules to define The syntax of operation definitions is analogous to the syntax for view definitions. The various types of constants are the same, and the notions of term and atom and literal are also the same. However, to these, we add a few new items. To denote operations, we designate some constants as An An
Intuitively, the meaning of an operation rule is simple. If the conditions of a rule are true in any state, then executing the action in the head requites that we execute the effects of the rule. For example, the following rule states that in any state in which
As with rules defining views, operation rules may contain variables to express information in a compact form. For example, we can write the following rule to generalize the preceding rule to all objects.
As with view rules, The operation rules shown above are both safe. However, the rules shown below are not. The second effect of the first rule contains a variable that does not appear in the head or in any positive condition. In the second rule, there is a variable that appears in a negative condition that does not appear in the head or in any positive condition.
In some operation rules there is no condition, i.e. the effects of the transition rule take place on all datasets. We can, of course, write such rules by using the condition
For the sake of simplicity in writing our examples, we sometimes abbreviate such rules by dropping the conditions and the transition operator and instead write just the effects of the transition as the body of the operation rule. For example, we can abbreviate the rule above as shown below.
An The semantics of operation definitions is similar to semantics of view definitions. In what follows, we first define the expansion of an action in the context of a given dataset, and we then define the result of performing that action on that dataset. Suppose we are given a set Ω of rules, a set Γ of actions (factoids, negated factoids, and actions), and a dataset Δ. We say that an Given this notion, we define the Next, we define the positive updates A(γ,Ω,Δ) to be the positive base factoids in U(γ,Ω,Δ). We define the negative updates D(γ,Ω,Δ) to be the set of all negative factoids in U(γ,Ω,Δ). Finally, we define the result of applying an action γ to a dataset Δ as the result of removing the negative updates from Δ and adding the positive updates, i.e. the result is (Δ - D(γ,Ω,Δ)) ∪ A(γ,Ω,Δ). To illustrate these definitions, consider an application with a dataset representing a directed acyclic graph. In the sentences below, we use symbols to designate the nodes of the graph, and we use the
The following operation definition defines a ternary operation
Given this operation definition and the dataset shown above, the expansion of
After executing this event, we end up with the following dataset.
The following rule defines a unary operation
The expansion of
After executing this event, we end up with the following dataset.
Finally, the following operation rules define a binary operation that inserts a new node into the graph (the first argument) with an arc to the second argument and arcs to all of the nodes that are reachable from the second argument.
The expansion of
Applying this event to the preceding dataset produces the result shown below.
Note that it is possible to define ## 5. ConclusionIn practice, it is common to extend the simple version of Dynamic Logic Programming described here to include "built-in" relations (e.g. arithmetic) and other operators (e.g. aggregates). The syntax and semantics of such extensions are a little messy. Luckily, they pose no significant theoretical challenges; and, in the interest of brevity, they are not covered here. The intent of this article is to provide a concise but reasonably rigorous account of the syntax and semantics of Dynamic Logic Programming. For motivation and examples of all of these concepts, see the textbook Dynamic Logic Programming. |