Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/16500

Title: An Approach towards the Study of Symmetric Queries
Authors: Gyssens, Marc
Paredaens, Jan
Van Gucht, Dirk
Wijsen, Jef
Wu, Yuqing
Issue Date: 2013
Citation: 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.
URI: http://hdl.handle.net/1942/16500
Link to publication: http://www.vldb.org/pvldb/vol7/p25-gyssens.pdf
ISSN: 2150-8097
Category: A2
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Main article286.75 kBAdobe PDF

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