中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 会议论文
题名:
determinacy and rewriting of conjunctive queries over unary database schemas
作者: Zheng Lixiao ; Chen Haiming
会议文集: Proceedings of the ACM Symposium on Applied Computing
会议名称: 26th Annual ACM Symposium on Applied Computing, SAC 2011
会议日期: March 21,
出版日期: 2011
会议地点: TaiChung, Taiwan
关键词: Computability and decidability ; Information management ; Information theory ; Query processing
出版地: United States
收录类别: EI
ISBN: 9781450301138
部门归属: (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; (2) Graduate University, Chinese Academy of Sciences, China
主办者: ACM Special Interest Group on Applied Computing (SIGAPP); Tunghai University; Taiwan Ministry of Education; Taiwan Bureau of Foreign Trade; Taiwan National Science Council (NSC)
英文摘要: 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.
内容类型: 会议论文
URI标识: http://ir.iscas.ac.cn/handle/311060/14325
Appears in Collections:计算机科学国家重点实验室 _会议论文

Files in This Item:
File Name/ File Size Content Type Version Access License
determinacy and rewriting of conjunctive queries over unary database schemas.pdf(561KB)----限制开放-- 联系获取全文

Recommended Citation:
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,.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Zheng Lixiao]'s Articles
[Chen Haiming]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Zheng Lixiao]‘s Articles
[Chen Haiming]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace