A Tractable Class of Disjunctive Deductive Databases ^{∗}

Zahidul A. Khandaker^{1}  José A. Fernández^{1}  Jack Minker^{1,2}

1Department of Computer Science and 2 Institute for Advanced Computer Studies University of Maryland at College Park College Park, MD 20742

October 27, 1992

Abstract

In general, computing answers to queries in disjunctive deductive databases is CoNP-complete and therefore computationally infeasible. However, there are some tractable classes of disjunctive databases. In this paper, we present polynomial time algorithms to compute answers to queries in one such tractable class of disjunctive databases where at most two atoms are allowed in any disjunction.

∗We greatly appreciate the financial support of the National Science Foundation, provided under the grant Nr. IRI-89-16059, and the Air Force Office of Scientific Research, provided under the grant Nr. AFOSR-91-0350, that made this work possible.

1 Introduction

Disjunctive deductive databases are an outgrowth of work performed in the field of disjunctive logic programming where non-Horn clauses are allowed in the program [GM92]. The declarative, fixpoint and procedural semantics for disjunctive logic programs have been presented in [LMR92] which can be carried over to disjunctive deductive databases to solve many of the semantic issues for such databases.

Answering queries in disjunctive deductive databases has been studied by a number of researchers. Grant and Minker [GM86] were among the first to develope algorithms to answer conjunctive queries in disjunctive databases where there are no rules. Yahya and Henschen [YH85] developed a deductive method to determine whether a conjunction of ground atoms is entailed by the disjunctive database or not. Henschen and Park [HP88] presented a method to answer yes/no queries where the rules may be recursive. Liu and Sunderraman [LS91] generalized the relational model and introduced M-tables to represent disjunctive data. They extended the relational algebra operators to apply on M-tables to compute answers to queries. Their extended algebra is sound, but not complete. Yuan and Chiang [YC89] defined an extended algebra and developed a sound and complete query evaluation algorithm for disjunctive databases. Demolombe [Dem89] extended the concepts of magic sets to disjunctive databases. Fernandez and Minker [FM91] introduced a data structure called model trees to store the database and developed algorithms for bottom-up evaluation of rules and computation of answers.

All these methods to compute answers in disjunctive databases are in general bound to take exponential time since it has been demonstrated that even in deductive databases with only disjunctive facts and no rules, there are simple conjunctive queries with CoNP-complete complexity [IV89] [Imi91]. Although these results indicate that evaluation of rules and general queries in disjunctive deductive databases is computationally infeasible, a natural question arises is whether there are classes of disjunctive databases where queries can be computed in polynomial time or whether there are classes of queries that can be computed in polynomial time given some syntactic information about the database.

A number of researchers have investigated the complexity issues in disjunctive deductive databases. In [Var86] Vardi considers the complexity of query processing in databases with incomplete information. In [IV89] Imielinsky and Vadaparty give syntactic characterization of CoNP-complete conjunctive queries for a class of disjunctive databases called OR-databases. They give a polynomial time algorithm to compute conjunctive queries that are tractable. However, they consider only definite answers. In [LYW92] Lobo, Yu and Wang show that the computation of sets of pairs in the transitive closure of an acyclic relation with a disjunctive description is polynomial. In [Dal92] Dalal defines a parameter called cryptness and uses the measure of cryptness to identify classes of programs that can be queried in polynomial time. However, the algorithms do not provide a practical method for query evaluation; they can be used only as theoretical tools to study complexity of queries.

In this paper, we present algorithms for a tractable class of databases that we call 2-disjunctive databases. We represent the database as a graph and prove a correspondence between answers to queries in the database and paths in the graph with a particular structure. The algorithm computes the paths in polynomial time and derives answers to the query from these paths. The paper is organized as follows. In section 2 we provide some basic notions in disjunctive deductive databases, and discuss previous complexity results. In section 3 we introduce D-graphs and Q-graphs as a way of representing 2-disjunctive deductive databases, define Q-paths in the Q-graphs and show some properties of these graphs. In section 4, we present a polynomial time algorithm to evaluate 2-join queries by computing paths in the Q-graph. In section 6, we classify some classes of rules as tractable in a 2-disjunctive database and present algorithms to evaluate such rules. In the last section, we summarize the results of this paper and discuss directions for fututre research.

2 Background

2.1 Disjunctive deductive databases

A disjunctive deductive database is one in which indefinite information is allowed in the form of disjunctions. Deductive databases are based on function-free first-order logic programs in which only Horn-clauses are allowed. Disjunctive deductive databases are based on function-free disjunctive logic programs in which non-Horn clauses are also allowed. Formally, disjunctive deductive databases are defined as follows:

Definition 1 ([FM91]) Let DB be a function-free disjunctive logic program, and let E_{DB} and I_{DB} be a finite set of extensional and intensional rules, respectively. DB is called a disjunctive deductive database iff

1. E_{DB} = {C ∈ DB | c = (a_{1} ∨ … ∨ a_{n}) ∧ C is ground }

2. I_{DB} = {C ∈ DB | c = (a_{1} ∨ … ∨ a_{n} ← b_{1}, …, b_{m}) ∧ C is range-restricted }

3. DB = E_{DB} ∪ I_{DB}

where the a_{i} and b_{j} are atoms.

A clause is said to be range-restricted when all variables that occur in the head of the clause also occur in its body.

Example 1 The union of the following two sets of clauses yields a disjunctive deductive database:

E_{DB} = father(pat, john) ∨ mother(pat, john).
mother(ruth, pat).
I_{DB} = parent(X, Y) ← mother(X, Y).
parent(X, Y) ← father(X, Y).

The semantics of a disjunctive deductive database DB is defined by a set of minimal Herbrand models of DB. If we denote by M_{DB} the set of minimal models defining the semantics of a database DB, then a positive clause C is a logical consequence of DB if and only if ∀M ∈ M_{DB}, M ⊧ C.

This characterization of the semantics using M_{DB} is called model theoretic. A second way to characterize the semantics of a disjunctive database is by defining M_{DB} as the fixpoint of a monotonic immediate consequence operator. We refer to [LMR92] for such a fixpoint semantics for disjunctive databases.

A query in a deductive database consists of a conjunction of atoms A_{1}, …, A_{n} where n ≥ 1. There are two possible answers for these queries: yes/no answers and generative answers. An answer to a query Q(x⃗) in a disjunctive deductive database DB is yes iff DB ⊧ ∃x⃗(A_{1}, …, A_{n}). We refer to such queries for which only yes/no answers are sought as closed queries. An answer to a query is called generative if it is a set of substitutions {θ_{1}, …, θ_{k}} of the variables in the query such that DB ⊧ (A_{1}∧…∧A_{n})θ_{1}∨… (A_{1}∧…∧A_{n})θ_{k}. We refer to answers that can be represented with a single substitution as definite answers; otherwise they are called disjunctive answers.

In deductive databases, it is necessary to obtain not only a correct answer but the set of all answers. However, we are interested only in minimal answers, i.e. answers that are not subsumed by other answers.

Definition 2 ([FM91]) A set of answers S is a complete set of answers for a query Q(x⃗) iff (∀C′ ∈ S, C′ is an answer to Q(x⃗)) and (∀C′′ ∉ S, (C′′ is an answer to Q(x⃗) ⇒ (∃C′ ∈ S, C′ ⇒ C′′)).

If the set S is empty, then we say that the query Q(x⃗) is not entailed by the database DB.

2.2 Complexity of disjunctive databases

It is known that for a very simple class of queries and disjunctive databases, the complexity of answering queries is CoNP-complete [IV89]. The following example is taken from [Imi91]:

Example 2 Assume that we are given an instance of a graph G = (V, E) and we want to decide whether G can be colored using three colors: red, green and black. We construct an instance of a disjunctive database DB as follows: i) v ∈ V iff color(v, red) ∨ color(v, green) ∨ color(v, black) ∈ DB (the disjunctions represent the information that each node can be colored with red, green or black), ii) ⟨m, n⟩ ∈ E iff edge(m, n) ∈ DB(the atoms represent the edges in the graph). Let Q be the following query: ∃X∃Y ∃Zedge(X, Y) ∧ color(X, Z) ∧ color(Y, Z). The query Q encodes the graph-colorability problem. If the answer to the query Q is yes, then the graph G cannot be colored with three colors without having two adjacent nodes with the same color. Thus, for a very simple query, an yes/no query of conjunctions of atoms in a database with disjunctions but no rules is intractable.

Even in a restricted case when disjunctions in a database are limited to one column of a single predicate, the intractibility remains. More formally, let B = P_{1}(t_{1}) ∨ … ∨ P_{n}(t_{n}) be a ground disjunction. B is called a restricted disjunction iff

1. All P_{i} for i = 1, …, n are the same predicate.

2. All tuples t_{i} differ exactly on one attribute.

For example, P (a, b) ∨ P (c, d) is not a restricted disjunction, but P (a, b) ∨ P (a, c) is.

It has been argued that such restricted disjunctions occur much more often in practice then unrestricted disjunctions. Unfortunately, restricted disjunctions are not computationally beneficial ( at least in the worst case). The following example shows that, in the worst case, they are equivalent to arbitrary disjunctions [IV89].

Example 3 Assume we have a set of monotonic clauses C = {C_{1}, …, C_{n}} each with 3 literals such that in each clause, all the literals are either positive or negative but not both.. We construct a disjunctive database as follows. For each clause C_{i} = l_{1} ∨ l_{2} ∨ l_{3}, we have a disjunctive fact in the database p_{1} ∨ p_{2} ∨ p_{3} where p_{i} = true(x) if l_{i} is a positive literal x, and p_{i} = false(x) if l_{i} is a negative literal of the form ¬x. Let Q(X) = true(X),false(X). The query Q encodes the complement of the monotonic 3-satisfiability problem. If the answer to the query is yes, then the set C of monotonic clauses is not satisfiable. Thus, for a very simple yes/no query of conjunctions of atoms in a database with restricted disjunctions but no rules, the computation is intractable.

Conjunctive queries in deductive databases represent natural joins in relational algebra. Therefore, even a fundamental operation like join is CoNP-complete when general disjunctions are allowed in relational databases. The natural question that arises here is whether there are interesting classes of queries which can always be processed in polynomial time in a database with disjunctive information or whether there are subclasses of disjunctive databases where general queries can be computed in polynomial time.

Cadoli and Lenzerini [CL90] identify one such tractable subclass of disjunctive logic programs, where at most two literals (either positive or negative) are allowed in each clause (they refer to such clauses as Krom clauses). In [Dal92] Dalal notices that disjunctive logic programs with at most two atoms in a clause are tractable, which are in a subclass of the Krom class. However, they do not present practical and efficient algorithms to evaluate the queries. In the next section, we show how answers to some queries can be computed efficiently in polynomial time in a 2-disjunctive database where at most two atoms are allowed in a disjunction.

q(a) p(a) p(c)  q(c)  q(e)  p(e)  p(f)  q(f) q(h) p(h) q(g) q(d) p(d) ∗ ∗  p(g) q(b)  p(b) ∗  p(i)  q(j)

Figure 1: The D-graph G_{D}B that represents the 2-disjunctive database of Example 3.

3 2-Disjunctive Deductive Databases

We consider a subclass of disjunctive databases we call 2-disjunctive databases in which there are no rules and at most two atoms are allowed in any ground disjunction. 2-Disjunctive databases are a subclass of the Krom class which has been identified as tractable. We represent the database by a graph and show how some queries can be evaluated in polynomial time by computing paths in the graph.

Definition 3 A disjunctive deductive database is called a 2-disjunctive database iff all the ground disjunctions in DB contain at most 2 atoms and there are no rules (i.e., I_{DB} = ∅).

Definition 4 Let DB be a 2-disjunctive database. The D-graph G_{DB} that represents the database DB is a tuple ⟨V, D, f, mark⟩ where V is the set of vertices, D is the set of undirected edges called d-edges, f : V → H_{DB} is the labelling function and mark : V → {true, false} is the marking function such that

1. H_{DB} is the set of all atoms belonging to DB.

2. f is one-to-one and onto.

3. D = {(m, n) | the 2-disjunctive clause f(m) ∨ f(n) belongs to DB}.

4. mark(n) = true iff the definite clause f(n) belongs to DB, false otherwise.

A node n in the D-graph G_{DB} for which mark(n) = true is called a marked node and is denoted with an asterisk in the pictorial representation of the D-graph.

Example 4 Let DB be the following 2-disjunctive database:

p(a) p(b) p(c) q(a) ∨ q(b) q(c) ∨ q(d) q(c) ∨ p(d) p(e) ∨ p(f) q(e) ∨ q(g) q(e) ∨ p(g) q(f) ∨ q(h) q(f) ∨ p(h) p(i) ∨ q(j)

Figure 1 shows the D-graph G_{DB} that represents the 2-disjunctive database DB.

Let DB be a 2-disjunctive database represented by the D-graph G_{DB}. For simplicity, we assume that DB contains only two different types of predicates p and q (with possibly mixed 2-disjunctions). Queries to DB can be answered by using the D-graph G_{DB}. For simple selection and projection queries, the computation is straight-forward. However, computing queries that involve natural join is more complex. In the rest of this section, we describe how we can compute simple selection-projection queries, join queries with at most 2 atoms, and negated ground queries in DB in polynomial time by using the D-graph G_{DB}. We assume that the predicates have only one argument, although our methods can be easily extended for more general cases.

Answering selection/projection queries Queries with only one atom in their body are called selection/projection queries. Answers to such queries in a 2-disjunctive database DB can be computed using the D-graph G_{DB} that represents DB.

Lemma 1 Let Q = p(X) be a selection/projection query, and let θ, θ_{1}, θ_{2} be ground substitutions.

1. θ is a definite answer to Q iff ∃n ∈ V such that mark(n) = true and Qθ = f(n).

2. θ_{1} ∨ θ_{2} is a disjunctive answer to Q iff ∃(m, n) ∈ D such that mark(m) = false, mark(n) = false, Qθ_{1} = f(m) and Qθ_{2} = f(n).

3. There are no other minimal answers.

Answering 2-join queries Queries defined by a conjunction of two atoms are called 2-join queries. Let Q = p(X) ∧ q(X) be the 2-join query to a 2-disjunctive database DB that we want to evaluate. We need some additional tools to evaluate this query.

Definition 5 A Q-graph G_{DB∪{←Q}} of a D-graph G_{DB} = ⟨V, D, f, mark⟩ that represents a 2-disjunctive database DB with respect to a 2-join query Q = p(X) ∧ q(X) is a tuple ⟨V, D, J, f, mark, S⟩ where J is a set of edges called j-edges and S is a function that maps j-edges to ground substitutions such that

1. J = {(m, n) | ∃ a ground substitution θ and Qθ = f(m) ∧ f(n)}.

2. S((m, n)) = θ iff Qθ = f(m) ∧ f(n) where θ is a ground substitution.

In the pictorial representation of a Q-graph, d-edges are shown with straight lines and j-edges are shown with dotted lines. Notice that both types of edges may be present at the same time between a pair of nodes m and n in a Q-graph.

Example 5 Figure 2 shows the Q-graph that represents G_{DB∪{←Q}} with respect to the 2-join query Q = p(X) ∧ q(X).

Answers to the 2-join query Q are related to different types of paths in the Q-graph G_{DB∪{←Q}}.

Definition 6 A path P = (n_{1}, n_{2}, …, n_{2k}) is called a simple Q-path in the Q-graph G_{DB∪{←Q}} iff

1. ∀i ≠ j, n_{i} ≠ n_{j}, nodes n_{1} and n_{2k} are marked and all other nodes are not marked.

2. ∀i such that 1 ≤ i < 2k, if i is odd, then (n_{i}, n_{i+1}) is a j-edge in the Q-graph.

3. ∀i such that 1 ≤ i < 2k, if i is even, then (n_{i}, n_{i+1}) is a d-edge in the Q-graph.

Definition 7 A path P = (n_{1}, n_{2}, …, n_{2k}, n_{j}, n_{j−1}, …, n_{1}) is a cyclic Q-path in the Q-graph G_{DB∪{←Q}} iff

1. n_{2k} is not marked, but marking n_{2k} gives a simple Q-path P′ = (n_{1}, n_{2}, …, n_{2k}).

2. 1 < j < 2k, (n_{2k}, n_{j}) is a d-edge and (n_{j−1}, n_{j}) is a j-edge in the Q-graph.

q(a)  p(b) p(c)  q(c)  q(e)  p(e)  p(f)  q(f) q(h) p(h) q(g) q(d) p(d) ∗  p(g) q(b)  q(j) p(i) ∗ p(a)  ∗

Figure 2: The Q-graph G_{DB∪{←Q}} with respect to 2-join query Q.

Definition 8 A path P = (n_{1}, n_{2}, …, n_{2i}, n_{j}, …, n_{1}, m_{1}, …, m_{2k}, m_{l}, …, m_{1}) is a complex Q-path in the Q-graph G_{DB∪{←Q}} iff

1. n_{1} is not marked, but marking n_{1} gives a cyclic Q-path P′ = (n_{1}, n_{2}, …, n_{2i}, n_{j}, …, n_{1}).

2. m_{1} is not marked, but marking m_{1} gives a cyclic Q-path P′′ = (m_{1}, m_{2}, …, m_{2k}, m_{l}, …, m_{1}).

3. (m_{1}, n_{1}) is a d-edge and (m_{1}, n_{1}) is not a j-edge in the Q-graph.

Example 6 Figure 3 shows (a)a simple Q-path, (b)a cyclic Q-path and (c)a complex Q-path in the Q-graph of Example 2.

Definition 9 An s-set of a Q-path P is the set of all ground substitutions S((m, n)) such that (m, n) is a j-edge in the path P.

Example 7 The s-sets of the paths in Figure 5 are (a){a, b}, (b){c, d} and (c){e, f, g, h}.

Edges in Q-paths represent resolution steps in the proof of the 2-join query Q in DB. Therefore, each Q-path represents the computation towards a particular answer. The following theorems relate answers to a 2-join query Q with the s-sets of the Q-paths defined above.

Lemma 2 If P = (n_{1}, n_{2}, …, n_{2k}) is a simple Q-path with s-set(P) = {x_{1}, …, x_{k}} then X = x_{1} ∨ X = x_{2} ∨ … X = x_{k} is an answer to the query Q = p(X) ∧ q(X).

Proof: (by induction on k)

Base Case: k = 1.

The only possible simple Q-path is (n_{1}, n_{2}) where either f(n_{1}) = p(x_{1}) and f(n_{2}) = q(x_{1}) or f(n_{1}) = q(x_{1}) and f(n_{2}) = p(x_{1}) and both n_{1} and n_{2} are marked. Therefore, DB ⊧ p(x_{1}) and DB ⊧ q(x_{1}), which implies DB ⊧ p(x_{1}) ∧ q(x_{1}) i.e., X = x_{1} is an answer to the query Q = p(X) ∧ q(X).

Induction Step:

Assume that if P = (n_{1}, n_{2}, …, n_{2k}) is a simple Q-path with s-set(P) = {x_{1}, …, x_{k}} then X = x_{1} ∨ X = x_{2} ∨ … X = x_{k} is a minimal answer to the query Q = p(X) ∧ q(X).

Let P_{1} = (m_{1}, m_{2}, …, m_{2k}, m_{2k+1}, m_{2k+2}) be a simple Q-path in the graph with s-set(P_{1})={x_{1}, …, x_{k}, x_{k+1}}. By the definition of a simple path, (m_{2}, m_{3}) is a d-edge in the Q-graph. Without loss of generality, let us assume that f(m_{2}) = q(x_{1}) and f(m_{3}) = p(x_{2}). Since (m_{2}, m_{3}) is a d-edge in the Q-graph,

(a)p(b) q(b) q(a) p(a) ∗ ∗  (b) ∗ p(c) q(c) q(d) p(d)  (c) p(e)  p(f) q(e) q(g) p(g)  p(h) q(h) q(f)

Figure 3: (a) a simple Q-path, (b) a cyclic Q-path, (c) a complex Q-path.

q(x_{1}) ∨ p(x_{2}) must be a disjunction in the database DB. Clearly, DB ∪ {q(x_{1})} ⊧ p(x_{1}) ∧ q(x_{1}) because (f^{−1}(p(x_{1})), f^{−1}(q(x_{1}))) is a simple Q-path in the graph of DB ∪ {q(x_{1})}. Similarly, in the graph of DB ∪ {p(x_{2})}, P′ = (m_{3}, m_{4}, …, m_{2k+2}) is a simple Q-path with s-set(P′) = {x_{2}, …, x_{k+1}}; therefore, by the induction hypothesis, DB ∪ {p(x_{2})} ⊧ (p(x_{2}) ∧ q(x_{2})) ∨ … ∨ (p(x_{k+1}) ∧ q(x_{k+1}). Therefore, DB ∪ {q(x_{1}) ∨ p(x_{2})} ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ (p(x_{2}) ∧ q(x_{2})) ∨ … ∨ (p(x_{k+1}) ∧ q(x_{k+1}) which implies X = x_{1} ∨ … ∨ X = x_{k+1} is an answer to the query Q in the database DB.

Lemma 3 If P = (n_{1}, n_{2}, …, n_{2k}, n_{j}, …, n_{1}) is a cyclic Q-path with s-set(P) = {x_{1}, …, x_{k}} then X = x_{1} ∨ X = x_{2} ∨ … X = x_{k} is an answer to the query Q = p(X) ∧ q(X).

Proof:

By the definition of a cyclic Q-path, (n_{2k}, n_{j}) is a d-edge in the Q-graph. Without loss of generality, let us assume that f(n_{2k}) = q(x_{k}) and f(n_{j}) = q(x_{\frac{j}{2}} ). Since (n_{2k}, n_{j}) is a d-edge in the Q-graph, q(x_{k}) ∨ q(x_{\frac{j}{2}} ) must be a disjunction in the database DB. Clearly, in the Q-graph of the database DB ∪ \{q(x_{\frac{j}{2}} )\}, P′ = (n_{1}, n_{2}, …, n_{j}) is a simple Q-path with s-set(p′) = \{x_{1}, …, x_{\frac{j}{2}} \}; therefore, by 2, DB ∪ \{p(x_{j})\} ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ … ∨ (p(x_{\frac{j}{2}} ) ∧ q(x_{\frac{j}{2}} ). Similarly, in the Q-graph of DB ∪ \{p(x_{k})\}, P′ = (n_{1}, n_{2}, …, m_{2k}) is a simple Q-path with s-set(P′) = {x_{1}, …, x_{k}}; therefore, by 2, DB ∪ {q(x_{k})} ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ … ∨ (p(x_{k}) ∧ q(x_{k}). Therefore, DB ∪ \{q(x_{k}) ∨ p(x_{\frac{j}{2}} )\} ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ (p(x_{2}) ∧ q(x_{2})) ∨ … ∨ (p(x_{k}) ∧ q(x_{k})) which implies X = x_{1} ∨ … ∨ X = x_{k} is an answer to the query Q in the database DB.

Lemma 4 If P = (n_{1}, n_{2}, …, n_{2i}, n_{j}, …, n_{1}, m_{1}, m_{2}, …, m_{2k}, m_{l}, …, m_{2}, m_{1}) is a complex Q-path with s-set(P) = {x_{1}, …, x_{h}} then X = x_{1} ∨ X = x_{2} ∨ … X = x_{h} is an answer to the query Q = p(X) ∧ q(X).

Proof:

By the definition of a complex Q-path, (n_{1}, m_{1}) is a d-edge in the graph. Without loss of generality, let us assume that f(n_{1}) = p(x_{i}) and f(m_{1}) = q(x_{k}) where x_{i} ≠ x_{k}. Since (n_{1}, m_{1}) is a d-edge in the Q-graph, p(x_{i}) ∨ q(x_{k}) must be a disjunction in the database DB. Clearly, in the D-graph of the database DB ∪ {p(x_{i})}, P′ = (n_{1}, n_{2}, …, n_{2i}, n_{j}, …, n_{1}) is a simple Q-path with s-set(P′) = {x_{1}, …, x_{i}}; therefore, by 3, DB ∪ {p(x_{i})} ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ … ∨ (p(x_{i}) ∧ q(x_{i})). Similarly, in the Q-graph of DB ∪ {q(x_{k})}, P′′ = (m_{1}, m_{2}, …, m_{2k}, m_{l}, …, m_{1}) is a simple Q-path with s-set(P′′) = {x′_{1}, …, x′_{k}}; therefore, by 3, DB ∪ {q(x_{k})} ⊧ (p(x′_{1}) ∧ q(x′_{1})) ∨ … ∨ (p(x′_{k}) ∧ q(x′_{k}). Since s-set(p) = s-set(p′) ∪ s-set(p′′), DB ∪ {q(x_{k}) ∨ p(x_{i})} ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ (p(x_{2}) ∧ q(x_{2})) ∨ … ∨ (p(x_{h}) ∧ q(x_{h})) which implies X = x_{1} ∨ … ∨ X = x_{h} is an answer to the query Q in the database DB.

Theorem 1 If P is a simple, cyclic or complex Q-path with s-set(P) = {x_{1}, …, x_{k}} in the Q-graph of a 2disjunctive database DB with respect to a 2-join query Q = p(X)∧q(X), then X = x_{1} ∨X = x_{2} ∨… X = x_{k} is an answer to the query Q.

Proof: by Lemmas 2, 3 and 4.

Theorem 2 If X = x_{1} ∨ X = x_{2} ∨ … ∨ X = x_{k} is a minimal answer to the 2-join query Q = p(X) ∧ q(X) in a 2-disjunctive database DB, then there is a simple, cyclic or complex Q-path P in the Q-graph of DB with respect to the query Q such that s-set(P) = {x_{1}, x_{2}, …, x_{k}}.

Proof: Since DB ⊧ (p(x_{1}) ∧ q(x_{1})) ∨ (p(x_{2}) ∧ q(x_{2})) ∨ … (p(x_{k}) ∧ q(x_{k})), all of the following must be true in DB: DB ⊧ p(x_{1}) ∨ p(x_{2}) … ∨ p(x_{k}) DB ⊧ q(x_{1}) ∨ p(x_{2}) … ∨ p(x_{k}) DB ⊧ p(x_{1}) ∨ p(x_{2}) … ∨ p(x_{k}) DB ⊧ p(x_{1}) ∨ q(x_{2}) … ∨ p(x_{k})

⋮ DB ⊧ q(x_{1}) ∨ q(x_{2}) … ∨ p(x_{k}) DB ⊧ q(x_{1}) ∨ q(x_{2}) … ∨ q(x_{k})

Since, only 2-disjunctions are allowed in DB, all of the above must be implied by definite and 2-disjunctive facts only. There could be three cases:

Case 1: There are 2 definite facts (without loss of generality, let us assume p(x_{i}) and q(x_{j}) where x_{i} ≠ x_{j}). It can be shown that the Q-graph of DB has a simple Q-path P where f^{−1}(p(x_{i})) is the start node and f^{−1}(q(x_{j})) is the end node of P.

Case 2: There is a definite fact (without loss of generality, let us assume p(x_{i})). It can be shown that the Q-graph of DB has a cyclic Q-path P where f^{−1}(p(x_{i})) is the start node of P.

Case 3: There is no i ∈ {1, 2, …, k} such that p(x_{i}) or q(x_{i}) is true in DB. It can be shown that the Q-graph of DB has a complex Q-path P where s-set(P) = {x_{1}, x_{2}, …, x_{k}}.

The above theorems are the basis for our algorithm to compute generative answers to 2-join queries in 2-disjunctive databases by traversing the Q-graphs and computing Q-paths. The traversal uses a technique we call alternate-edge depth-first-search which is a variation of the usual depth-first-search technique for undirected graphs and runs in polynimial time with respect to the size of the database. The algorithm is presented in section 4.

Answering negated ground queries Queries with only one negated ground atom in their body are called negated ground queries. Using the GCWA as the semantics for negation, answers to such queries in a 2-disjunctive database DB can be computed in polynomial time.

Lemma 5 Let Q = ¬p(a) be the negated ground query that we want to evaluate using GCWA.

1. If ∃n ∈ V such that f(n) = p(a) and mark(n) = true then Q is false in DB.

2. If ∃(n, m) ∈ D such that f(n) = p(a), mark(m) = false and mark(n) = false then Q is unknown in DB.

3. Otherwise, Q is true in DB.

4 Algorithms

In this section, we present the algorithms to compute yes/no answers and generative answers to 2-join queries in 2-disjunctive databases by traversing the Q-graphs and computing Q-paths. The traversal uses a technique we call alternate-edge depth-first-search which is a variation of the usual depth-first-search technique for undirected graphs. In an altrnate-edge depth-first-search, if a node is visited through a d-edge, then its j-neighbor only is visited from that node; similarly if a node is visited through a j-edge, then its d-neighbors only are visited from that node. Search is stopped when a marked node is visited through a j-edge or when an appropriate back-edge is found.

Before we describe the algorithms, we need to define some operators used in Q-graph traversals.

mark(n) deletes all d-edges incident on node n and saves them for future reconstruction and sets marked[n] to true.

unmark(n) re-inserts all d-edges that were deleted and stored by a previous mark(n) operation and sets marked[n] to false.

d-neighbors(n) returns the set of all nodes m such that (m, n) is a d-edge in the Q-graph.

j-neighbor(n) returns node m if (m, n) is a j-edge in the Q-graph.

4.1 Computing yes/no answers

In this section, we present an algorithm to compute yes/no answers to a 2-join query Q = p(X) ∧ q(X) in a 2-disjunctive database. We assume that the Q-graph is computed before the algorithm is invoked. The algorithm searches the Q-graph for a simple, cyclic or complex Q-path using the alternate-edge depth-first-search technique and returns yes if it can find any such Q-path. Otherwise, it returns no.

Algorithm 1: {gives an yes/no answer to a join query}

step 1. {look for a simple or cyclic Q-path starting at a marked node} for each marked node n do if there is a simple or cyclic Q-path starting at node n then return an yes answer and halt.

step 2. {look for a complex Q-path } for each unused d-edge (m, n) where (m, n) is not a j-edge do if mark(m) and mark(n) result in new simple or cyclic Q-paths starting at nodes m and n then a complex Q-path has been found, return an yes answer and halt.

step 3. {no simple, cyclic or complex Q-path was found in steps 1 and 2} return a no answer.

Algorithm 1.a:{checks if there is a simple or cyclic Q-path beginning at node n}

1. if node n has no j-neighbor then return no.

2. begin an alternate-edge depth-first-search by visiting the j-neighbor of node n through a j-edge. The search performs successfully if a marked node is ever visited through a j-edge or a node is ever visited through a j-edge such that one of its d-neighbors has already been visited through a j-edge. if the search succeeds then return yes else return no.

The above algorithm can be used to check if a given answer is indeed correct or not. All we have to do is modify the algorithm so that during the search through the graph, it only visits those nodes whose values are contained in the given answer.

Lemma 6 Algorithm 1 runs in polynomial time.

4.2 Computing generative answers

We now present an algorithm to compute the set of all answers to a 2-join query in a 2-disjunctive database. We assume that the Q-graph is computed before the algorithm is invoked. The algorithm stores in the set ANSW ER the s-sets of all simple, cyclic and complex Q-paths in the Q-graph and returns this set. The actual algorithm that is used to compute the s-sets of all simple and cyclic Q-paths beginning at a specified node n is presented in the Appendix. We refer to the Appendix for a detailed discussion of the alternateedge depth-first-search algorithm and how it is used to compute the s-sets of all simple and cyclic Q-paths beginning at a given node.

Algorithm 2: {returns the set of all answers to a 2-join query}

Initially, ANSW ER ← {∅}

step 1. {find all simple and cyclic Q-paths and compute s-sets of these Q-paths} for each marked node n do

1.1 S ← {s | P is a simple or cyclic Q-path beginning at node n and s = s-set(P)}

1.2 ANSW ER ← ANSW ER ∪ S

step 2. {find all complex Q-paths and compute s-sets of these Q-paths} for each unused d-edge (m,n) where (m, n) is not a j-edge do

2.1 mark(m); S_{1} ← {s | P is a simple or cyclic Q-path beginning at node m and s = s-set(P)}; unmark(m).

2.2 mark(n); S_{2} ← {s | P is a simple or cyclic Q-path beginning at node n and s = s-set(P)}; unmark(n).

2.3 if S_{1} ≠ {∅} and S_{2} ≠ {∅} then

2.3.1 S ← {s_{1} ∪ s_{2}|s_{1} ∈ S_{1} ∧ s_{2} ∈ S_{2}}
2.3.2 ANSW ER ← ANSW ER ∪ S

2.4 mark d-edge (m,n) as used

step 3. {no more Q-paths in the Q-graph} return ANSW ER

Lemma 7 Algorithm 2 runs in polynomial time.

Proof: The worst-case running time of an alternate-edge depth-first-search is the same as the worst-case case running time of a depth-first-search in an undirected graph which is Θ(n + e). Since one such search is performed at every marked node and at nodes that are connected by unused d-edges, the running time of Algorithm 2 is bounded by Θ(max(n, e) ∗ (n + e)).

Example 8 Figure 4 shows how Algorithm 2 travarses the D-graph of example 2 to compute all simple, cyclic and complex paths and their s-sets..

5 2-Disjunctive Databases with Rules

In this section, we identify some classes of rules in a hierarchical disjunctive deductive database with 2disjunctions that are tractable. In a hierarchical disjunctive deductive database, it is possible to establish an evaluation order for rules in the databases such that each rule needs to be evaluated only once during the computation. The rules that define a predicate p appear in the order prior to a rule that uses p. We classify tractable rules in a hierarchical 2-disjunctive deductive database and present polynomial time algorithms to evaluate rules in each class.

return ANSW ER = {{a, b}, {c, d}, {e, f, g, h}} p(b) {b} {b} q(b) q(a) {a, b} {a, b} p(a)  ∗ ∗ p(e) q(e) q(g) p(g)  p(f) q(f) q(h) p(h) ∗  {g} {g}  {h} {h} {f, h} {f, h} {e, g} {e, g} {e, g, f, h} Step 1: Step 2: Step 3:  ∗  {c, d} {c, d} {d} {d} p(c) q(c) p(d) ∗ q(d)

Figure 4: Paths and s-sets in the D-graph of example 2 computed by Algorithm 2

5.1 Safe Selection Rules

Rules with only one atom in their head and one atom in their body are called safe selection rules. Evaluation of a safe selection rule s ← p in a graph G_{DB} that represents a 2-disjunctive database DB yields a larger graph G_{DB∪{s←p}} which contains the old graph G_{DB}.

Algorithm: Computes G_{DB∪{s←p}} from G_{DB} and a safe selection rule (s ← p).

For each node n such that ∃θ ground, f(n) = pθ do

step 1. create a new node n′ with f(n′) = sθ and set new[n] = n′

step 2. if n is marked or ∃m ∈ d-neighbor(n) such that ∃θ′ ground, f(m) = pθ′ and f(n′) = sθ′ then mark node n′.

else for each m ∈ d-neighbor(n) do

create d-edge (n′, m)

if f(m) = p then create d-edge (n′,new[m])

Example 9 Let DB be the following 2-disjunctive database:

p(a, f) q(f) p(b, g) ∨ p(b, h) q(g) p(c, f) ∨ p(d, h) q(h)

The graph G_{DB} that represents DB and G_{DB∪{s(X)←p(X,Y)}} after the evaluation of the safe selection rule {s(X) ← p(X, Y)} are shown in Figure 5(a) and 5(b).

5.2 Safe Join Rules

Rules with only one atom in their head and two atoms in their body where one predicate is definite and the other is disjunctive are called safe join rules. Evaluation of a safe selection rule s ← p, q in a graph G_{DB} that represents a 2-disjunctive database DB yields a larger graph G_{DB∪{s←p,q}} which contains the old graph G_{DB}.

Algorithm: Computes G_{DB∪{s←p,q}} from G_{DB} and a safe join rule (s ← p, q) where p is disjunctive and q is definite.

For each node n such that ∃θ_{1} ground, f(n) = pθ_{1} do if there is a node m such that ∃θ_{2} ground, f(m) = qθ_{1}θ_{2}

step 1. create a new node n′ with f(n′) = sθ_{1}θ_{2} and set new[n] = n′

step 2. for each m ∈ d-neighbor(n) do

create d-edge (n′, m)

if f(m) = p then if f(new[m] = f(n′) then mark n′ else create d-edge (n′,new[m])

Example 10 The D-graph G_{DB∪{s(X)←p(X,Y),q(Y)}} after the evaluation of the safe selection rule {s(X) ← p(X, Y), q(Y)} are shown in Figure 5(c).

(c)^{∗}^{∗}^{∗}^{∗}  ^{p(d, h)}^{p(c, h)}^{p(b, h)}^{p(b, g)}  ^{q(h)}^{q(g)}^{q(f)}^{p(a, f)}  (a)^{p(d, h)}^{p(c, h)}^{p(b, h)}^{p(b, g)}^{p(a, f)}  ^{q(f)}  ^{q(g)}  ^{q(h)}^{∗}  ^{∗}  ^{∗}  ^{∗}^{∗}  ^{∗}^{s(a)}  ^{s(b)}  ^{s(c)}  ^{s(d)} (b)  ^{s(d, h)}^{s(c, h)}^{s(b, h)}^{s(a, f)} ^{s(b, g)}  ^{∗}^{∗}^{∗}^{∗}  ^{q(h)}^{q(g)}^{q(f)}^{p(a, f)} ^{p(b, h)}^{p(b, g)}  ^{p(d, h)}^{p(c, h)}^{∗}

Figure 5: (a) The D-graph G_{DB} of the Database in Example (b) The D-graph G_{DB∪{s(X)←p(X,Y)}}, (c) The graph G_{DB∪{s(X)←p(X,Y),q(Y)}}.

6 Conclusion

In this paper, we identified a tractable class of disjunctive deductive databases. We defined 2-disjunctive databases and presented polynomial time algorithms to compute general queries in such databases. One advantage of our algorithm is that by introducing a parameter k, we can control the depth of the graph search and thus the user can get a better response time by specifying the length of disjunctive answers if he is interested in shorter answers only. We also classified some classes of rules that are evaluable in polynomial time and presented algorithms to evaluate them. Our future research would be on finding larger and more powerful subclasses of disjunctive deductive databases that are tractable.

References

[CL90] M. Cadoli and M. Lenzerini. The complexity of closed world reasoning and circumscription. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI-90), pages 550–555. MIT Press, July 1990.

[Dal92] M. Dalal. Some tractable classes of disjunctive logic programs. Technical report, Rutgers University, Department of Computer Science, 1992.

[Dem89] R. Demolombe. An efficient evaluation strategy for non-horn deductive databese. In Proceedings of IFIP, 1989.

[FM91] J. A. Fernandez and J. Minker. Bottom-up evaluation of hierarchical disjunctive deductive databases. In K. Furukawa, editor, Logic Programming proceedings of the 8th International Conference, pages 660–675. MIT Press, 1991.

[GM86] J. Grant and J. Minker. Answering queries in indefinite databases and the null value problem. In P. Kanellakis, editor, Advances in Computing Research, pages 247–267. 1986.

[GM92] J. Grant and J. Minker. The impact of logic programming on databases. Communications of the ACM, 35(3):66–81, March 1992.

[HP88] L. J. Henschen and H. Park. Compiling the gcwa in indefinite database. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 395–438. Morgan Kaufmann Pub., Washington, D.C., 1988.

[Imi91] T. Imielinsky. Incomplete deductive databases. Annals of Mathematics and Artificial Intelligence, 3:259–294, 1991.

[IV89] T. Imielinsky and K. Vadaparty. Complexity of query processing in databases with or-objects. In Proceedings of the 7th ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, pages 51–65, Philadelphia, Pennsylvania, March 1989.

[LMR92] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, 1992.

[LS91] K.C. Liu and R. Sunderraman. A generalized relational model for indefinite and maybe information. IEEE Transactions on Knowledge and Data Engineering, 3(1):65–77, 1991.

[LYW92] J. Lobo, C. Yu, and G. Wang. Computing the transitive closure in disjunctive databases. Technical report, University of Illinois at Chicago, Department of Electrical Engineering and Computer Science, 1992.

[Var86] M. Vardi. Querying logical databases. Journal of Computing and Systems Sciences, (33):142–160, 1986.

[YC89] L. Y. Yuan and D.A. Chiang. A sound and complete query evaluation algorithm for relational databases with disjunctive information. In Proceedings of the 8th Symposium on Principles of Database Systems, pages 66–74, March 1989.

[YH85] A. Yahya and L. J. Henschen. Deduction in non-horn databases. Journal of Automated Reasoning, 1(2):141–160, 1985.

A Appendix

Before we describe the algorithm, we need to define the data structures and operators used in Q-graph traversals.

visited[n] = \{ \begin{matrix}true & if node n is marked and has been visited \\ d-edge & if node n is not marked and has been visited through a d-edge \\ j-edge & if node n is not marked and has been visited through a j-edge \\ false & if node n has not been visited yet \end{matrix}

p-sets[n]: set of partial sets where each partial-set is a subset of an s-set of a simple or cyclic Q-path that contains node n. initialize(): for all nodes n p-sets[n] is set to {∅}, visited[n] and done[n] are set to false.

Algorithm: computes s-sets of all simple and cyclic Q-paths starting at node n in a Q-graph G_{DB∪{←Q}} = ⟨V, D, J, f, mark, S⟩.

0. initialize()

1. S-SETS← {∅}

2. if ∃(n, m) ∈ J then alternate-edge-dfs(m,n,j-edge) S-SETS←p-sets[m]

3. return(S-SETS)

procedure alternate-edge-dfs(m,n,edge-type) {visits node m from node n, performs a depth-first search and stores in p-sets[m] the set of partial s-sets of Q-paths that contain node m}

0. P-SETS← {∅}

1. visited[m]←edge-type

2. if edge-type = d-edge and ∄(m, n) ∈ J then alternate-edge-dfs(j-neighbor(m),m,j-edge) P-SETS←p-sets[j-neighbor(m)]

3. if edge-type = j-edge then if mark(n) then P-SETS← {{S((m, n))}} else for each v ∈ d-neighbors(m) do

if visited[v] = j-edge and done[v] = false then P-SETS←P-SETS∪{{S((m, n))}} if visited[v] = d-edge and done[v] = true and p-sets[v] ≠ {∅} then

P-SETS←P-SETS∪{s ∪ {S((m, n))} | s ∈ p-sets[v]} else if visited[v] = false then

alternate-edge-dfs(v, m,d-edge)

P-SETS←P-SETS∪{s ∪ {S((m, n))} | s ∈ p-sets[v]}

4. p-sets[m]←P-SETS

5. done[m]← true

6. return()