期刊
ACM TRANSACTIONS ON DATABASE SYSTEMS
卷 35, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1806907.1806913
关键词
Algorithms; Design; Security; Theory; Verification; Queries; views; rewritingg
资金
- National Science Foundation [IIS-0705589]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据