Calculi for symmetric queries

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.

Jaar van publicatie:2019

Trefwoorden: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

BOF-keylabel:ja

IOF-keylabel:ja

BOF-publication weight:0.5

CSS-citation score:1

Auteurs:International

Authors from:Higher Education

Toegankelijkheid:Open