Logical Queries over Views: Decidability and Expressiveness
James Bailey, Guozhu Dong, Anthony Widjaja To
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC | ASSOC COMPUTING MACHINERY | Published : 2010
We study the problem of deciding the satisfiability of first-order logic queries over views, with our aim 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 main result is the identification of a decidable class of first-order queries over unary conjunctive views that generalizes the decidability of the classical class of first-order sentences over unary relations known as the Löwenheim class. We then demonstrate how various extensions of this class lead to undecidability and also provide some expres..View full abstract
Awarded by EPSRC
A. W. To was supported by ORSAS Awards and EPSRC grant E005039.