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.

Abstract. The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A central problem concerning the chase procedure is uniform (a.k.a. all-instances) chase termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is, in general, undecidable, it is natural to ask whether known well-behaved classes of TGDs ensure decidability. We focus on the main paradigms that led to robust TGD-based formalisms, namely guardedness and stickiness, that have been introduced in the context of knowledge-enriched databases. Although uniform chase termination is well understood for the oblivious version of the chase (2EXPTIME-complete for guarded, and PSPACE-complete for sticky TGDs), the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that uniform restricted chase termination under guarded single-head TGDs and sticky single-head TGDs is decidable in elementary time. In the case of guardedness, we provide a reduction to the satisfiability problem of monadic second-order logic over infinite trees of bounded degree, while for stickiness we provide a reduction to the emptiness problem of deterministic Büchi automata. Those reductions build on a series of technical results of independent interest related to the notion of fairness of the restricted chase, and the existence of critical databases that characterize nontermination of the restricted chase via databases of a certain form.

We propose a novel use of ontologies to aid the ondemand design of data-centric systems. By means of a process that we call focusing, a schema for a (possibly knowledge-enriched) database can be obtained semi-automatically from an existing ontology and a specification of the scope of the desired system.We formalize the inputs and outputs of focusing, and identify relevant computational problems: finding a schema via focusing, testing its consistency, and answering queries in the knowledge-enriched databases it produces. These definitions are independent from the ontology language. We then study focusing for selected description logics as ontology languages, and popular classes of queries for specifying the scope of the system. For several representative combinations, we study the decidability and complexity of the identified computational problems. As a by-product, we isolate (and solve) mixed variants of the classical satisfiability and entailment problems, where selected predicates are required to have finite extension, as well as the nullability problem, which is closely related to query emptiness.

We study the problem of finite entailment of ontology-mediated queries. Going beyond local queries, we allow transitive closure over roles. We focus on ontologies formulated in the description logics ALCOI and ALCOQ, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of unions of conjunctive queries with transitive closure. We also provide a matching lower bound by showing that finite entailment of conjunctive queries with transitive closure in ALC is 2EXPTIME-hard

We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIF extended with closed predicates. In particular, we present a polynomial-time translation from OMQs into Datalog with negation under the stable model semantics, the formalism that underlies Answer Set Programming. This is a novel and non-trivial result: the considered OMQs are not only non-monotonic but also feature a tricky combination of nominals, inverse roles, and role functionality. We start with atomic queries and then lift our approach to a large class of first-order queries where quantification is “guarded” by closed predicates. Our translation is based on a characterization of the query answering problem via integer programming, and a specially crafted program in Datalog with negation that finds solutions to dynamically generated systems of integer inequalities. As an important by-product of our translation, we get that the query answering problem is co-NP-complete in data complexity for the considered class of OMQs. Thus, answering these OMQs in the presence of closed predicates is not harder than answering them in the standard setting. This is not obvious as closed predicates are known to increase data complexity for some existing ontology languages.

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs ensure decidability. We consider here the main paradigms that led to robust TGD-based formalisms, that is, guardedness and stickiness. Although all-instances termination is well-understood for the oblivious chase, the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that all-instances restricted chase termination for guarded/sticky single-head TGDs is decidable in elementary time.

We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries (the latter under restriction to a single, transitive role).

This paper studies properties of entropy functions that are induced by groups and subgroups. We showed that many information theoretic properties of those group induced entropy functions also have corresponding group theoretic interpretations. Then we propose an extension method to find outer bound for these group induced entropy functions.

We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of the Red Spider method invented in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance Q0, Q= \Q1, Q2, ... Qk} such that the set Q of CQs does not determine CQ Q0 but finitely determines it. Finally, we claim that while Q0 is finitely determined by Q, there is no FO-rewriting of Q0, with respect to Q

We solve a well known, long-standing open problem in relational databases theory, showing that the conjunctive query determinacy problem (in its "unrestricted" version) is undecidable.

We consider sequences of vectors from ℕ d . Each coordinate of a vector can be reset or incremented by 1 with respect to the same coordinate of the preceding vector. We give an example of non-dominating sequence, like in Dickson’s Lemma, of length 2 2 θ( n) , what matches the previously known upper bound.

Abstract Regular groups and fields are common generalizations of minimal and quasi-minimal groups and fields, so the conjectures that minimal or quasi-minimal fields are algebraically closed have their common generalization to the conjecture that each regular field is algebraically closed. Standard arguments show that a generically stable regular field is algebraically closed. LetKbe a regular field which is not generically stable and letpbe its global generic type. We observe that ifKhas a finite extensionLof degreen, thenP(n)has unbounded orbit under the action of the multiplicative group ofL. Known to be true in the minimal context, it remains wide open whether regular, or even quasi-minimal, groups are abelian. We show that if it is not the case, then there is a counter-example with a unique nontrivial conjugacy class, and we notice that a classical group with one nontrivial conjugacy class is not quasi-minimal, because the centralizers of all elements are uncountable. Then, we construct a group of cardinality ω1with only one nontrivial conjugacy class and such that the centralizers of all nontrivial elements are countable.

We solve a problem, stated in [CGP10], showing that Sticky Datalog∃, defined in the cited paper as an element of the Datalog±project, has the finite controllability property. In order to do that, we develop a technique, which we believe can have further applications, of approximating Chase(D, T), for a database instance D and a set of tuple generating dependencies and datalog rules T, by an infinite sequence of finite structures, all of them being models of T and D.

Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog3 programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.