Computer Science – Logic in Computer Science
Scientific paper
2008-03-18
Computer Science
Logic in Computer Science
Scientific paper
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 main result is the identification of a decidable class of first order queries over unary conjunctive views that generalises the decidability of the classical class of first order sentences over unary relations, known as the Lowenheim class. We then demonstrate how various extensions of this class lead to undecidability and also provide some expressivity results. Besides its theoretical interest, our new decidable class is potentially interesting for use in applications such as deciding implication of complex dependencies, analysis of a restricted class of active database rules, and ontology reasoning.
Bailey James
Dong Guozhu
To Anthony Widjaja
No associations
LandOfFree
Logical Queries over Views: Decidability and Expressiveness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Logical Queries over Views: Decidability and Expressiveness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logical Queries over Views: Decidability and Expressiveness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-637524