Loading...
Please wait, while we are loading the content...
Similar Documents
A tractable class of disjunctive deductive databases (1992).
| Content Provider | CiteSeerX |
|---|---|
| Author | Zahidul Khandaker Jos'E. Minker, Jack |
| 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 dat... |
| File Format | |
| Publisher Date | 1992-01-01 |
| Access Restriction | Open |
| Content Type | Text |
