Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/29069
Title: | Calculi for symmetric queries | Authors: | GYSSENS, Marc HELLINGS, Jelle Paredaens, Jan Van Gucht, Dirk Wijsen, Jef Wu, Yuqing |
Issue Date: | 2019 | Publisher: | ACADEMIC PRESS INC ELSEVIER SCIENCE | Source: | JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 105, p. 54-86 | Abstract: | Symmetric queries are introduced as queries on a sequence of sets of objects the result of which does not depend on the order of the sets. An appropriate data model is proposed, and two query languages are introduced, QuineCALC and SyCALC. They are correlated with the symmetric Boolean respectively relational functions. The former correlation yields an incidence-based normal form for QuineCALC queries. More generally, we propose counting only queries as those SyCALC queries the result of which only depends on incidence information, and characterize them as quantified Boolean combinations of QuineCALC queries. A normal form is proposed for them too. It turns out to be undecidable whether a SyCALC query is counting-only, but decidable whether a counting-only query is a QuineCALC query. Finally, some classical decidability problems are considered which are shown to be undecidable for SyCALC, but decidable for QuineCALC and counting-only queries. (C) 2019 Elsevier Inc. All rights reserved. | Notes: | [Gyssens, Marc; Hellings, Jelle] Hasselt Univ, Martelarenlaan 42, B-3500 Hasselt, Belgium. [Hellings, Jelle] Univ Calif Davis, Dept Comp Sci, Exploratory Syst Lab, Davis, CA 95616 USA. [Paredaens, Jan] Univ Antwerp, Middelheimlaan 1, B-2020 Antwerp, Belgium. [Van Gucht, Dirk] Indiana Univ, Sch Informat Comp & Engn, 919 E 10th St, Bloomington, IN 47408 USA. [Wijsen, Jef] Univ Mons, Pl Parc 20, B-7000 Mons, Belgium. [Wu, Yuqing] Pomona Coll, 185 E 6th St, Claremont, CA 91711 USA. | Keywords: | Bag of sets data model; Symmetric query; Two-sorted first-order logic; Two-sorted relational calculus; Symmetric Boolean function; Symmetric relational function; Counting-only query; Normal form; Expressibility; Satisfiability;Bag of sets data model; Symmetric query; Two-sorted first-order logic; Two-sorted relational calculus; Symmetric Boolean function; Symmetric relational function; Counting-only query; Normal form; Expressibility; Satisfiability | Document URI: | http://hdl.handle.net/1942/29069 | ISSN: | 0022-0000 | e-ISSN: | 1090-2724 | DOI: | 10.1016/j.jcss.2019.04.003 | ISI #: | 000474332400003 | Rights: | 2019ElsevierInc.Allrightsreserved | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2020 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
gyssens 1.pdf Restricted Access | Published version | 890.42 kB | Adobe PDF | View/Open Request a copy |
sycalcpaper.pdf | Peer-reviewed author version | 583.29 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
1
checked on Oct 12, 2024
Page view(s)
124
checked on Sep 7, 2022
Download(s)
154
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.