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.