determinacy and rewriting of conjunctive queries over unary database schemas
文献类型：会议论文
| 作者 | Zheng Lixiao ; Chen Haiming |
| 出版日期 | 2011 |
| 会议名称 | 26th Annual ACM Symposium on Applied Computing, SAC 2011 |
| 会议日期 | March 21, |
| 会议地点 | TaiChung, Taiwan |
| 关键词 | Computability and decidability Information management Information theory Query processing |
| 页码 | 1039-1044 |
| 英文摘要 | The problem of answering queries using views arises in a wide variety of data management applications. From the information-theoretic perspective, a notion of determinacy has been recently introduced to formalize the intuitive notion that whether a set of views V is sufficient to answer a query Q. We say that V determines Q iff for any two databases D1, D2, V(D1) = V(D2) implies Q(D1) = Q(D2). Determinacy has been investigated for many query and view languages including first order logic (FO) and unions of conjunctive queries (UCQ) and a considerable number of cases are resolved. However the problem remains open for queries and views defined by conjunctive queries (CQ) and appears to be quite challenging. In this paper we study the problem of determinacy for conjunctive queries and views over unary database schemas where each relation has only one attribute. We show that determinacy is decidable in ptime in this case. We provide syntactic characterizations for a CQ query Q to be determined by a set of CQ views V and give an algorithm for checking determinacy which runs in time O(|Q|*|V|) where |Q| and |V| are the sizes of Q and V respectively. Furthermore we show that whenever V determines Q there exists a CQ query which is an equivalent rewriting of Q using V. © 2011 ACM. |
| 收录类别 | EI |
| 会议主办者 | ACM Special Interest Group on Applied Computing (SIGAPP); Tunghai University; Taiwan Ministry of Education; Taiwan Bureau of Foreign Trade; Taiwan National Science Council (NSC) |
| 会议录 | Proceedings of the ACM Symposium on Applied Computing
 |
| 会议录出版地 | United States |
| ISBN号 | 9781450301138 |
| 源URL | [http://124.16.136.157/handle/311060/14325]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _会议论文 |
| 推荐引用方式 GB/T 7714 | Zheng Lixiao,Chen Haiming. determinacy and rewriting of conjunctive queries over unary database schemas[C]. 见:26th Annual ACM Symposium on Applied Computing, SAC 2011. TaiChung, Taiwan. March 21,. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。