Technical Propositions for the paper "Conjunctive Query Containment with Safe Negation and TGD One-boundedness"

In the following, we present two technical propositions for the paper Conjunctive Query Containment with Safe Negation and TGD One-boundedness. The first proposition serves as a preliminary step toward the second, which is the one cited in the paper. Proposition. Given a tgd t , a database D and a ground atom a , we can reduce, in polynomial time, the problem of deciding ⟨t, D⟩ | = a to deciding whether ⟨t′, D′⟩ | = a′ where ⟨t′, D′⟩ | = b for some ground atom b∈ D′, and t′a tgd. Proof. Lets assume that our tgd t has the form P1 ( x1 ) ∧. . . ∧Pn ( xn ) →N ( x ), our database D = {d1 ( c1 ) , . . . , d|D| ( c|d| ) } , and a is of the form A ( ca ). The idea is to append an extra variable v1 in all the atoms of t , and append an extra constant (e.g., 1) in all the atoms of D and a . Once we have done so, we can pick, in essence, the freeze ( LHS ( t )) and add it into the database but appending a new different constant to its atoms (e.g., 2). In this way, the atoms whose last constant is 2 ensure that the chase generates, at least, some atom (in particular, the freeze(RHS(t) with a constant 2), and the atoms whose last constant is 1 keep track of the atoms that could be generated in the original tgd and database. In particular, lets build the tgd t′ as P1 ( x1, v1 ) ∧ . . . ∧Pn ( xn, v1 ) →N ( x, v1 ), where v1 is a new fresh variable; D′ as {di ( ci, 1) |di ( ci ) ∈D} ∪ {Pi ( xi[σ], 2) |Pi ( xi ) ∈LHS ( t )and σ replaces each variable xto a labelled null #x}; and a′as a(ca,1). It is easy to see that an atom b ( cb )is entailed in ⟨t, D⟩ iff ⟨t′, D′⟩ | = b ( cb, 1). Furthermore, ⟨t′, D′⟩ entails at least one atom (in particular, N ( x, 2) [σ] ). It is also easy to see that such reduction is polynomial. ◀ Proposition. Given a tgd t , a database D , and a ground atom a , we can reduce, in polynomial time, the problem of deciding whether ⟨t, D⟩ | = a to deciding whether ⟨t′, D′⟩ | = a′ , where t′ is a tgd, and D′shows that t′is not uniformly one-bounded. Proof. Lets assume that our tgd t has the form P1 ( x1 ) ∧. . . ∧Pn ( xn ) →N ( x ), our database D = {d1 ( c1, . . . , d|D| ( c|d| )) } , and a is of the form A ( ca ). In virtue of Proposition ?? , w.l.o.g., we can assume that ⟨t, D⟩entails, at least, some atom. The idea is to append four extra constants 1,2,3,4into the tgd atoms, and the atoms of D and a . Do note that, roughly speaking, this modification is harmless since it only appends the very same vector of constants to every atom. However, we now modify the tgd so that, instead of generating a new atom N ( x, 1 , 2 , 3 , 4), it generates a new atom N ( x, b, c, d, a ) provided that there is some atom N ( x′, a, b, c, d )in the database (that is, roughly speaking, we shift the four final constants one position to the left w.r.t. some other atom with the same predicate). The idea is that, if we provide an initial atom N ( 0, 2 , 3 , 4 , 1), the chase takes at least 3 chase-steps to generate an atom N ( c, 1 , 2 , 3 , 4). Furthermore, if such atom is not generated (because N ( c, 1 , 2 , 3 , 4) already appears in the database), do note that the chase will generate, at least, two atoms corresponding to the combinations 3 , 4 , 1 , 2and 4 , 1 , 2 , 3, which makes it not uniform one-bounded since it requires two chase-steps. In particular, lets build the tgd t′ as P1 ( x1, 1 , 2 , 3 , 4) ∧. . .∧Pn ( xn, 1 , 2 , 3 , 4) ∧N ( x′, a, b, c, d ) → N ( x, b, c, d, a ), where a, b, c, d , and x′ are new fresh variables; D′ as {di ( ci, 1 , 2 , 3 , 4) |di ( ci ) ∈ D}∪{N ( k, 2 , 3 , 4 , 1 } where k is a vector of constants not appearing in D ; and a′ is A(ca,1,2,3,4). Do note that, by hypothesis, the original ⟨t, D⟩ entails, at least, some atom N ( c ). Furthermore, by construction, ⟨t′, D′⟩generates the atoms N(c, 3,4,1,2) and N(c, 4,1,2,3) with two chase-steps. From here, it is easy to realise that any atom b ( cn )is entailed in ⟨t, D⟩ iff b ( cn, 1 , 2 , 3 , 4) is entailed in ⟨t′, D′⟩ . Do realise also that all this reduction is polynomial. ◀