3 DEONTIC ACTION PROGRAMS

Thomas Eiter^{1} and V.S. Subrahmanian^{2}

1Institut und Ludwig Wittgenstein Labor f� ur Informationssysteme

Technische Universit� at Wien, Treitlstra�e 3, 1040 Wien

Austria

eiter@kr.tuwien.ac.at

2Institute for Advanced Computer Studies and Department of Computer Science

University of Maryland, College Park, Maryland 20742

U.S.A.

vs@cs.umd.edu

Abstract: We introduce the concept of an Action Policy in the context of databases. Intuitively, such a policy tells us which from a collection of actions must be executed (i.e. are obligatory), which are forbidden from being executed, and which are permitted (but not obligatory) given a state of the database. We approach this by a rule-based action language which uses concepts of deontic logic. We de�ne a semantics for programs in this language based on the concept of a status set, which intuitively describes a consistent global view of the actions. Moreover, we consider re�nements of status sets, and we investigate the complexity and computation of all these semantics.

3.1 INTRODUCTION

During the last several years, active databases have been studied extensively by researchers around the world. Following the lead provided by many successful implementations (Ceri and Widom, 1991; Ghandeharizadeh et al., 1993; Hanson, 1992; Dayal et al., 1995), formal semantics have recently been proposed for eventcondition-action (ECA) rules, cf. (Fraternali and Tanca, 1995; Gottlob et al., 1996; Picouet and Vianu, 1995; Zaniolo, 1993).

In this paper, we introduce the concept of an Action Policy. Intuitively, given a feasible space A of actions, and a database state DB, an action policy ℘ tells us which of the actions in A must be executed (i.e. are obligatory), which are forbidden from being executed, and which are permitted (but not obligatory). Given a feasible space A of actions, a database state DB, an action policy further speci�es a way of determining which actions to actually perform, based on the implied obligations and permissions. We will build our notion of an action policy on top of deontic logic (�Aquist, 1984; Meyer and Wieringa, 1993). It will turn out that the well known ECArules are a special case of our notion of an action policy, thus making our semantics applicable not only to existing ECA-rules, but also to the extended set of action policies proposed in this paper.

Before proceeding any further, let us consider a simple example to see why action policies are needed. Consider a tax agency (such as the Internal Revenue Service in the USA) that monitors tax returns. The database monitors discrepancies between the amounts reported by individual taxpayers, and amounts reported by all employers who have made payments to that person. An action policy might make the following statement:

1. If the amount reported by the individual is less than 70% of the employer-reported income, then triggering an audit program is obligatory.

2. if the amount reported by the individual is less than 80% of the employer-reported income, then triggering an audit program is permitted.

3. If the amount reported by the individual is over 80% then it is forbidden to run the audit program.

4. If a person makes over 200K (according to employer �led returns) and it is permitted to audit him/her, then do the audit program run.

5. If an audit run is done on a person, then an action that noti�es him/her to this effect must also be done.

Rules such as these (with different percentages) are often used to determine whom to audit, based on objective criteria that are legally defendable.^{1}

If one examines the �rst three rules, we note that the individuals who reported as income, only 70-80% of what employers said they earned, fall in a �gray� area � audits are permitted on them, but it is not clear what mechanism is used to select exactly whom to audit from this group of people. The fourth rule presents one such way of determining which of these people should be audited. We note (for deontic logic a�cionados) that the last two rules are not easily expressed in standard deontic logic.

In this paper, we will formally introduce the syntax of action policies (Section 3.2) by building upon a restricted version classical deontic logic, i.e. we will start with a fragment of deontic logic and extend it with non-deontic operators. We will then provide three alternative semantics for sets of action policies (Section 3.3). We will present results on the computational complexity of these different semantics (Section 3.4), as well as some results on the inter-relationships between them. We have developed algorithms to compute these semantics as well (Section 3.5). We will conclude with a brief discussion of related work in the area of active databases (Section 3.6).

3.2 SYNTAX

Throughout this section, we will assume the existence of a relational database DB of relations p_{1}, …, p_{n}. We also assume that DB has an accompanying query language QL which has a subclass of queries called boolean queries (of QL), together with a set IC of integrity constraints. Without loss of generality, we will assume that the initial state DB_{0} of the database is consistent with the integrity constraints (and of course, we must ensure that our semantics preserves this consistency when active rules �re). Figure 3.1 shows an example of instances of some of the relations associated with the tax example.

Figure 3.1 Relations from the tax database

return  employer report
SSN  Name RawInc AdjInc
91-762-8976 Smith 75000 58000
34-289-0127 Jones 16000 14000
…  …  …  …
…  …  …  …

EmpID  SSN  Inc
company1 91-762-8976 57000
company2 91-762-8976 17650
company1 34-289-0127 15800
…  …  …
audit  notified
SSN  Result  Date
98-283-2829 prosecute Nov. 5, 1997
83-211-9232  okay  Nov. 3, 1997
…  …  …

SSN  Date
98-283-2829 Nov. 9, 1997
83-211-9232 Nov. 9, 1997
…  …

De�nition 3.2.1 (action) An action α has the following components:

A name, α, and a list (X_{1}, …, X_{n}) of parameters X_{i} (treated as variables);

A schema, usually written as (τ_{1}, …, τ_{n}), of types. Intuitively, this says that the variable X_{i} must be of type τ_{i} for all 1 ≤ i ≤ n.

a boolean query q(t⃗) on DB called the precondition of the action, denoted by P re(α), where t⃗ is a vector of terms;

a set Add(α) = {A_{1}(t⃗_{1}), …, A_{n}(t⃗_{n})} of atoms to be inserted into DB; and,

a set Del(α) = {D_{1}(t⃗′_{1}), …, D(t⃗′_{m})} of atoms to be deleted from DB;

Here, A_{i}(t⃗_{i}) (resp., D_{i}(t⃗′_{i})) are possibly non-ground atoms, each of which is associated with a boolean query q_{A_{i}}(t⃗_{i}) (resp., q_{D_{i}}(t⃗′_{i})); informally, they represent the ground atoms A_{i}(t⃗_{i}θ) (resp., D_{i}(t⃗′_{i}θ)) such that q_{A_{i}}(t⃗_{i}θ) (resp., q_{D_{i}}(t⃗′_{i}θ)) is true on a database state DB.

The above de�nition states what an action is, but allows the possibility that an action allows an atom to be simultaneously added and deleted. Classical AI systems like STRIPS (Nilsson, 1980) also allow this to happen in the syntax (e.g. in a STRIPS rule, an atom could occur in both the Add and Delete lists) and handle potential problems of this sort by �rst doing deletions and then insertions. We mimic this as well. Table 3.1 shows some of the actions associated with the tax example:

Table 3.1 Some actions in the tax example

Action  run audit  notify
Name  run audit(Name,SSN)  notify(SSN)
Precondition  return(SSN,Name,Raw,Adj) &  audited(SSN,Res,Date)
S=sum(Inc,employer(E,SSN,Inc)) &  �

Adj < 0.7 × S

Add audit(SSN,Result,Date): noti�ed(SSN,Date):
Result = eval audit(SSN) &  Date = today()

Date = today()

Del  �  �

(Here, prede�ned function queries eval audit(SSN) and today() are available). As usual, a (ground) action α is executable in a database state DB iff pre(α)

evaluates to true in DB. We de�ne the result of executing such an α in state DB as the state DB′ = (DB \ Del(α, DB)) ∪ Add(α, DB), where Add(α, DB) = {A(t⃗γ) | A(t⃗) ∈ Add(α), DB ⊧ q_{A}(t⃗γ)} and Del(α, DB) = {D(t⃗γ) | D(t⃗) ∈ Del(α), DB ⊧ q_{D}(t⃗γ)} are the sets of ground instances of atoms in Add(α) (resp., Del(α)) over DB such that the associated query q_{A} (resp., q_{D}) is true on DB.

We next describe a natural de�nition for the execution of a collection of ground actions on DB.

De�nition 3.2.2 (concurrent execution) Let AS = {α_{1}, …, α_{n}} be a set of ground actions, and DB a state such that α_{i} is executable in DB, i = 1, …, n. Then AS is concurrently executable, iff (i) every sequential execution AS[π] = α_{π(1)}, …, α_{π(n)} on DB is feasible, i.e., α_{π(i)} is executable on DB_{i−1}^{π}, where DB_{0}^{π} = DB and DB_{i}^{π} results from executing α_{π(i)} on DB_{i−1}^{π}, i = 1, …, n, and (ii) DB_{n}^{π} = DB_{n}^{π′} for every permutations π and π′ on {1, …, n}.

Unfortunately, this notion is intractable, even in a very simple setting.

Theorem 1 Let AS be a set of ground actions and DB a database state, and suppose that QL contains conjunctive queries on DB. Then, deciding whether AS is concurrently executable is co-NP-hard.

A dual result (NP-hardness) holds for choosing any feasible AS[π] for execution, as deciding the existence of such an AS[π] is NP-hard. In (Eiter et al., 1998) we use an alternative polynomial-time concurrent execution model: The execution of a nonground action α(X⃗) in DB is de�ned as the simultaneous execution of all ground instances α′ of α which are executable on DB.

De�nition 3.2.3 (action base & status atom) An action base, AB, is any �nite collection of actions. Suppose α(t⃗) is an action atom, i.e., an action name with a vector t⃗ of terms (variables or domain elements) matching the type schema of α. Then, the formulas P(α(t⃗)), F(α(t⃗)), O(α(t⃗)), and Do(α(t⃗)) are action status atoms.

For convenience, we sometimes omit parentheses and write Pα, Fα instead of P(α), P(α) etc. An action status atom has the following intuitive meaning:

Pα means that action α is permitted;

Fα means that action α is forbidden;

Oα means that action α is obligatory; and,

Doα means that action α is in fact executed.

De�nition 3.2.4 (action rules & programs) A rule is a clause r of the form

A ← L_{1}, …, L_{n}  (3.1)

where A is an action status atom, and every L_{i} is either action status atom Op(t⃗), possibly preceded by a negation sign (¬), or a � possibly negated � Boolean query q(t⃗_{i}) from QL, where t⃗_{i} is a vector of terms. An action program P is a �nite collection of rules. An action program P is positive, if all its rules are positive.

The rules speci�ed in the tax example may now be easily encoded through the following rules. We use the predicate tot rep inc(SSN,Inc) as a view on top of the base relation, employer report. tot rep inc(SSN,Inc) speci�es the total income that a particular individual has received based on all tuples pertaining to him in the employer report relation.

Orun audit(Name, SSN) ← return(SSN, Name, RInc, AInc),
tot rep inc(SSN, Inc), AInc ≤ 0.7 × Inc.
Prun audit(Name, SSN) ← return(SSN, Name, RInc, AInc),
tot rep inc(SSN, Inc), AInc ≤ 0.8 × Inc.
Frun audit(Name, SSN) ← return(SSN, Name, RInc, AInc),
tot rep inc(SSN, Inc), AInc > 0.8 × Inc.
Dorun audit(Name, SSN) ← Prun audit(Name, SSN),
tot rep inc(SSN, Inc), Inc > 200K.
Donotify(SSN) ← Dorun audit(Name, SSN).

3.3 SEMANTICS

In what follows, we assume the existence of an action base AB and a set of integrity constraints IC, all associated with an underlying database DB.

For de�ning the semantics of action programs, we �rst introduce the concept of a feasible status set. Feasible status sets provide the basic structure in terms of which we de�ne our semantics.

De�nition 3.3.1 A status set is any set S of ground action status atoms over DB. For any action status operator Op, we denote Op(S) = {α | Op(α) ∈ S}.

Informally, if some atom Op(α) occurs in S, then this means that the status Op is true for α.

De�nition 3.3.2 (deontic consistency) A status set S is called deontically consistent, if it satis�es the following rules for any ground action α: (1) Pα ∈ S ⇒ Fα ∉ S, (2) Pα ∈ S ⇒ α is executable in state DB, and (3) Fα ∈ S ⇒ Pα ∉ S.

De�nition 3.3.3 (deontic and action closure) Let S be a status set. The deontic (resp., action) closure of S, denoted DCl(S) (resp., ACl(S)), is the closure of S under the rule Oα ⇒ Pα (resp., the rules Oα ⇒ Doα, Doα ⇒ Pα), where α is any ground action.

De�nition 3.3.4 (feasible status set) A status set S is a feasible status set for P on database state DB, if the following conditions S1�S4 hold:

S1 Let r : A ← L_{1}, …, L_{n} be any ground instance of some rule in P. Suppose the following conditions 1.�4. hold:

1. If L_{i} is a positive status atom Op(α), then Op(α) ∈ S;

2. if L_{i}, A is a positive status atom P(α), O(α), or Do(α), then α is executable in DB;

3. If L_{i} is a negated status atom ¬Op(α), then Op(α) ∉ S;

4. For every non-status literal L_{i}, DB ⊧ L_{i}, i.e., the (possibly negated) query represented by L_{i} is true on DB.

Then, the atom A is in S. For later reference, denote by App_{P,DB}(S) the set of all such A, for all ground rules r.

S2 S is deontically consistent;

S3 S is deontically and action closed, i.e., S = DCl(S) and S = ACl(S);

S4 DB′ ⊧ IC, where DB′ = apply(Do(S), DB) is the state which results by executing the actions in Do(S) on DB (cf. above).

In general, there are action programs that have zero, one or several feasible status sets. This is shown by the following example.

Example 3.3.1 Consider the relation emp below, together with the sets of rules P_{1}, P_{2}, P_{3}:

P_{1}:  Osend notice(P) ← emp(P, Salary), Salary ≥ 80K.
Psend notice(P) ← emp(P, Salary), 70K ≤ Salary < 80K.
Fsend notice(P) ← emp(P, Salary), Salary < 70K.
P_{2}:  Osend notice(P) ← emp(P, Salary), Salary ≥ 80K.
Fsend notice(P) ← emp(P, Salary), Salary < 80K.
P_{3}:  Dosend notice(P) ← ¬Psend notice(P), emp(P, Salary).
F(send notice(Dina)) ←

emp

Name Salary
Harry 76K
Mary 90K
Ted  34K
Ken 44K
Dina 65K

It is easy to see that P_{1} has (among others) the following two feasible status sets:

F SS_{1} = { Osend notice(Mary), Dosend notice(Mary),
Psend notice(Mary), Fsend notice(Ken),

Fsend notice(T ed), Fsend notice(Dina), Psend notice(Harry) }

F SS_{2} = { Osend notice(Mary), Dosend notice(Mary),
Psend notice(Mary), Fsend notice(Ken),
Fsend notice(T ed), Fsend notice(Dina),
Psend notice(Harry), Dosend notice(Harry)}.

On the other hand, P_{2} has the following feasible status set:

F SS_{3} = { Osend notice(Mary), Dosend notice(Mary),
Psend notice(Mary), Fsend notice(Ken),

Fsend notice(T ed), Fsend notice(Dina), Fsend notice(Harry)}.

P_{3} can be easily seen to have no feasible status set.

3.3.1 Rational status sets

Intuitively, a feasible status set describes a set of status atoms that are compatible with the state of the database, the obligations and restrictions imposed by its associated action program, and the deontic consistency requirements. Nevertheless, we note from the previous example that feasible status sets may include Doing actions that are not strictly necessary (F SS_{2}). The notion of a rational status set is based on the principle that each action which is executed should be suf�ciently �grounded� or �justi�ed� by the action program. That is, there should be evidence from the rules of the action program that a certain action must be executed. For example, it seems unacceptable that an action α is executed, if α does not occur in any rule of the action program. This way, we also have to make sure that execution of an action must not be driven by the need to preserve the consistency of the database state. Rather, the integrity constraints should serve to prevent executions which appear to be rational if no integrity constraints were present. This motivates the following formal notion of groundedness.

De�nition 3.3.5 (rational status set) Let S be a feasible status set S for P on DB. S is grounded, if there exists no status set S′ ≠ S such that S′ ⊆ S and S′ satis�es conditions S1�S3 of a feasible status set for P on DB. S is a rational status set of P on DB, if (i) S is a feasible status set of P on DB, and (ii) S is grounded.

Returning to the previous example, we note that the feasible status set F SS_{2} is not rational.

Proposition 3.3.1 Let P be an action program.

1. If P is positive, then P has for any DB a unique rational status set (if one exists on DB).

2. If IC = ∅, then P (positive or not) has a rational status set on DB iff P has a feasible status set on DB.

In the previous example, F SS_{1} and F SS_{3} are the unique rational status sets of P_{1} and P_{2}, respectively. Notice that an apparently �contradictory� program may have feasible and rational status sets; e.g., the two rules

Osend notice(P) ← emp(P, Salary), Salary ≥ 80K.
Fsend notice(P) ← emp(P, Salary), Salary < 90K.

are contradictory; however, w.r.t. the previous relation emp, they have a feasible and a rational status set (even if we adopt the functional dependency Name → Salary on emp in IC).

3.3.2 Reasonable status sets

A more serious attack against rational status sets, is that for action programs with negation, the semantics of rational status sets allows logical contraposition of the program rules. For example, consider the following program:

Do(α) ← ¬Do(β)

This program has two rational status sets: S_{1} = {Do(α), Pα}, and S_{2} = {Do(β), Pβ}. The second rational status set is obtained by applying the contrapositive of the rule:

Do(β) ← ¬Do(α)

However, the second rational set seems less intuitive than the �rst as there is no explicit rule in the above program that justi�es the derivation of this Do(β).

This observation leads us to the following remarks. First, in logic programming, deductive databases, and knowledge representation, the meaning of negation in rules has been extensively discussed and there is broad consensus that contraposition should not be applied as a proof principle; rather, derivation should be constructive from rules. These observations led to the well known stable model semantics for logic programs (Gelfond and Lifschitz, 1988).

Second, the presence of derivation by contraposition may have a detrimental effect on the complexity of programs, since it inherently simulates disjunction. Therefore, it is advisable to have a mechanism which cuts down rational status sets in an acceptable way, so that negation can be largely used without introducing high computational cost.

For these reasons, we introduce the concept of a reasonable status set.

De�nition 3.3.6 (reasonable status set) Let P be an action program, let DB be a database state, and let S be status set on DB. If P is a positive action program, then S is a reasonable status set for P on DB, iff S is a rational status set for P on DB.

For an arbitrary program P, let the reduct of P w.r.t. S and DB, denoted by red^{S}(P, DB), be the program obtained from the ground instance of P over DB as follows.

1. Remove every rule A ← …, ¬Op(α), … where Op(α) ∈ S, for any status atom Op(α);

2. Remove all negated status action atoms ¬Op(α) from the remaining rules.

Then, S is a reasonable status set for P on DB, iff it is a reasonable status set of red^{S}(P, DB) on DB.

Example 3.3.2 For the program P: Do(β) ← ¬Do(α), the reduct of P w.r.t. S = {Do(β), P(β)} is P: Do(β) ← . Clearly, S is a reasonable status set of P, and hence S is a reasonable status set of P.

The following result tells us that reasonable status sets are always rational (but the converse may not be true). Thus, reasonable status sets prune the rational status sets.

Proposition 3.3.2 Let P be an action program and DB a database state. Then, every reasonable status set of P on DB is a rational status set of P on DB.

3.4 COMPLEXITY RESULTS

In this section, we address the computational cost of action programs. We assume that the reader is familiar with the basic concepts of complexity theory, cf. (Johnson, 1990; Papadimitriou, 1994).

We consider here data complexity of action programs in the sense of (Vardi, 1982), i.e., evaluation of a �xed action program P over varying instances DB of a relational database DB; we assume that AB and IC are �xed, and that the associated Boolean query language QL has polynomial data complexity and IC contains �rst-order constraints. We adopt an active domain assumption: all objects considered for grounding the program rules, evaluation of the action preconditions, the conditions of the actions constraints and the integrity constraints must be from DB. Under this assumption, the size of the ground instance of P over DB is polynomial in the size of DB, and the evaluation of integrity constraints is polynomial (as is the evaluation of preconditions and action constraints). Moreover, a set of ground actions AS is executable on DB in polynomial time.

Our results on the computational complexity of action programs are summarized in Tables 3.2 and 3.3 below. The hardness results for arbitrary IC hold for the case where IC contains only functional dependencies. The problems considered are:

(consistency) deciding the existence of an acceptable status set on a state DB;

(recognition) the recognition of an acceptable status set on DB;

(computation) the computation of an arbitrary acceptable status set on DB; and

(action reasoning) reasoning about whether the system executes an action α on DB, for

the possibility variant (α is executed in some acceptable status set), and

the certainty variant (α is executed in every acceptable status set).

Table 3.2 Complexity of �xed positive action programs

action reasoning

\frac{IC = ∅}{IC arbitrary}

consistency computation recognition possible certain

feasible  \frac{P}{NP}  \frac{FP}{FNP}  P  \frac{P}{NP}  \frac{P}{co-NP}
rational  P  FP  P  P  P
reasonable  P  FP  P  P  P

Table 3.3 Complexity of �xed action programs with negation

action reasoning

\frac{IC = ∅}{IC arbitrary}

consistency computation recognition possible certain

feasible  NP  FNP  P  NP  co-NP
rational  \frac{NP}{Σ_{2}^{P}}  \frac{* FNP// log}{FΣP 2}  co-NP  Σ_{2}^{P}  \frac{co-NP}{Π_{2}^{P}}
reasonable  NP  FNP  P  NP  co-NP

F -preferred ; rational

\frac{NP}{Σ_{2}^{P}}
\frac{FNP// log}{^{†} RP · FP_{∥}^{Σ_{2}^{P}}}

\frac{co-NP}{Π_{2}^{P}}

\frac{Σ_{2}^{P}}{Σ_{3}^{P}}

\frac{Π_{2}^{P}}{Π_{3}^{P}}

F -preferred semantics selects those rational status sets S such that F(S) is minimal w.r.t. inclusion.

The entries for decision problems are well-known classes from the polynomial hierarchy (PH). For NP, co-NP, Σ_{k}^{P}, and Π_{k}^{P} they denote completeness. For P, we have completeness (under log space reductions) in general, depending on QL; since datalog has P-complete data complexity (Vardi, 1982), it can be seen that Pcompleteness holds for arbitrary (reasonable) QL except for recognition of feasible status sets.

The entries for the computation problem are the classes FC and FNP// log (= FNP//OptP[O(log n)]) according to (Papadimitriou, 1994; Chen and Toda, 1993) (i.e., compute any solution for an instance of a search problem). The entries FNP, FΣ_{2}^{P}, and FNP// log stand for completeness under appropriate polynomial-time reductions as used in (Papadimitriou, 1994; Chen and Toda, 1993), while FNP// log marked with ’*’ stands for membership in FNP// log and lower bounds of FP_{∥}^{NP} and FNP. (FP_{∥}^{NP} contains the problems solvable in polynomial time with parallel access to an NP oracle).

The class FNP (resp., FΣ_{2}^{P}) contains the problems for which each solution can be generated nondeterministically in polynomial time, such that a given candidate for a solution can be checked in polynomial time (resp., the check is in co-NP). The class is contained in the class NPMV (resp., NPMV^{NP}), which contains all multi-valued functions computable in nondeterministic polynomial time (resp., in nondeterministic polynomial time with an NP oracle) (Fenner et al., 1997).

The class FNP// log (Chen and Toda, 1993) contains informally those search problems for which a solution can be nondeterministically found in polynomial time for instance I, if the optimal value opt(I) of an NP optimization problem on I is known, where opt(I) is a number which must have O(log |I|) bits; for example, computing a maximum clique in a graph is a typical problem in FNP// log. It holds that with respect to problem solving power, FP^{NP} is (presumably) more powerful than FNP// log, which is (presumably) more powerful than FP_{∥}^{NP} cf. (Chen and Toda, 1993). (Observe that FNP// log, like FNP, expresses problem solving in the presence of multiple solutions (i.e., multivalued functions), while FP_{∥}^{NP} and FP^{NP} express problems with a single solution (i.e., single-valued functions). Thus, formally FP_{∥}^{NP} ⊂ FNP// log and FNP// log ⊈ FP^{NP} holds. RP · FP_{∥}^{Σ_{2}^{P}} is a randomized

version of FP_{∥}^{Σ_{2}^{P}}; the symbol ’^{†}’ denotes hardness for FP_{∥}^{Σ_{2}^{P}} and FΣ_{2}^{P}.

For space reasons, a detailed treatment and derivation of all these results is beyond the scope of this paper. Some of the results, in particular for the polynomial cases in Table 3.2, follow from the results of the next section. These and the other results are also obtained from the detailed analysis of the respective problems in the slightly more general framework described in (Eiter et al., 1998). Here, we con�ne to describe the intuition behind the results.

Brie�y, the complexity of feasible status sets intuitively explained by analogy to models of a propositional formula. A feasible status set can be veri�ed in polynomial time, but an exponential number of candidates for a feasible status set S exists. A positive program without integrity constraints has a least feasible status set, if it is consistent. For a rational status set, on a positive program only a single candidate S needs to be checked, which is polynomial time computable (see next section). Moreover, rational and reasonable status sets coincide on positive programs.

On general programs, the complexity of rational status sets can be intuitively explained by a rough analogy to minimal models of a propositional formula, where the groundedness condition corresponds to minimality. For IC = ∅, this analogy is proper, while for arbitrary IC, it no longer applies: here, a feasible status set does not necessarily include a rational status set. Thus, while existence of a feasible status set implies the existence of a rational status set S if IC = ∅ (which yields NP), for arbitrary IC, we can guess and verify S in polynomial time with an NP oracle, and there seems to be no more ef�cient algorithm in general.

Reasonable status sets are in analogy to stable models of a logic program (Gelfond and Lifschitz, 1988); observe that their complexity is immune to integrity constraints. For a suitable concept of strati�cation, their complexity is polynomial for all problems.

F -preferred rational status sets roughly correspond to a selection from the minimal models of a propositional formula, if minimization is restricted to part of the variables, and the remaining variables may �oat to support minimization; thus, they correspond to a particular instance of the so called P; Z-minimal models of a formula (Lifschitz, 1985).

The high complexity of action reasoning using F -preferred status sets can be intuitively explained as follows. There are three sources of complexity, which act in a way orthogonally on each other:

1. The (possibly exponential) number of candidates S for a feasible status sets;

2. the test whether S is grounded; and,

3. the (possibly exponential) number of candidates S′ which are F -preferred over S.

For the reasonable status sets, only one of the above sources is present, namely (1) (we do not consider F -preferred reasonable status sets here). The intuitive reason is that the refutation of a reasonable status sets reduces to the computation of the rational status set of a positive action program, and there integrity constraints do not affect complexity.

3.5 ALGORITHMS

It is possible to characterize the unique rational status set of a positive program in terms of a �xpoint operator. Given any positive action program P and a database state DB, de�ne the operator T_{P,DB} which maps status sets to status sets as follows:

T_{P,DB}(S) = App_{P,DB}(S) ∪ DCl(S) ∪ ACl(S).  (cf. Def. 3.3.4,3.3.3)

It is easy to see that T_{P,DB} is a monotonic and continuous operator (Lloyd, 1987) on a complete lattice, and thus it has a least �xpoint lfp(T_{P,DB}) given by lfp(T_{P,DB}) = ⋃_{i≥0} T_{P,DB}^{i} where T_{P,DB}^{0} = ∅ and T_{P,DB}^{i+1} = T_{P,DB}(T_{P,DB}^{i}), for all i ≥ 0. We then have the following result.

Theorem 2 Let P be a positive action program. Then, for any DB, lfp(T_{P,DB}) is the unique rational status set of T_{P,DB} on DB iff lfp(T_{P,DB}) is a feasible status set.

The following algorithm computes a rational status set for positive action programs.

Algorithm Compute-P-RSS Input: database state DB (�xed positive action program P); Output: the (unique) rational status set of P, if a rational status set exists; �No�,

otherwise.

Step 1. Compute S = lfp(T_{P,DB});

Step 2. Check whether S satis�es conditions S2 and S4 of a feasible status set;

Step 3. If S satis�es S2 and S4, then output S; otherwise, output �No�. Halt

By Theorem 2 and the fact that S satis�es S1 and S3, algorithm Compute-P-RSS correctly computes the unique rational status set of P on DB. Step 1 is polynomial, since the ground instance of �xed P is polynomial in DB, and we can compute S = lfp(T_{P,DB}) bottom up by �xpoint iteration. Step 2, is, by our assumptions, possible in polynomial time. Therefore, for �xed P, algorithm Compute-Pos-Rational-SS runs in polynomial time.

Observe that if IC = ∅, then P has a feasible status set on DB if and only if lfp(T_{P,DB}) is a feasible status set. Therefore, deciding the existence of a feasible status set (and computing one) is polynomial if IC = ∅.

In the absence of integrity constraints, the rational status sets coincide with the ⊆-minimal feasible status sets. Using an NP oracle, we can thus compute a rational status set as follows.

Algorithm Compute-Rational-SS Input: database state DB (�xed action program P, IC = ∅); Output: a rational status set of P, if one exists; �No�, otherwise.

Step 1. Set S := ∅ and At := set of all ground action status atoms.

Step 2. Check if S is a feasible status set; if true, then output S and halt.

Step 3. If At = ∅, then output �No� and halt.

Step 4. Choose some atom A ∈ At and query the oracle whether a feasible status set S′ exists such that S ⊆ S′ ⊆ S ∪ (At \ {A}); If the answer is �no�, then S := S ∪ {A};

Step 5. set At := At \ {A} and continue at Step 2.

Clearly, Compute-Rational-SS runs in polynomial time modulo calls to the oracle. Hence, the problem is in FP^{NP}. This upper bound can be improved to FNP// log; indeed, if the size s of a smallest feasible status set S is known, then such an S (which is a rational status set) can be nondeterministically computed in polynomial time. Since computation of s is an NP-optimization problem with O(log |I|) output bits, it follows that computing a rational status set is in FNP// log if IC = ∅. In fact, it is polynomially equivalent to computing a (global) ⊆-maximal model of a CNF formula, which is in FNP// log and known to be FP_{∥}^{NP}-hard (Chen and Toda, 1993).

3.6 CONCLUSIONS

During the last few years, there has been an explosion in the amount of data accessible to database users. The sheer quantity of such data makes it very dif�cult for users to constantly monitor the content of the database. Active databases monitor conditions on databases and take actions as speci�ed by the active rules de�ned by the application developer. Early work on active databases focused on building scalable implementations, e.g. the Starburst system of IBM (Ceri and Widom, 1991) and the Ariel system (Hanson, 1992).

More recently, there has been a trend towards developing a formal semantics for active databases. (Zaniolo, 1993) suggested the use of Datalog-1S for this purpose. (Fraternali and Tanca, 1995) also proposed a semantics for ECA rules. The expressive power of implemented active database systems has been analyzed in (Picouet and Vianu, 1995), where computations over time are considered. If we consider evaluation of action programs over time, then over a �xed active domain, all computations in PSPACE are feasible, while if new values can be suitably created, all computations are possible. (Baral and Lobo, 1996) use situation semantics (a more general version of Datalog-1S) to give a logic program semantics for active rules. (Gottlob et al., 1996) proposed a semantics for active rules which allowed the user to specify different con�ict resolution policies. (Lud� ascher et al., 1997) develop methods to handle actions so as to preserve referential integrity constraints.

However, in many applications (e.g. the tax application, and various legal applications), the database administrators have certain legal obligations (that is, they are required to take certain actions), as well as certain restrictions (that is, they are forbidden to take certain actions) if certain conditions are true. However, not all actions are either forbidden or obligatory. The vast majority of actions fall within a �gray� area � they are permitted, but neither obligatory or forbidden. To date, no active database system has provided a formal semantics for obligatory, permitted, and forbidden actions. In this paper, we have done so, building on top of classical deontic logic syntax (�Aquist, 1984; Meyer and Wieringa, 1993).

Elements of deontic logic have been repeatedly used in the context of computer security to build a formal system for expressing security and authorization policies. Examples are the approach by (Glasgow et al., 1989) and the security logic proposed in (Bieber and Cuppens, 1993), where further work on this subject is reviewed. The quoted approaches basically propose logics of knowledge in a modal language, which are extended by an operator P ϕ which expresses permission to know ϕ; in (Bieber and Cuppens, 1993), the operator is indexed by time, and also the deontic operators O and F are available. The systems allow arbitrarily nested formulas, and suitable axioms for a formal system (including the security axiom Kϕ → P ϕ) as well as Kripke style semantics are investigated. Thus, these approaches are in the tradition of standard modal logic, and in they aim at providing abstract frameworks for expressing different security policies on information access (viewed as knowledge) and reasoning about statements in these logics. Our system is concerned with singling out actions for execution, a rather different task.

We have added to deontic logic as well in two ways: �rst, we have introduced the Do operator which standard deontic logic does not contain. Second, our semantics is completely new � to our knowledge, the concepts of feasible, rational and reasonable status sets are novel and new. Last, but not least, our framework also allows nonmonotonic inference through the negation operator in rule bodies.

Acknowledgments

We gratefully acknowledge the support of the Army Research Of�ce under Grants DAAH-04-95-10174, DAAH-04-96-10297, and DAAH04-96-1-0398, of the Army Research Laboratory under contract number DAAL01-97-K0135, of an NSF Young Investigator award IRI-93-57756, and of a DAAD grant.

The main part of this work has been carried out while the �rst author was with the Institute of Informatics, University of Gie�en, Germany.

Appendix:

This appendix provides sketches for the proofs of some results. Proofs of all result are contained in (Eiter et al., 1998).

Theorem 1 Let AS be a set of ground actions and DB a database state, and suppose that QL contains conjunctive queries on DB. Then, deciding whether AS is concurrently executable is co-NP-hard.

Proof. (Sketch) To show that the problem is co-NP-hard, we reduce the problem M3UNSAT, the complement of M3SAT (Garey and Johnson, 1979), to concurrent executability checking. Let I be an instance of M3UNSAT, consisting of positive clauses P_{1}, …, P_{n_{p}} and negative clauses N_{1}, …, N_{n_{n}}, n_{p}, n_{n} ≥ 1 over atoms a_{1}, …, a_{n}. Here, each clause is supposed to have three (not necessarily distinct) literals.

Let I′ be the instance of I which results if every positive clause is made negative and vice versa, and if every atom a_{i} is replaced by a_{n+i}. Clearly, I′ is a Yes-instance of M3UNSAT if and only if I is a Yes-instance, if and only if I ∪ I′ is not satis�ed by some truth assignment to a_{1}, …, a_{2n} in which a_{i} has opposite value to the value of a_{n+i}, for every i = 1, …, n.

The relational database DB we construct has four relations, namely

POS(V_{1}, V_{2}, V_{3}), NEG(V_{1}, V_{2}, V_{3}), which serve for storing the positive and negative clauses of I ∪ I′, respectively;

VAL(V ar, BV), which stores a truth value assignment to the variables, s.t. variable a_{i} is true if (a_{i}, 1) ∈ VAL, and a_{i} is false if (a_{i}, 0) ∈ VAL, for every i = 1, …, 2n;

a 0-ary relation (propositional letter) UNSAT.

The initial database DB contains the relations POS and NEG storing the clauses of I ∪ I′, the relation VAL which holds the tuples (a_{i}, 0) and (a_{n+i}, 1), for every i = 1, …, n, and the relation UNSAT is empty.

The action base contains the actions switch(X, Y) and eval, where

P re(switch(X, Y)) = true,

Add(switch(X, Y)) = { VAL(X, 1), VAL(Y, 0)}, and

Del(switch(X, Y)) = {VAL(X, 0), VAL(Y, 1)};

P re(eval) = { POS(V_{1}, V_{2}, V_{3})∧VAL(V_{1}, 0)∧VAL(V_{2}, 0)∧VAL(V_{3}, 0)∧

NEG(V′_{1}, V′_{2}, V′_{3})∧VAL(V′_{1}, 1)∧VAL(V′_{2}, 1)∧VAL(V′_{3}, 1) },

Add(eval) = { UNSAT }, Del(eval) = ∅.

(The free variables in P re(eval) are existentially quanti�ed.) Observe that we assume tacitly that the action base is �xed; otherwise, already the evaluation of varying conjunctive queries is intractable.

The action set is AS = {switch(a_{i}, a_{n+i}) | 1 ≤ i ≤ n} ∪ {eval}.

Intuitively, an action switch(a_{i}, a_{n+i}) �ips the value of a_{i} from 0 to 1 and the value of a_{n+i} from 1 to 0. The eval action checks whether for the truth assignment to a_{1}, …, a_{2n} given in VAL, there is some positive clause and some negative clause which are both violated.

Clearly, all actions in AS are executable on DB, and it is easy to see that every feasible AS[π] yields the same result DB′. It can be shown that AS is concurrently executable, if and only if I is a Yes-Instance of M3UNSAT.

Proposition 3.3.2 Let P be an action program and DB a database state. Then, every reasonable status set of P on DB is a rational status set of P on DB.

Proof. (Sketch) To show that a reasonable status set S of P is a rational status of P, we have to verify that S is a feasible status set and that S is grounded.

Since S is a reasonable status set of P, it is a rational status set of P′ = red^{S}(P, DB), i.e., a feasible and grounded status set of P′. As the conditions (S2)�(S4) of the de�nition of feasible status set depend only on S and DB but not on the program, for showing that S is feasible it remains to check (S1) (closure under the program rules).

Let thus r be a ground instance of a rule from P. Suppose the body of r satis�es the conditions 1.�4. of (S1). Then, by the de�nition of red^{S}(P, DB), the reduct of the rule r obtained by removing all negative status literals is in P′. Since S is closed under the rules of P′, the head of r is in S. Thus, S is closed under the rules of P, which means (S1) is satis�ed. It follows that S is feasible status set.

Assuming that S is not grounded, i.e., some smaller S′ ⊂ S satis�es (S1)�(S3) for P, a contradiction can be derived. If S′ satis�es (S1) for P, then S′ satis�es (S1) for P′. For, if r is a rule from P′ such that 1.�4. of (S1) hold, then there is a ground rule r′ of P such that r is obtained from r′ in the construction of red^{S}(P, DB) and, as easily seen, 1.�4. of (S1) hold. Since S′ satis�es (S1) for P, the head of r is in S′. It follows that S′ satis�es (S1) for P′. Since conditions (S2) and (S3) are independent of the program, they are satis�ed for S′ w.r.t. P′. This means that S is not a rational status set of P′, which is the desired contradiction.

Theorem 2 Let P be a positive action program. Then, for any DB, lfp(T_{P,DB}) is the unique rational status set of T_{P,DB} on DB iff lfp(T_{P,DB}) is a feasible status set.

Proof. (Sketch) From the de�nition of the operator T_{P,DB}, one can show by induction on the stages i of the operator that each feasible status S must include T_{P,DB}^{i}, i ≥ 0, and hence S must include lfp(T_{P,DB}).

As lfp(T_{P,DB}) is a �xpoint of T_{P,DB}, it satis�es the conditions (S1)�(S3) of a feasible status set. Thus, from the de�nitions of groundedness and rational status set it follows that the only candidate for a rational status set of P on DB is lfp(T_{P,DB}) itself. This set is rational iff it is a feasible status set, i.e., lfp(T_{P,DB}) also satis�es (S4) besides (S1)�(S3).

Notes

1. Deontic concepts were used in McCarty’s classic TAXMAN system (McCarty, 1977) for corporate tax law. The purpose of this system, whose foundations have been extended in (McCarty, 1983), was checking whether a corporate reorganization can be classi�ed as a tax-free transaction, cf. (Meyer and Wieringa, 1993).

References

�Aquist, L. (1984). Deontic Logic. In Gabbay, D. and Guenthner, F., editors, Handbook of Philosophical Logic, Vol.II, chapter II.11, pages 605�714. D. Reidel Publishing Company.

Baral, C. and Lobo, J. (1996). Formal Characterization of Active Databases. In Pedreschi, D. and Zaniolo, C., editors, Workshop of Logic on Databases (LID ’96), volume 1154 of Lecture Notes in Computer Science, pages 175�195, San Miniato, Italy.

Bieber, P. and Cuppens, F. (1993). Expression of Con�dentiality Policies. In (Meyer

and Wieringa, 1993), chapter 5, pages 103�123. Ceri, S. and Widom, J. (1991). Deriving Production Rules for Incremental View Main-

tenance. In Proceedings VLDB-91, pages 577�589. Chen, Z.-Z. and Toda, S. (1993). The Complexity of Selecting Maximal Solutions.

In Proceedings of the 8th IEEE Structure in Complexity Theory Conference, pages 313�325.

Dayal, U., Hanson, E., and Widom, J. (1995). Active Database Systems. In Kim, W.,

editor, Modern Database Systems, pages 434�456. Addison Wesley. Eiter, T., Subrahmanian, V., and Pick, G. (1998). Heterogenous Active Agents. Tech-

nical Report UMCP-CSD CS-TR-3880, Computer Science Department, University of Maryland, College Park, Maryland. iii + 114 pp. Also IFIG-RR 9802, University of Gie�en.

Fenner, S., Homer, S., Ogihara, M., and Selman, A. (1997). Oracles That Compute

Values. SIAM Journal on Computing, 26(4):1043�1065. Fraternali, P. and Tanca, L. (1995). A Structured Approach for the De�nition of the

Semantics of Active Databases. ACM Trans. on Database Syst., 20(4):414�471. Garey, M. and Johnson, D. S. (1979). Computers and Intractability � A Guide to the

Theory of NP-Completeness. W. H. Freeman, New York. Gelfond, M. and Lifschitz, V. (1988). The Stable Model Semantics for Logic Program-

ming. In Logic Programming: Proceedings Fifth Intl Conference and Symposium, pages 1070�1080, Cambridge, Mass. MIT Press.

Ghandeharizadeh, S., Hull, R., and Jacobs, et al, D. (1993). On Implementing a Language for Specifying Active Database Execution Models. In Proceedings VLDB-93, pages 441�454.

Glasgow, J., MacEwen, G., and Panangaden, P. (1989). Security by Permission in Databases. In Landwehr, C., editor, Database Security II: Status and Prospects, pages 197�205, Results of the IFIP WG 1.3 Workshop on Database Security (1988), Ontario, Canada. North Holland.

Gottlob, G., Moerkotte, G., and Subrahmanian, V. (1996). The PARK Semantics for Active Rules. In Proceedings Int’l Conf. on Extending Database Technology (EDBT ’96), pages 35�55.

Hanson, E. (1992). Rule Condition Testing and Action Execution in Ariel. In Proceed-

ings ACM SIGMOD ’92, pages 49�58. Johnson, D. S. (1990). A Catalog of Complexity Classes. In van Leeuwen, J., editor,

Handbook of Theoretical Computer Science, volume A, chapter 2. Elsevier Science Publishers B.V. (North-Holland).

Lifschitz, V. (1985). Computing Circumscription. In Proceedings International Joint

Conference on Arti�cial Intelligence (JCAI-85), pages 121�127. Lloyd, J. (1984, 1987). Foundations of Logic Programming. Springer, Berlin. Lud� ascher, B., May, W., and Lausen, G. (1997). Actions as Logical Rules. In Proceed-

ings PODS-97, pages 217�277. McCarty, T. (1977). Re�ections on TAXMAN: An Experiment in Arti�cial Intelligence

and Legal Reasoning. Harvard Law Review, 90:837�893. McCarty, T. (1983). Permissions and Obligations. In Proceedings IJCAI ’83, pages

287�294. Meyer, J.-J. C. and Wieringa, R., editors (1993). Deontic Logic in Computer Science.

Wiley & Sons, Chichester et al. Nilsson, N. (1980). Principles of Arti�cial Intelligence. Morgan Kaufmann. Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley. Picouet, P. and Vianu, V. (1995). Semantics and Expressiveness Issues in Active

Databases. In Proceedings PODS-95, pages 126�138. Vardi, M. (1982). Complexity of Relational Query Languages. In Proceedings 14th

STOC, pages 137�146, San Francisco. Zaniolo, C. (1993). On the Uni�cation of Active Databases and Deductive Databases.

In Advances in Databases: Proceedings 11th British National Conference on Databases (BNCOD 93), number 696 in LNCS, pages 23�39. Springer.