Vol-3194/paper34
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3194/paper34 |
| wikidataid | Q117344917→Q117344917 |
| title | Active Integrity Constraints with Existential Quantification |
| pdfUrl | https://ceur-ws.org/Vol-3194/paper34.pdf |
| dblpUrl | https://dblp.org/rec/conf/sebd/CalauttiCGMTZ22 |
| volume | Vol-3194→Vol-3194 |
| session | → |
Active Integrity Constraints with Existential Quantification
Active Integrity Constraints with Existential
Quantification
Marco Calautti1 , Luciano Caroprese2 , Sergio Greco3 , Cristian Molinaro3 ,
Irina Trubitsyna3 and Ester Zumpano3
1
DISI, University of Trento, Italy
2
ICAR-CNR, Italy
2
DIMES, University of Calabria, Italy
Abstract
We present the framework of Existential Active Integrity Constraints (EAICs) introduced in [1]. EAICs are
a powerful extension of Active Integrity Constraints (AICs), which allow us to express a wide range of
constraints used in databases and ontological systems. Specifically, the paper discusses a new definition
of founded updates for AICs, presents syntax and semantics for EAICs, and a “representative” set of
founded updates for EAICs, called universal, which suffices for query answering.
1. Introduction
The consistent query answering (CQA) framework is a principled approach to answer queries
over inconsistent databases. It was first proposed in [2], giving rise to flourishing research
activity (e.g., see [3, 4, 5, 6]). It relies on the notions of repair and consistent query answer.
Intuitively, a repair for a possibly inconsistent database is a consistent database that “minimally”
differs from the original one. In general, there may be multiple repairs for an inconsistent
database. The consistent (or certain) answers to a query over an inconsistent database are the
query answers that can be obtained from every repair.
Example 1. Consider the database schema consisting of two relations emp(Name, Dept) and
dept(Name), where the former stores information on employees and departments they work for,
and the latter stores all departments. Consider a referential integrity constraint stating that every
department occurring in the emp relation must appear in the dept relation too. This constraint can
be expressed through the following logical formula: ∀E ∀D [emp(E, D) ∧ ¬ dept(D) ⇒].
Consider now the database 𝐷 consisting of the facts emp(john, cs), emp(john, math), and
dept(math). Clearly, 𝐷 is inconsistent, as the cs department appearing in the emp relation
does not appear in the dept relation. A repair can be obtained by applying a minimal (under
set-inclusion) set of update operations to the original database. We consider only fact insertions
SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
$ marco.calautti@unitn.it (M. Calautti); luciano.caroprese@icar.cnr.it (L. Caroprese); greco@dimes.unical.it
(S. Greco); cmolinaro@dimes.unical.it (C. Molinaro); trubitsyna@dimes.unical.it (I. Trubitsyna);
zumpano@dimes.unical.it (E. Zumpano)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
�and deletions as admissible update operations.1 Therefore, there are two repairs: 𝐷1 , obtained by
inserting the fact dept(cs) into 𝐷, and 𝐷2 , obtained by deleting the fact emp(john, cs) from 𝐷.
The only consistent answer to the query asking for all departments’ names is math.
Although inconsistent databases can be repaired in different ways, in many applications it is
natural and desirable to express that only a restricted set of update operations can be performed
to restore consistency, which cannot be done with classical integrity constraints. Active integrity
constraints (AICs) [13] have been introduced to overcome such a limitation.
Example 2. Consider again the scenario of Example 1 and suppose that, when the integrity
constraint is violated, we want to restore consistency only by adding missing departments (and thus
avoid deleting facts of the emp relation). This behavior can be expressed by means of the following
active integrity constraint: ∀E ∀D [ emp(E, D) ∧ ¬ dept(D) ⇒ +dept(D) ].
The same constraint of Example 1 is defined on the left-hand side of ⇒, while on the right-hand
side the only admissible update operation is specified. Thus, only the insertion of dept(cs) can
be performed to restore consistency of 𝐷, and 𝐷1 is the only acceptable repair. As defined in the
following, inserting dept(cs) is a “founded” update, because the AIC above allows it, while deleting
emp(john, cs) is not a founded update, because the AIC above does not allow it.
Active integrity constraints allow users to express integrity constraints along with admissible
update operations. One limitation of AICs is that they do not allow existential quantification, and
thus do not allow users to formulate classical constraints such as foreign keys and more general
inclusion dependencies, which require existentially quantified variables to be expressed [14].
We can lift the idea of AICs (that is, to specify which update operations should be applied when
a constraint is violated) to Existential Active Integrity Constraints (EAICs), which generalize AICs
enabling users to express a wider class of integrity constraints commonly arising in practice.
Example 3. The EAIC: ∀E ∀D [emp(E, D) ∧ ∄C dept(D, C) ⇒ ∃Z +dept(D, Z)] defines a con-
straint stating that inconsistency must be resolved by adding missing departments to relation dept.
Importantly, EAICs lead to value invention because of existential variables, which is not the case
for AICs, and this poses different new issues—for instance, for a database containing only the fact
emp(john, cs), a city for the cs department needs to be invented.
In this paper we present syntax and semantics of EAICs, and show how to define a “represen-
tative” set of founded updates for EAICs, called universal, which suffices for query answering.
2. Preliminaries
We assume the existence of the following (pairwise disjoint) sets: predicates 𝒫, variables 𝒱, and
constants 𝒞. Each predicate is associated with an arity, which is a non-negative integer. A term
is either a constant or a variable.
1
Other minimality criteria and update operations, such as value updates [7, 8, 9, 10, 11], have been considered in the
literature. In this paper, we consider minimality under set-inclusion and insert/delete updates, which indeed are
the most common minimality criteria and repair primitives considered in the literature. When only deletions are
allowed, the set of operations is a minimal transversal of all minimal inconsistent subsets of the database [12].
� An atom is of the form 𝑝(𝑡1 , . . . , 𝑡𝑛 ), where 𝑝 is a predicate of arity 𝑛 and the 𝑡𝑖 ’s are terms.
We write an atom containing only constants also as 𝑝(𝑐), where 𝑐 is understood to be a sequence
of constants, and write 𝑝(𝑋) to refer to an atom whose terms are the variables 𝑋. A literal
is either an atom 𝐴 (positive literal) or its negation ¬𝐴 (negative literal). An update atom is
of the form +𝑎(𝑋) or −𝑎(𝑋), where 𝑎(𝑋) is an atom. Intuitively, a ground update atom
+𝑎(𝑐) (resp. −𝑎(𝑐)) states that 𝑎(𝑐) will be inserted into (resp. deleted from) the database.
The complementary literal of an update atom +𝑎(𝑋) (resp. −𝑎(𝑋)) is CompLit (+𝑎(𝑋))
= ¬ 𝑎(𝑋) (resp. CompLit(−𝑎(𝑋)) = 𝑎(𝑋)). For any set 𝒰 of update atoms, CompLit(𝒰) =
{CompLit(±𝑎(𝑋)) | ±𝑎(𝑋) ∈ 𝒰}. Logical formulae are built using literals and logical
connectives—the precise syntax will be defined later.
A term/atom/literal/formula is ground if it is variable-free. A formula 𝜙′ is a ground instance
of a formula 𝜙 if 𝜙′ can be obtained from 𝜙 by substituting every variable in 𝜙 with a constant.
We use ground (𝜙) to denote the set of all ground instances of 𝜙, and for a set of formulae Φ,
we define ground (Φ) = ∪𝜙∈Φ ground (𝜙).
Active Integrity Constraints. An active integrity constraint (AIC) 𝜎 is of the form:
⎡ ⎤
𝑚
⋀︁ 𝑛
⋀︁ 𝑞
⋁︁ 𝑝
⋁︁
∀𝑋 ⎣ 𝑏𝑖 (𝑋 𝑖 ) ∧ ¬ 𝑏𝑖 (𝑋 𝑖 ) ⇒ −𝑎𝑖 (𝑋 𝑖 ) ∨ +𝑎𝑖 (𝑋 𝑖 )⎦ (1)
𝑖=1 𝑖=𝑚+1 𝑖=1 𝑖=𝑞+1
where (i) 𝑛, 𝑝 > 0, (ii) the 𝑏𝑖 (𝑋 𝑖 )’s are atoms, (iii) the −𝑎𝑖 (𝑋 𝑖 )’s and +𝑎𝑖 (𝑋 𝑖 )’s are up-
date atoms, (iv) variables occurring in negative literals also occur in positive literals, and (v)
𝐶𝑜𝑚𝑝𝐿𝑖𝑡(ℎ𝑒𝑎𝑑(𝜎)) ⊆ 𝑏𝑜𝑑𝑦(𝜎), where ℎ𝑒𝑎𝑑(𝜎) (resp., 𝑏𝑜𝑑𝑦(𝜎)) denotes the right (resp., left)
hand side of ⇒.
For an AIC 𝜎, 𝑏𝑜𝑑𝑦 + (𝜎) and 𝑏𝑜𝑑𝑦 − (𝜎) denote the set of positive and negative atoms in
𝑏𝑜𝑑𝑦(𝜎), respectively. An AIC specifies both an integrity constraint (in the body) and the
actions to be performed (in the head) if the integrity constraint is violated. We use 𝑆𝑡(𝜎) to
denote the integrity constraint derived from 𝜎 by removing all the head update atoms. For a set
of active integrity constraints Σ, 𝑆𝑡(Σ) denotes the corresponding set of integrity constraints,
that is 𝑆𝑡(Σ) = {𝑆𝑡(𝜎) | 𝜎 ∈ Σ}. Furthermore, for any set of AICs Σ and set of ground update
atoms 𝒰, Σ[𝒰] denotes the set of AICs derived from 𝑔𝑟𝑜𝑢𝑛𝑑(Σ) by deleting head update atoms
not occurring in 𝒰 and AICs such that all head update atoms have been deleted.
We now present the semantics of AICs used in [1]. Given a database 𝐷 and a set of AICs Σ:
• A set ℛ of ground update atoms is an update for ⟨𝐷, Σ⟩ if it is an update for ⟨𝐷, 𝑆𝑡(Σ)⟩.
• An update ℛ for ⟨𝐷, Σ⟩ is founded iff it is an update for ⟨𝐷, Σ[ℛ]⟩.
• A repair ℛ(𝐷) is founded iff ℛ is a founded update.
The idea underlying the definition above is that the actions of an update must be determined
only by the AICs allowing those actions. Observe that the founded semantics guarantees that,
given a founded repair ℛ, for each update atom ±𝐴 ∈ ℛ there must be an AIC 𝜎 ∈ 𝑔𝑟𝑜𝑢𝑛𝑑(Σ)
such that ±𝐴 ∈ ℎ𝑒𝑎𝑑(𝜎) (otherwise ℛ is not minimal).
Although the definition introduced in [1] is different from that used in [13], we use the same
name since the former is a refinement of the latter, and its purpose is to overcome the problem
�of cyclic support, see [15]. Theorem 8 in [1] shows that every founded update according to the
current definition is also founded according to the definition given in [13].
The sets of all updates and founded updates for a database 𝐷 and a set of AICs Σ are denoted
as R(𝐷, Σ) and FR(𝐷, Σ) respectively. Clearly, FR(𝐷, Σ) ⊆ R(𝐷, Σ).
More details regarding AIC and their extensions can be found in [1, 13, 16]. The cer-
answers to a query 𝑄 on a database 𝐷 w.r.t. a set of AICs Σ are certain(𝑄, 𝐷, Σ) =
tain ⋂︀
𝑄(ℛ(𝐷)).
ℛ∈FR(𝐷,Σ)
3. Existential Active Integrity Constraints
Syntax. We are now going to present an extension of AICs, that let us define AICs with exis-
tentially quantified variables, allowing for more expressive integrity constraints, like inclusion
dependencies. The set of complementary literals of an update atom is redefined as follows:
• 𝐶𝑜𝑚𝑝𝐿𝑖𝑡(−𝑎(𝑋)) = {𝑎(𝑋)};
′ ′
• 𝐶𝑜𝑚𝑝𝐿𝑖𝑡(∃𝑍 + 𝑎(𝑋, 𝑍)) = {∄𝑌 𝑎(𝑋 , 𝑌 ) | ∃ 𝑠𝑢𝑏𝑠𝑡. 𝜗 𝑠.𝑡. 𝑎(𝑋, 𝜗(𝑌 )) = 𝑎(𝑋, 𝑍)}.
For any set 𝒰 of update atoms, CompLit(𝒰) = ∪±𝐴∈𝒰 CompLit(±𝐴).
Definition 1. An Existential Active Integrity Constraint (EAIC) is of the form:
⎡ ⎤
𝑚
⋀︁ 𝑛
⋀︁ 𝑞
⋁︁ 𝑝
⋁︁
∀𝑋 ⎣ 𝑏𝑖 (𝑋𝑖 ) ∧ ∄𝑍𝑖 𝑏𝑖 (𝑋𝑖 , 𝑍𝑖 ) ⇒ -𝑎𝑖 (𝑋𝑖 ) ∨ ∃𝑍𝑖 +𝑎𝑖 (𝑋𝑖 , 𝑍𝑖 )⎦
𝑖=1 𝑖=𝑚+1 𝑖=1 𝑖=𝑞+1 (2)
where (i) 𝑛, 𝑝 > 0, (ii) universal variables occurring in negative body literals also occur in positive
body literals, (iii) every existential variable occurs only in one update atom or negative body literal,
and (iv) for each ±𝐴 ∈ ℎ𝑒𝑎𝑑(𝜎), the condition 𝐶𝑜𝑚𝑝𝐿𝑖𝑡(±𝐴) ∩ 𝑏𝑜𝑑𝑦(𝜎) ̸= ∅ holds. □
Example 4. Consider two relations node(Id) and edge(Source, Dest, Weight) used to store
nodes and weighted edges of a graph, respectively.
For the EAIC 𝜎 : node(X1 ) ∧ node(X2 ) ∧ ∄(Y1 ,Y2 ) edge(X1 , Y1 ,Y2 ) ⇒ ∃Z1 +edge(X1 , X2 ,Z1 ),
we have 𝐶𝑜𝑚𝑝𝐿𝑖𝑡(∃Z1 +edge(X1 , X2 ,Z1 )) ∩ 𝑏𝑜𝑑𝑦(𝜎) = {∄(Y1 ,Y2 ) edge(X1 , Y1 ,Y2 )} =
̸ ∅.
A negative body literal ∄𝑍 𝑖 𝑏𝑖 (𝑋 𝑖 , 𝑍 𝑖 ) s.t. 𝑍 𝑖 is empty will be simply written as ¬ 𝑏𝑖 (𝑋 𝑖 ). For
an EAIC 𝜎, 𝑆𝑡(𝜎) denotes the constraint, called existential integrity constraint (EIC), obtained by
deleting all head atoms from 𝜎. For any set of EAICs Σ, we define 𝑆𝑡(Σ) = {𝑆𝑡(𝜎) | 𝜎 ∈ Σ}.
For ease of presentation (and w.l.o.g.), we assume that constants do not appear in EAICs.
Semantics. We use pground (𝜙) to denote the set of all partially ground instances of a formula
𝜙 obtained by replacing universally quantified variables with constants in all possible ways.
For a set of formulae Φ, pground (Φ) = ∪𝜙∈Φ pground (𝜙).
A database 𝐷 satisfies a partially ground conjunction of literals 𝜙 (denoted 𝐷 |= 𝜙), if
𝜙+ ⊆ 𝐷 and there is no substitution 𝜗 replacing existentially quantified variables in 𝜙 with
constants s.t. 𝜗(𝜙− ) ∩ 𝐷 ̸= ∅, where 𝜙+ and 𝜙− denote the sets of positive and negated atoms
in 𝜙, respectively. Thus, for any partially ground EIC 𝜎 of the form 𝜙 ⇒, as it expresses a
�denial constraint, 𝐷 |= 𝜎 iff 𝐷 ̸|= 𝜙, that is, the following condition holds: if body + (𝜎) ⊆ 𝐷,
then there is a substitution 𝜗 replacing existentially quantified variables with constants s.t.
𝜗(body − (𝜎)) ∩ 𝐷 ̸= ∅. Furthermore, 𝐷 satisfies an EIC 𝜎 if 𝐷 satisfies every partially ground
instance in pground (𝜎); 𝐷 satisfies an EAIC (or partially ground instance thereof) 𝜎 if it satisfies
𝑆𝑡(𝜎). Finally, 𝐷 satisfies a set of EAICs (or EICs) Σ if 𝐷 satisfies every 𝜎 ∈ Σ—we also say
that 𝐷 is consistent w.r.t. Σ. Updates and repairs for databases with EICs and EAICs can be
defined analogously to the cases of ICs and AICs, respectively.
Example 5. Consider the database schema consisting of two relations edge(Source, Dest) and
node(Id) storing edges and nodes of a graph. The EAIC 𝜎5 : node(X) ∧ ∄Y edge(X, Y) ⇒
−node(X) ∨ ∃Z +edge(X, Z) says that every node must have an outgoing edge. When this is not
the case either the node is deleted or an outgoing edge is added. The database 𝐷 = {node(a)}
is clearly inconsistent. Since the domain 𝒞 is infinite, 𝜎5 suggests an infinite number of ways to
repair the database, namely, by means of update atoms of the form {+edge(a, c)} with c ∈ 𝒞.
Notice that {−node(a)} is another possible way of restoring consistency.
For any set of EAICs Σ and set of ground update atoms 𝒰, Σ[𝒰] denotes the set of partially
ground EAICs derived from 𝑝𝑔𝑟𝑜𝑢𝑛𝑑(Σ) by first deleting every head update atom ±𝐴 for which
there does not exist a substitution 𝜗 such that 𝜗(±𝐴) ∈ 𝒰, and then deleting every EAICs
where all head update atoms have been deleted.
The definitions of founded update and founded repair are the same as those defined for AICs,
that is, for any database 𝐷 and set of EAICs Σ: (𝑖) an update ℛ is founded iff it is an update for
⟨𝐷, Σ[ℛ]⟩, and (𝑖𝑖) a repair ℛ(𝐷) is founded iff ℛ is a founded.
The introduction of existentially quantified variables increases the expressivity of active
integrity constraints. The price to pay is that, differently from the AIC setting, decidability of
query answering over knowledge bases with EAICs is no more guaranteed, in general. Example 5
showed that EAICs can admit an infinite number of updates, whereas other EAICs can admit
updates of infinite size (i.e., containing an infinite number of update atoms).
To restrict the number of repairs to be considered for query evaluation, we next introduce
the concepts of labeled null and universal repairs. A labeled null can be used as a placeholder
for any constant from 𝒞. Thus, in addition to the set of constants 𝒞, we assume the existence of
an infinite enumerable set of labeled nulls 𝒩 of the form ⊥𝑖 , where 𝑖 ∈ N is a natural number.
For any set of atoms 𝐷 with values in 𝒞 ∪ 𝒩 ∪ 𝒱, we use 𝒞(𝐷) (resp. 𝒩 (𝐷), 𝒱(𝐷)) to denote
the set of constants (resp. nulls, variables) occurring in 𝐷. For every two sets of atoms 𝐷1
and 𝐷2 over 𝑆, a homomorphism ℎ from 𝐷1 to 𝐷2 , denoted ℎ : 𝐷1 → 𝐷2 , is a mapping
from 𝒞(𝐷1 ) ∪ 𝒩 (𝐷1 ) ∪ 𝒱(𝐷1 ) to 𝒞(𝐷2 ) ∪ 𝒩 (𝐷2 ) ∪ 𝒱(𝐷2 ) such that:(i) ℎ(𝑐) = 𝑐, for every
𝑐 ∈ 𝒞(𝐷1 ); (ii) ℎ(⊥𝑖 ) ∈ 𝒞(𝐷2 ) ∪ 𝒩 (𝐷2 ), for every ⊥𝑖 ∈ 𝒩 (𝐷1 ); (iii) for every fact 𝑅𝑖 (𝑡¯) of 𝐷1 ,
we have that 𝑅𝑖 (ℎ(𝑡¯)) is a fact of 𝐷2 (where, if ¯𝑡 = (𝑎1 , ..., 𝑎𝑛 ), then ℎ(𝑡¯) = (ℎ(𝑎1 ), ..., ℎ(𝑎𝑛 ))).
A homomorphism that is the identity on 𝒞 ∪ 𝒩 (i.e., it maps variables only) is also called a
substitution, whereas a substitution whose image is 𝒞 ∪ 𝒩 (resp. 𝒞) is called a matcher (resp.
constant matcher). The concepts of homomorphism can be extended to (sets of) update atoms.
The new definitions of ground (update) atom, update and repair are given in the following. A
ground atom 𝐴 is of the form 𝑝(𝑡1 , . . . , 𝑡𝑛 ), where 𝑝 is an 𝑛-ary predicate and 𝑡1 , . . . , 𝑡𝑛 ∈ 𝒞 ∪𝒩 ;
we write it also as 𝑝(𝑡), where 𝑡 is understood to be a sequence of constants and labeled nulls.
Intuitively, 𝐴 represents all atoms 𝐵 = 𝑝(𝑐1 , . . . , 𝑐𝑛 ), with 𝑐1 , . . . , 𝑐𝑛 ∈ 𝒞, such that there
�exists a homomorphism from 𝐴 to 𝐵. A ground update atom is of the form +𝑝(𝑡) or −𝑝(𝑡),
where 𝑝(𝑡) is a ground atom. We use ±𝑝(𝑡) to refer to a generic ground update atom.
The semantics of a database 𝐷 with labeled nulls is usually given in terms of the set poss(𝐷)
of its possible worlds, that is, all databases that can be obtained from 𝐷 by replacing
⋂︀all nulls with
constants. The certain answers to a query 𝑄 over 𝐷 are certain(𝑄, 𝐷) = 𝑄(𝑊 ).
𝑊 ∈poss(𝐷)
The definitions of partially ground constraints remains the same. A database 𝐷 with labeled
nulls satisfies a partially ground EIC 𝜎 if the following condition holds: for every homomor-
phism ℎ from 𝑏𝑜𝑑𝑦 + (𝜎) to 𝐷 that maps nulls to constants, there is a constant matcher 𝜗 s.t.
𝜗(body − (𝜎)) ∩ ℎ(𝐷) ̸= ∅. The definitions of satisfaction of (sets of) EICs and EAICs remain
the same, whereas the definitions of coherent update atoms and update needs to be revised.
A set of ground update atoms 𝒰 is coherent if there are no two update atoms +𝑎(𝑡1 ), −𝑎(𝑡2 ) ∈ 𝒰
and a homomorphism ℎ s.t. 𝑎(ℎ(𝑡1 )) = 𝑎(ℎ(𝑡2 )). Let 𝒰𝑖 and 𝒰𝑗 be coherent sets of ground
update atoms. 𝒰𝑖 is more general than 𝒰𝑗 , denoted 𝒰𝑖 ⊒ 𝒰𝑗 , if there exists a homomorphism ℎ
from 𝒰𝑖 to 𝒰𝑗 . 𝒰𝑖 and 𝒰𝑗 are (homomorphically) equivalent, denoted 𝒰𝑖 ≡ 𝒰𝑗 , if 𝒰𝑖 ⊒ 𝒰𝑗 and
𝒰𝑗 ⊒ 𝒰𝑖 . For instance, {+edge(⊥1 , ⊥2 )} ⊒ {+edge(a, ⊥2 )} ⊒ {+edge(a, a)}, and the sets
{+edge(a, ⊥1 )}, {+edge(⊥2 , a)}, {−node(a)} are pairwise incomparable.
Definition 2 (Update). Given a database 𝐷 and a set of EICs Σ, an update for ⟨𝐷, Σ⟩ is a
coherent set of ground update atoms ℛ such that (i) ℛ(𝐷) |= Σ, and (ii) for every coherent set of
ground update atoms ℛ′ such that ℛ′ (𝐷) |= Σ if ℛ′ ⊒ ℛ, then also ℛ ⊒ ℛ′ holds. □
Observe that the previous definition coincides with the one provided in Section 2 when
applied to AICs, as update atoms contain only constants and ℛ ⊒ ℛ′ is equivalent to ℛ ⊆ ℛ′ .
Once we have revised the definition of coherent set of ground update atoms, update, founded
update atom, founded update and founded repair are defined analogously to the case of AICs.
The definition of certain answers has to consider all possible founded repairs for⋂︀⟨𝐷, Σ⟩ and, for
each founded repair, all its possible worlds. certain(𝑄, 𝐷, Σ) = 𝑄(𝑀 ).
ℛ∈FR(𝐷,Σ)∧𝑀 ∈poss(ℛ(𝐷))
Proposition 1 from [1] shows that certain query answering is undecidable in the presence of
EAICs. This result does not preclude the existence of interesting classes of EAICs for which the
problem of computing certain query answers is decidable. As for AICs, it might be the case that
there are no founded updates for a database and set of EAICs. Although the introduction of
nulls enlarges the number of (founded) updates, only a subset of these need to be considered in
computing certain answers. This idea is captured by a “universal set of founded updates”.
Definition 3 (Universal Set of Updates). Let 𝐷 be a database and Σ a set of EAICs. A uni-
versal set of updates 𝑆 is a minimal (w.r.t. ⊆) set of 𝑆-updates for ⟨𝐷, Σ⟩ s.t. for every update ℛ𝑗
for ⟨𝐷, Σ⟩ there is an 𝑆-update ℛ𝑖 ∈ 𝑆 s.t. ℛ𝑖 ⊒ ℛ𝑗 . □
Roughly speaking, a universal set of founded updates is a set of founded updates that is
representative of all founded updates.
Example 6. Consider the database and the EAIC of Example 5. The founded updates are ℛ0 =
{−node(a)}, every ℛ𝑖 = {+edge(a, ⊥i )}, for some 𝑖 ∈ N, and every ℛ𝑐 = {+edge(a, c)}, for
some 𝑐 ∈ 𝒞. The sets of the form {ℛ0 , ℛ𝑖 } are universal sets of founded updates, whereas the sets
of the form {ℛ0 , ℛ𝑐 }, for some 𝑐 ∈ 𝒞, are not.
� Different interesting results have been shown in [1]. To compute certain query answers, it
suffices to consider any universal set of founded updates. As a consequence, certain answers
can be computed by only considering the repairs obtained by taking any universal set of
founded updates. Also, for databases with EAICs and positive queries, certain answers can be
computed by resorting to the naive evaluation of [17]. Finally, since the universal set of founded
updates can be infinite, restrictions guaranteeing finiteness and the existence of at most one
representative founded update have been presented in [1].
4. Conclusions
The framework presented in this paper finds application in several domains from different
fields, including knowledge representation and reasoning and databases. As EAICs generalize
classical production rules, they can be used as a basic representation mechanism useful in
different contexts, such as automated planning, expert systems and action selection. Regarding
data integration, EAICs could be used to implement, using a unified framework, both dataset
merging and cleaning mechanisms and to enrich smart data exchange setting [18]. It would be
interesting to extend the EAIC language so as to express different kind of preferences, e.g., by
incorporating formalisms like CP-nets [19, 20, 21]. Since explaining query (non)entailment has
recently received increasing attention (e.g., see [22, 23, 24, 25, 26, 27, 28]), another interesting
direction for future work is to investigate notions of explanations in the EAIC framework.
Finally, because existential quantification generally leads to undecidability of reasoning tasks,
it would be interesting to see how techniques guaranteeing decidability developed for logic
programs (e.g., see [29, 30]) might be adapted to the EAIC framework.
References
[1] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential
active integrity constraints, Expert Syst. Appl. 168 (2021) 114297.
[2] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases,
in: PODS, 1999, pp. 68–79.
[3] M. Calautti, M. Console, A. Pieris, Counting database repairs under primary keys revisited,
in: PODS, 2019, pp. 104–118.
[4] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering
under inconsistency in datalog+/-, in: IJCAI, 2018, pp. 1921–1927.
[5] T. Lukasiewicz, E. Malizia, A. Vaicenavicius, Complexity of inconsistency-tolerant query
answering in Datalog+/– under cardinality-based repairs, in: AAAI, 2019, pp. 2962–2969.
[6] T. Lukasiewicz, E. Malizia, M. V. Martinez, C. Molinaro, A. Pieris, G. I. Simari, Inconsistency-
tolerant query answering for existential rules, Artif. Intell. 307 (2022) 103685.
[7] S. Greco, C. Molinaro, I. Trubitsyna, Computing approximate query answers over incon-
sistent knowledge bases, in: IJCAI, 2018, pp. 1838–1846.
[8] J. Wijsen, Database repairing using updates, ACM TODS 30 (2005) 722–768.
[9] S. Greco, C. Molinaro, Approximate probabilistic query answering over inconsistent
databases, in: ER, 2008, pp. 311–325.
�[10] S. Greco, C. Molinaro, Probabilistic query answering over inconsistent databases, Annals
of Mathematics and Artificial Intelligence 64 (2012) 185–207.
[11] S. Flesca, F. Furfaro, F. Parisi, Range-consistent answers of aggregate queries under
aggregate constraints, in: SUM, 2010, pp. 163–176.
[12] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, SIAM J. Comput. 47 (2018) 456–492.
[13] L. Caroprese, S. Greco, E. Zumpano, Active integrity constraints for database consistency
maintenance, IEEE TKDE 21 (2009) 1042–1058.
[14] A. Cali, G. Gottlob, T. Lukasiewicz, A general datalog-based framework for tractable query
answering over ontologies, Journal of Web Semantics 14 (2012) 57–83.
[15] L. Caroprese, M. Truszczynski, Active integrity constraints and revision programming,
Theory and Practice of Logic Programming 11 (2011) 905–952.
[16] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Consistent
query answering with prioritized active integrity constraints, in: IDEAS, 2020, pp. 3:1–3:10.
[17] T. Imielinski, W. Lipski Jr., Incomplete information in relational databases, J. ACM 31
(1984) 761–791.
[18] S. Greco, E. Masciari, D. Saccà, I. Trubitsyna, HIKE: A step beyond data exchange, in: ER,
2019, pp. 423–438.
[19] T. Lukasiewicz, E. Malizia, On the complexity of mcp-nets, in: D. Schuurmans, M. P.
Wellman (Eds.), AAAI, 2016, pp. 558–564.
[20] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
[21] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
Max and rank voting, Artif. Intell. 303 (2022) 103636.
[22] I. I. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavicius, Explanations for query answers
under existential rules, in: IJCAI, 2019, pp. 1639–1646.
[23] I. I. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Preferred explanations
for ontology-mediated queries under existential rules, in: AAAI, 2021, pp. 6262–6270.
[24] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under
inconsistency-tolerant semantics, in: IJCAI, 2022.
[25] I. I. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavicius, Explanations for ontology-
mediated query answering in description logics, in: ECAI, 2020, pp. 672–679.
[26] I. I. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Explanations for
negative query answers under existential rules, in: KR, 2020, pp. 223–232.
[27] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query
answering under existential rules, in: AAAI, 2020, pp. 2909–2916.
[28] L. Caroprese, I. Trubitsyna, M. Truszczynski, E. Zumpano, A measure of arbitrariness in
abductive explanations, Theory Pract. Log. Program. 14 (2014) 665–679.
[29] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Logic program termination analysis using
atom sizes, in: IJCAI, 2015, pp. 2833–2839.
[30] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Checking termination of logic programs
with function symbols through linear constraints, in: Proc. RuleML, 2014, pp. 97–111.
�