Recursively indefinite databases

We define recursively indefinite databases, a new type of logical database in which indefinite information arises from partial knowledge of the fixpoint of a Datalog program. Although, in general, query answering is undecidable, we show that queries containing only basic predicates and monadic defined predicates are decidable. The main contribution of the paper is an analysis of the complexity of query answering for this class of queries. We demonstrate a class of databases which generalizes disjunctive databases, but without increasing data complexity. We also establish connections with the theory of hypergraph edge replacement graph grammars.

Authors

• Ron van der Meyden

Keywords

No keywords are indexed for this paper.