Complexity aspects of various semantics for disjunctive databases
- 1 January 1993
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 158-167
- https://doi.org/10.1145/153850.153864
Abstract
This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional disjunctive database under a variety of well-known disjunctive database semantics is investigated, as well deciding whether a disjunctive database has a model under a particular semantics. The problems are located in appropriate slots of the polynomial hierarchy.Keywords
This publication has 0 references indexed in Scilit: