Journal
ACM TRANSACTIONS ON DATABASE SYSTEMS
Volume 35, Issue 3, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1806907.1806913
Keywords
Algorithms; Design; Security; Theory; Verification; Queries; views; rewritingg
Funding
- National Science Foundation [IIS-0705589]
Ask authors/readers for more resources
We investigate the question of whether a query Q can be answered using a set V of views. We first define the problem in information-theoretic terms: we say that V determines Q if V provides enough information to uniquely determine the answer to Q. Next, we look at the problem of rewriting Q in terms of V using a specific language. Given a view language V and query language Q, we say that a rewriting language R is complete for V-to-Q rewritings if every Q is an element of Q can be rewritten in terms of V is an element of V using a query in R, whenever V determines Q. While query rewriting using views has been extensively investigated for some specific languages, the connection to the information-theoretic notion of determinacy, and the question of completeness of a rewriting language have received little attention. In this article we investigate systematically the notion of determinacy and its connection to rewriting. The results concern decidability of determinacy for various view and query languages, as well as the power required of complete rewriting languages. We consider languages ranging from first-order to conjunctive queries.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available