Decidability of First Order Logic Queries Over Views
James Bailey, Kings College London
Guozhu Dong, The University of Melbourne
Proceedings of International Conference on
Database Theory, Jerusalem, January, 1999.
Abstract
We study the problem of deciding satisfiability of first order logic
queries over views, our aim being to delimit the boundary between
the decidable and the undecidable fragments of this language.
Views currently
occupy a central place in database research, due to their role in
applications such as information integration and
data warehousing.
Our principal result is the identification
of an important decidable class of queries over unary conjunctive views.
This extends the decidability of the classical class
of first order sentences over unary relations.
We then demonstrate how extending this class leads to undecidability.
In addition to new areas,
our work
also has relevance to extensions of results for related problems such as
query containment, trigger termination, and
implication of dependencies.