Decidability of First Order Logic Queries over Views

Authors

James Bailey
Guozhu Dong, Wright State University - Main CampusFollow

Document Type

Book Chapter

Publication Date

1999

Find in a Library

Catalog Record

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 (the Lowenheim class). 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, implication of dependencies and reasoning in description logics.

Comments

Paper presented at the 7th International Conference on Database Theory, Jerusalem, Israel, January 10-12, 1999.

Repository Citation

Bailey, J., & Dong, G. (1999). Decidability of First Order Logic Queries over Views. Database Theory--ICDT'99: 7th International Conference, Jerusalem, Israel, January 10-12, 1999: Proceedings, 83-99.
https://corescholar.libraries.wright.edu/knoesis/348