Please use this identifier to cite or link to this item:
Title: An Approach towards the Study of Symmetric Queries
Authors: GYSSENS, Marc 
Paredaens, Jan
Van Gucht, Dirk
Wijsen, Jef
Wu, Yuqing
Issue Date: 2013
Source: Proceedings of the VLDB Endowment, 7 (1), p. 25-36
Abstract: Many data-intensive applications have to query a database that involves sequences of sets of objects. It is not uncommon that the order of the sets in such a sequence does not affect the result of the query. Such queries are called symmetric. In this paper, the authors wish to initiate research on symmetric queries. Thereto, a data model is proposed in which a binary relation between objects and set names encodes set membership. On this data model, two query languages are introduced, QuineCALC and SyCALC. They are correlated in a manner that is made precise with the symmetric Boolean functions of Quine, respectively symmetric relational functions, on sequences of sets of given length. The latter do not only involve the Boolean operations union, intersection, and complement, but also projection and Cartesian product. Quine’s characterization of symmetric Boolean functions in terms of incidence information is generalized to QuineCALC queries. In the process, an incidence-based normal form for QuineCALC queries is proposed. Inspired by these desirable incidence-related properties of QuineCALC queries, counting-only queries are introduced as SyCALC queries for which the result only depends on incidence information. Counting-only queries are then characterized as quantified Boolean combinations of QuineCALC queries, and a normal form is proposed for them as well. Finally, it is shown that, while it is undecidable whether a SyCALC query is counting-only, it is decidable whether a counting-only query is a QuineCALC query.
Document URI:
Link to publication:
ISSN: 2150-8097
e-ISSN: 2150-8097
Rights: Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Articles from this volume were invited to present their results at The 40th International Conference on Very Large Data Bases, September 1st - 5th, 2014, Hangzhou, China. Proceedings of the VLDB Endowment, Vol. 7, No. 1 Copyright 2013 VLDB Endowment 2150-8097/13/09... $ 10.00
Category: A2
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Main article286.75 kBAdobe PDFView/Open    Request a copy
Show full item record

Page view(s)

checked on May 26, 2022

Google ScholarTM


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