In ontology-based query answering a user query is typically evaluated over instances containing both known and anonymous individuals. In this context, the algebraic notion of isomorphism is relevant in many application scenarios, such as the so-called parsimonious chase. Two atoms are isomorphic if there is a bijection among them that, in addition, is the identity on the known individuals. A naive upper bound on the maximum cardinality of any instance containing non-isomorphic atoms is well-known from the literature. However, there are cases in which this bound is far from being optimal. This paper generalizes Bell numbers to provide a tight bound in the above setting. The main result is also relevant in classical databases by characterizing the family of non-equivalent atomic queries.
Ontology-Based Query Answering (OBQA) consists in querying databases by taking ontological knowledge into account. It is a fascinating research topic deeply studied not only in database theory [1,13], but also in arti cial intelligence [6,5,11] and in logic [2,3,12]. Moreover, OBQA is strictly related to others important application areas such as data integration [21], data exchange [9], and consistent query answering [23,24]. In particular, OBQA is the problem of answering a query q against a logical theory consisting of an extensional database D paired with an ontology . The goal is to nd certain answers to q, i.e. the query must be true in every possible model of the theory [20,7]. Here, we focus on ontologies expressed via existential rules, also known as tuple generating dependencies (TGDs) or datalog9 rules. They are at the core of Datalog [14], an emerging family of ontology languages, which collects the basic decidable Copyright c 2019 for the individual papers by the papers' authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy. classes of TGDs, and generalizes several ontology speci cation languages such as Description Logics (DLs) [10]. Indeed, datalog9 generalizes the well-known language Datalog [16] with existential quanti cation in the head. OBQA can be reduced to the problem of answering q over a universal model U that can be homomorphically embedded into every other model of the logical theory. A way to compute a universal model is to employ the so called chase procedure. Starting from D, the chase \repairs" violations of rules by repeatedly adding new atoms {introducing fresh values, called nulls, whenever required by an existential variable{ until a xed point satisfying all rules is reached. Therefore, in the classical setting, the chase is sound and complete. But, unfortunately, the chase does not always terminates [17,18].
Recently, in [22] a new class of datalog9 ontologies, called Shy, has been singled out for existential rules. It enjoys a new semantic property called parsimony and results in a powerful and decidable class that combines positive aspects of di erent Datalog classes [4]. The parsimony property is based on the parsimonious chase (pchase) procedure that repairs violations of rules only if the (inferred) head atom can not be homomorphically mapped to any atom previously produced. For some classes of Datalog , the parsimony property is sound and complete with respect to atomic query answering. Moreover, the termination of the pchase is always guaranteed, and computational complexity has been studied [22]. Understanding the nature of the pchase procedure can lead to obtain practical improvements of existing implementations [22]. Indeed, so far, the research has been focused on establishing the termination of the pchase procedure, thus providing just a very rough upper bound of its maximal size, without any understanding of the relations between the logical theory and the atoms generated by the pchase. We ll this gap deepening this relevant connection. In particular, we need to understand what kind of atoms belong to the pchase. This has as side e ect and it is strictly related to count the number of atoms generated by the pchase. An immediate consequence of this better understanding of the chase leads to re-prove computational complexity results, as we improve the upper bounds previously identi ed in [22]. Indeed, these are very large, as they are aimed at demonstrating computational complexity, and not how many atoms can be produced by the chase.
In this paper, we present contents already set out and published in [8]. In particular, we provide an exact upper bound for the pchase. To this end, we exploit the notion of \equality type" de ned in [19], which we show to be strictly related to the form of non-isomorphic atoms of a given predicate. Then, by exploiting the notion of Bell numbers, counting the number of distinct partitions of a nite set, we compute an upper bound for the number of atoms generating by the pchase procedure and we show that there exists a family of ontologies for which the pchase can produce exactly the upper bound previously computed, so that it corresponds to the maximal number of atoms e ectively generated by the pchase procedure.
Finally, as a corollary, our estimation of the maximum cardinality of any instance containing non-isomorphic atoms also provides a tight bound on the maximum number of non-equivalent atomic queries over a given relation, where two queries are considered equivalent if they give the same answers on every database. 2
Throughout this paper we use the following notation. Let = C [ N [ V
the domain of the terms, consisting of the union of the three countably in nite
domains of constants, nulls and variables, respectively. We write ' to denote
a null; X a variable; a an atom, that is an expression of the form p(t), where
p = pred(a) is a predicate, t = t1; : : : ; tk is a tuple of terms, k = arity(a) is
the arity of a or p, and a[i] is the i-th term of a. Moreover, const(a) (resp.,
vars(a)) is the set of constants (resp., variables) occurring in a. The set of
predicates is denoted by R. Let T a nonempty subset, then the set of all
atoms that can be formed with predicates of R and terms from T is denoted
by base(T ). Moreover, any subset of base( C [ N ) constitutes an instance
I, and whenever I base( C ), then it is also called database. A substitution
is a total mapping s : ! . Let 1 and 2 be two structures containing
atoms. An homomorphism h : 1 ! 2 is a substitution such that: (
C , then h(c) = c; (ii) if ' 2 N , then h(') 2 C [ N ; (iii) h(
Given an instance I, we say that a rule r is satis ed by I if whenever there is a homomorphism h : body(r) ! I, there is a homomorphism h0 hjvars(body(r)) s.t. h0 : head(r) ! I. An instance I is a model of a program P if each rule of dep(P ) is satis ed by I, and data(P ) I. A ring homomorphism for r and I is any homomorphism h : body(r) ! I s.t. h = hjvars(body(r)). The re of r via h produces the atom f ire(r; h) = (h(head(r))), where = jvars(h(head(r))) (i.e., it replaces each existential variable of r with a di erent fresh null). Given a ring homomorphism h for a rule r and an instance I, we say that the pair hr; hi satis es the parsimonious re condition w.r.t. an instance I0 I if there is no homomorphism from fh(head(r))g to I0. Finally, given a datalog9 program P , the parsimonious chase (pchase) of P (pchase(P )) is constructed as follows. We start from I0 = data(P ) and create a copy of it in I. Then, for each r in dep(P ), for each unspent ring homomorphism h for the pair hr; Ii we add the f ire(r; h) to I0 if hr; hi satis es the parsimonious re condition w.r.t. I0. If I 6= I0, we create a new copy of I0 and repeat the previous steps. Otherwise, we return I.
In this section, we introduce some basic notions that will help us to nd a tight upper bound for the pchase. We highlight a main property of the pchase, based on isomorphic atoms, a crucial notion in several Datalog classes [15]. Theorem 1. Given a program P , pchase(P ) does not contain isomorphic atoms. Proof. Assume, by contradiction, that there are two isomorphic atoms a and a0 in pchase(P ). Thus, there is a homomorphism h from fag to fa0g s.t. h 1 is a homomorphism from fa0g to f g
a . W.l.o.g. assume that a 2 I, for some I generated during the pchase procedure. As a0 2 pchase(P ), then there is a rule r, an instance I0 I, and an unspent ring homomorphism h0 for hr; I0i, s.t. f ire(r; h0) = a0, against the fact that h 1 is a homomorphism from fh0(head(r))g to I0. Indeed, (h 1 )(h0(head(r)) = h 1( (h0(head(r)) = h 1(f ire(r; h0)) = h 1(a0) = a 2 I I0. tu To provide a precise upper bound for the number of steps execute by the pchase, we introduce the concept of type that is equivalent to the notion of equality type de ned in.
De nition 1 (Type). Let m be a positive integer, S an arbitrary partition of f1; : : : ; mg, C a set with jCj jSj, and f : C ! S an injective map. We de ne the type of S; C and f as the family of sets T (S; C; f ) = s [ f 1(s) j s 2 S . Example 1. Let m = 6, C = fc1; c2g, and let S = f1; 2g; f3; 6g; f4g; f5g be a partition of f1; : : : ; 6g. Consider the injective map f : C ! S such that f (c1) = f3; 6g and f (c2) = f5g. Then, T (S; C; f ) = f1; 2g; f3; 6; c1g; f4g; f5; c2g . Fixed an integer m, our aim is to count the number of all possible types that can be generated from any partition of the set f1; : : : ; mg, by varying C on a superset D of a xed size d. In order to do this, we resort to the Bell number Bn, that is the number of ways to partition a set of n labeled elements. Theorem 2. Let m 2 N, D a nite set of size d > 0, and Bn the n-th Bell number. Hence, the number of all possible types generated from all the partitions of the set f1; : : : ; mg and all subsets of D is given by md = Phm=0 mh dhBm h. Proof Sketch. Recall that, given two sets A and B with jAj = jBj = , the number of injective maps from A to B is ( ! )! . Then, xed a partition S of f1; :::; mg with jSj = s, the number of injective maps from any subset C D to S, with jCj = c s, is (s s!c)! , while the number of subsets of size c is dc . Thus, the number of all possible types for the xed partition S is Pcm=i0nfs;dg dc (s s!c)! . Hence, the number of types generated from all the partitions of the set f1; : : : ; mg and all subsets of D is given by Pm c=0 c (s s!c)! ; where S(m; s) s=1 S(m; s) Pminfs;dg d is the Stirling number counting the number of partitions of size s on m elements. It can be shown that it is equivalent to md. tu Taking advantage of the notion of type, we can provide a new representation of an arbitrary atom.
De nition 2 (Atom Type). Given an atom a = p(t) of arity m, we de ne the type of the atom a as Ta = T (S; C; f ), where C = const(a); S = fn j a[n] = tig j i = 1; : : : ; m ; and f : C ! S such that f (c) = fn j a[n] = cg. Hence, the type of an atom a has the form Ta = f (t1); : : : ; (tm)g, where is such that (ti) = fn j n 2 f1; : : : ; mg ^ a[n] = tig [ ftig if ti is a constant, and (ti) = fn j n 2 f1; : : : ; mg ^ a[n] = tig otherwise. Intuitively, the type of an atom is formed by the sets of positions where a term occurs, by highlighting positions where constants occur.
Example 2. Let a = p1('1; '3; '2; '1) and b = p2(c; '1; d; c; '2; '2; '1). Then, Ta = f1; 4g; f2g; f3g and Tb = f1; 4; cg; f2; 7g; f3; dg; f5; 6g . Theorem 3. Let a = p(t1; : : : ; tk) and a0 = p(t01; : : : ; t0k) be two atoms. Then, a and a0 are isomorphic if, and only if, pred(a) = pred(a0) and Ta = Ta0 . Proof. Let us consider two atoms a and a0. If pred(a) 6= pred(a0) or arity(a) 6= arity(a0), then of course can not exists an isomorphism between them. Hence, we can take for granted that the two atoms have same predicate and arity. [)] Assume that there is an isomorphism between a and a0, i.e., there is a homomorphism h : fag ! fa0g s.t. h(ti) = t0i; i = 1; : : : ; k and s.t. h 1 : fa0g ! fag is a homomorphism. Let Ta = f (t1); : : : ; (tk)g and Ta0 = f 0(t1); : : : ; 0(tk)g. We claim that (ti) = (t0i), for i = 1; : : : ; k. Assume that (ti) (t0i), and let n 2 (ti) \ N, so that a[n] = ti: Therefore, we have that t0i = h(ti) = h(a[n]) = h(a)[n] = a0[n]. Hence, n 2 (t0i). Moreover, if n = c is a constant, by de nition of homomorphism, we have c 2 (ti) ) ti = c ) t0i = h(ti) = ti = c ) c 2 (t0i). The reverse inclusion can be easily proved by replacing h by h 1. [(] Let us assume that Ta = Ta0 . Let h : fag ! fa0g be s.t. h(ti) = t0i. First, we prove that h is a homomorphism. Let ti = c be a constant. Suppose that c 2 (ti), then by assumption c 2 (t0i), hence t0i = c. It remains to be shown that h is also injective. Let t0i = t0j . Then, (t0i) = (t0j ) ) (ti) = (tj ) ) ti = tj . tu Now, we are able to provide an upper bound for the maximum number of atoms generating by the pchase procedure.
Theorem 4. Let P be a program with arity(P ) = w, jconst(P )j = d, and lm the number of predicates in pred(P ) of arity m. Then, jpchase(P )j Pwm=0 lm md. Proof. By Theorem 2 and Theorem 3, the total number of non isomorphic atoms over pred(P ) and const(P ) [ N is given by Pwm=0 lm md. Moreover, by Theorem 1, we know that pchase(P ) does not contain isomorphic atoms. Hence, jpchase(P )j Pwm=0 lm md. tu Let wd be the upper bound in Theorem 4. To show that it is also tight, we introduce an ordering on types that will allow us to build a program with a sequence of ring homomorphisms generating a pchase of size exactly wd . De nition 3 (Type ordering). Let T = T (S; C; f ) and T 0 = T (S0; C0; f 0). Then, T precedes T 0, if (i) jCj < jC0j, or (ii) jCj = jC0j and jSj > jS0j. Intuitively, such a program should have a rule for each possible atom tag, whenever constants are allowed in the rules. Otherwise, we need a predicate to collect all constants of the database. To better understand our idea, we give an example of such a program before we provide the formal result.
Example 3. Let C be a nite set of constant, and P be a program such that data(P ) = ft(c1); t(c2)g, and dep(P ) is given by We build pchase(P ) by starting from rules in the rst column from top to bottom. For each rule r in this ordering, we consider all ring homomorphism h for r. E.g., the rule in bold produces the atoms fp('1; '2; c1); p('3; '4; c2)g. Thus, tahned njpucmhbaesre(oPf )ajt=om4s0 w=ith32p+red12ic.ate p generated by the pchase will be 37 = 32, Theorem 5. Let w be a positive integer, D a set of constants of size d, and as above. Then, there is a family Pw of programs s.t. jpchase(Pw)j = wd . Proof Sketch. We build a program Pw having two predicates p (of arity w) and t (of arity 1). We set data(Pw) = ft(c) j c 2 Dg, and de ne dep(Pw) as follows. Given a partition Si = f 1; : : : ; ng of w, where n = jSij, we construct a rule ri with an empty body, by adding X1; : : : ; Xn existential variables so that j = fk j p[k] = Xj ; k 2 [w]g. Now, xed a rule ri with n > 1 existential variables, we produce n 1 blocks of rules as follows. We translate j existential variables into universal ones, by adding j atoms over predicate t in the body. Hence, we construct nj rules. Then, we add the rules p(X1; : : : ; Xw) = t(X1); : : : ; t(Xw), and 9Xt(X). Finally, we remove all rules having in the head more than one rseepqueaetnecde oufnivwdersdal vrianrgiahbolem. oTmoorpprohvisemtsh. aTtojepacchhasrue(lePwr)inj =dep(Pwd w,)wwe eparsosvoicdieatae uniquely an atom g(head(r)), where g maps existential variables to fresh nulls, and universal variables to a xed constant. The type ordering on the atoms gives an ordering on the rules, and so to the sequence of ring homomorphisms. d w
In this work, we identi ed the maximal number of distinct atoms generable by the pchase procedure. In particular, md improves the bound given in [22], that is (d + m)m. In particular, dm md (d + m)m. Since in the OBQA context, normally, d is much bigger than m, it could seem that the e ort to nd such a precise upper bound can be useless for practical purposes. However, this is not the case, as shown in the paper. Indeed, the search for a precise upper bound led to identify the fundamental notions of type and type ordering that highlighted some qualitative characteristics of the pchase. Moreover, there could be other contexts where m is much bigger than d (think for example to scenarios where tuples encode strings over a certain alphabet, as in complexity proofs based on Turing Machine simulation). In this cases, our bound represents a concrete improvement. As future work, we plan to extend the pchase condition to rules with a complex head, and to compute the maximal number of distinct atoms generable in this case. Then, we will try to analyze the orderings of re homomorphisms in the generation of the pchase to understand if we can identify a sort of best ordering that minimizes the number of atoms produced. Finally, we will try to apply this metodology to give exact estimations of others chase versions. 11. Baget, J., Leclere, M., Mugnier, M., Salvat, E.: On rules with existential variables:
Walking the decidability line. Artif. Intell. 175(
In: ICDE. pp. 2{13. IEEE Computer Society (2011)
20. Imielinski, T., Lipski, W.: Incomplete information in relational databases. J. ACM
31(
ACM (2002)
22. Leone, N., Manna, M., Terracina, G., Veltri, P.: E ciently computable Datalog9
programs. In: Proc. of KR (2012)
23. Manna, M., Ricca, F., Terracina, G.: Consistent query answering via ASP from
di erent perspectives: Theory and practice. TPLP 13(