Journal article

Logical Queries over Views: Decidability and Expressiveness

James Bailey, Guozhu Dong, Anthony Widjaja To

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC | ASSOC COMPUTING MACHINERY | Published : 2010

Abstract

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