Difference between revisions of "Vol-3194/paper34"
Jump to navigation
Jump to search
(edited by wikiedit) |
(modified through wikirestore by wf) |
||
Line 1: | Line 1: | ||
− | + | =Paper= | |
{{Paper | {{Paper | ||
− | | | + | |id=Vol-3194/paper34 |
+ | |storemode=property | ||
+ | |title=Active Integrity Constraints with Existential Quantification | ||
+ | |pdfUrl=https://ceur-ws.org/Vol-3194/paper34.pdf | ||
+ | |volume=Vol-3194 | ||
+ | |authors=Marco Calautti,Luciano Caroprese,Sergio Greco,Cristian Molinaro,Irina Trubitsyna,Ester Zumpano | ||
+ | |dblpUrl=https://dblp.org/rec/conf/sebd/CalauttiCGMTZ22 | ||
}} | }} | ||
+ | ==Active Integrity Constraints with Existential Quantification== | ||
+ | <pdf width="1500px">https://ceur-ws.org/Vol-3194/paper34.pdf</pdf> | ||
+ | <pre> | ||
+ | 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. | ||
+ | � | ||
+ | </pre> |
Revision as of 17:55, 30 March 2023
Paper
Paper | |
---|---|
edit | |
description | |
id | Vol-3194/paper34 |
wikidataid | →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. �