determinacy and rewriting of conjunctive queries over unary database schemas

	determinacy and rewriting of conjunctive queries over unary database schemas
	Zheng Lixiao; Chen Haiming
	2011
会议名称	26th Annual ACM Symposium on Applied Computing, SAC 2011
会议录名称	Proceedings of the ACM Symposium on Applied Computing
页码	1039-1044
会议日期	March 21,
会议地点	TaiChung, Taiwan
收录类别	EI
出版地	United States
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
摘要	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.
关键词	Computability And Decidability Information Management Information Theory Query Processing
主办者	ACM Special Interest Group on Applied Computing (SIGAPP); Tunghai University; Taiwan Ministry of Education; Taiwan Bureau of Foreign Trade; Taiwan National Science Council (NSC)
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/14325
专题	基础软件与系统重点实验室
推荐引用方式 GB/T 7714	Zheng Lixiao,Chen Haiming. determinacy and rewriting of conjunctive queries over unary database schemas[C]. United States,2011:1039-1044.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
determinacy and rewr（561KB）			开放获取	--	请求全文