Browsing by Author "van der Meyden R"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Recursively indefinite databases(1993) van der Meyden RWe 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.