Home
Scholarly Works
First-Order Definable Counting-Only Queries
Conference

First-Order Definable Counting-Only Queries

Abstract

For several practical queries on bags of sets of objects, the answer does not depend on the precise composition of these sets, but only on the number of sets to which each object belongs. This is the case k = 1 for the more general situation where the query answer only depends on the number of sets to which each group of at most k objects belongs. We call such queries k-counting-only. Here, we focus on k$$k$$-SyCALC, k-counting-only queries that are first-order definable. As k$$k$$-SyCALC is semantically defined, however, it is not surprising that it is already undecidable whether a first-order query is in 1-SyCALC. Therefore, we introduce SimpleCALC-k$$k$$, a syntactically defined (strict) fragment of k$$k$$-SyCALC. It turns out that many practical queries in k$$k$$-SyCALC can already be expressed in SimpleCALC-k$$k$$. We prove that the k-counting-only queries form a non-collapsing hierarchy: for every k, there exist (k+1)-counting-only queries that are not k-counting-only. This result specializes to both SimpleCALC-k$$k$$ and k$$k$$-SyCALC. Finally, we establish a strong dichotomy between 1-SyCALC and SimpleCALC-k$$k$$ on the one hand and 2-SyCALC on the other hand by showing that satisfiability, validity, query containment, and query equivalence are decidable for the former two languages, but not for the latter one.

Authors

Hellings J; Gyssens M; Van Gucht D; Wu Y

Series

Lecture Notes in Computer Science

Volume

10833

Pagination

pp. 225-243

Publisher

Springer Nature

Publication Date

January 1, 2018

DOI

10.1007/978-3-319-90050-6_13

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743
View published work (Non-McMaster Users)

Contact the Experts team