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 sufices for query answering.
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 diferent 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 constraint 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 diferent 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 “representative” set of founded updates for EAICs, called universal, which sufices for query answering.
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.
1Other minimality criteria and update operations, such as value updates [
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 update 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 [
• A repair ℛ() is founded if ℛ 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 [
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 [
Syntax. We are now going to present an extension of AICs, that let us define AICs with existentially 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, |= if ̸|= , 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 if it is an update for ⟨, Σ[ ℛ]⟩, and () a repair ℛ() is founded if ℛ is a founded.
The introduction of existentially quantified variables increases the expressivity of active integrity constraints. The price to pay is that, diferently 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 homomorphism ℎ 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 [
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.
Diferent interesting results have been shown in [
The framework presented in this paper finds application in several domains from diferent ifelds, including knowledge representation and reasoning and databases. As EAICs generalize classical production rules, they can be used as a basic representation mechanism useful in diferent 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 diferent 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. [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 ontologymediated 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.