Recursively indefinite databases
Loading...
Date
1993
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Theoretical Computer Science
Keywords
Citation
10.1016/0304-3975(93)90223-G