Marcin Przybyłko

Tomasz Gogacz, Filip Murlak, Marcin Przybyłko et al.

Aiming to harmonise finite and infinite model reasoning, we initiate the study of partially finite models, where the reasoning task comes with a formula that specifies a part of the model that must be finite. We focus on the problem of partially finite query entailment in description logics (DLs): given a knowledge base (KB), a query, and a distinguished concept, decide whether the query holds in all models of the KB that interpret the distinguished concept as a finite set. To break the ground, we work with the DL S, an extension of the basic DL ALC with transitive roles, which is one of the simplest cases where finite and infinite query entailment diverge. Generalising previous results on the finite and infinite cases, we show that also partially finite entailment of conjunctive queries is in 2-exptime for S. The solution involves sophisticated infinite model surgery and goes far beyond combining the arguments for the two special cases. As a direct application, we show how the problem of query containment in the presence of closed predicates can be solved by reduction to partially finite query entailment.

Nofar Carmeli, Carsten Lutz, Marcin Przybyłko

We study the limits of linear time evaluation of conjunctive queries under constraints expressed as tuple-generating dependencies (TGDs), across several modes of query evaluation: single-testing, all-testing, counting, lexicographic direct access, and enumeration. While full classifications seem far beyond reach, we propose an approach that, for some evaluation modes and classes of TGDs, makes it possible to lift known dichotomies from the unconstrained setting. In particular, our approach applies to all mentioned evaluation modes except enumeration, when the constraints fall into one of two classes: non-recursive sets of TGDs in which every TGD uses at most binary relation symbols in the head or has at most two frontier variables; and frontier-guarded full TGDs. We further provide a collection of examples showcasing the challenges that arise for enumeration and for less restrictive classes of TGDs.

Quentin Manière, Marcin Przybyłko

Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or $\infty$, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over $\mathcal{ALCIF}$ ontologies: they are essentially the subsets of $\mathbb{N} \cup \{ \infty \}$ closed under addition. For most sublogics of $\mathcal{ALCIF}$, we show that possible spectra enjoy simpler shapes, being $[ m, \infty ]$ or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of $\mathcal{ALCIF}$. We also study the data complexity of computing the proposed effective representation and establish the $\mathsf{FP}^{\mathsf{NP}[\log]}$-completeness of this task under several settings.