Repairing inconsistent knowledge bases is a task that has been assessed, with great advances over several decades, from within the knowledge representation and reasoning and the database theory communities. As information becomes more complex and interconnected, new types of repositories, representation languages and semantics are developed in order to be able to query and reason about it. Graph databases provide an efective way to represent relationships among data, and allow processing and querying these connections eficiently. In this work, we focus on the problem of computing preferred (subset and superset) repairs for graph databases with data values, using a notion of consistency based on a set of Reg-GXPath expressions as integrity constraints. Specifically, we study the problem of computing preferred repairs based on two diferent preference criteria, one based on weights and the other based on multisets, showing that in some cases it is possible to retain the same computational complexity as in the case where no preference criterion is available for exploitation.
Graph databases are useful in many modern applications where the topology of the data is as
important as the data itself, such as social networks analysis [
RPQs and its most common extensions (C2RPQs and NREs [
As in the relational case, it is common to expect that the data preserves some semantic
structure related to the world it represents. These integrity constraints can be expressed in graph
databases through path constraints [
When a database does not satisfy its integrity constraints, a possible approach is to search
for a ‘similar’ database that does satisfy the constraints. In the literature, this new database is
called a repair [
In the literature one can find diferent notions of repairs, among others, set-based repairs [
This work is organized as follows. In Section 2 we introduce the necessary preliminaries and notation for the syntax and semantics for our data-graph model as well as the definitions of consistency and diferent types of repairs. In Section 3 we develop two diferent proposals to assign preferences to repairs. The first one is based on the assignment of weights, and the second one is based on lifting an ordering over edges and data to multiset orderings. For both proposals we study the computational complexity of the problem of computing a preferred repair. Conclusions and future work directions are discussed in Section 4.
Fix a finite set of edge labels Σ and a countable (either finite or infinite enumerable) set of data values Σ (sometimes called data labels), which we assume non-empty and with Σ ∩ Σ = ∅. A data-graph is a tuple (, , ) where is a set of nodes, is a mapping from × to (Σ) defining the edges of the graph, and is a mapping from to the set of data values Σ.
Reg-GXPath expressions are given by the following mutual recursion:
,
,
:= c= | c̸= | ¬ | ∨ | ∧ | ⟨ ⟩ | ⟨ = ⟩ | ⟨ ̸= ⟩
:= | _ | a | a− | ∘ | ∪ | ∩ | * | | [ ] | ,
where c iterates over Σ and a iterates over Σ. Formulas like are called node expressions and
formulas like are called path expressions. The subset of Reg-GXPath called Core-GXPath is
obtained by allowing the Kleene star to be applied only to labels and their inverses (i.e. a− ).
The semantics of these languages are defined in [
J_K = {(, ) | (, ) ̸= ∅}
Ja− K = {(, ) | a ∈ (, )} J * K = the reflexive transitive closure of J K J ⋆ K = J K ⋆ J K for ⋆ ∈ {∘ , ∪, ∩} J K = × ∖ J K Jc=K = { ∈ | () = c}
We use ⇛ to denote the path expression ∪ , and ⇒ to denote the node expression ∨ ¬ . We also note a label a as ↓a in order to easily distinguish the ‘path’ fragment of the expressions. For example, the expression a[c=]a will be noted as ↓a [c=] ↓a. Naturally, the expression ∩ can be rewritten as ∪ while preserving the semantics. Something similar happens with the operators ∧ and ∨ for the case of node expressions using the ¬ operator. We define all these operators in this grammar since further on we will be interested in a fragment of Reg-GXPath called Reg-GXPath, which has the same grammar except for the and ¬ productions. Thus, in Reg-GXPath we will not be able to ‘simulate’ the ∩ operator unless it is present in the original Reg-GXPath grammar.
We will also denote by Reg-GXPath the subset of Reg-GXPath that only contains node expressions.
Consistency Given a specific database, we want node or path expressions to represent some structural property we expect to find in our data. This kind of Core-GXPath or Reg-GXPath expression works as an integrity constraint by defining semantic relations among our data. Formally, we define the notion of consistency in the following way: Definition 1 (Consistency). Let be a data-graph and = ∪ a set of restrictions, where consists of path expressions and of node expressions. We say that is consistent w.r.t. , denoted by |= , if the following conditions hold: (a) for all ∈ , we have that J K = , (b) for all ∈ , we have that J K = × . Otherwise, we say that is inconsistent w.r.t. .
In the rest of the paper, we will simply say that is (in)consistent whenever the restriction set is clear from the context.
Example 2. Consider the film database from Figure 1, where we have nodes representing people from the film industry (such as actors or directors) and others representing movies or documentaries.
If we want to make a cut from that graph that preserves only actors who have worked with Philip Seymour Hofman through a film by Paul Thomas Anderson, then we want the following formula to be satisfied: = ⟨↓type [=]⟩ ⇒ ⟨↓acts_in ⟨↓directed_by [Anderson=]⟩ ↓−acts_in [Hofman =]⟩. acts_in type n i _ s t c a Actor type Hofman
type
Joaquin Phoenix acts_in Margot Robbie type
Anderson directed_by Babylon type Film
Notice that is not satisfied in the depicted data-graph, since Robbie did not work with Hofman in a film directed by Anderson, hence we do not have consistency with respect to { }. Observe that the restriction also applies to Hofman, thus it is required that he participates in at least one film by Anderson in order to satisfy the constraint.
Repairs If a graph database is inconsistent with respect to a set of restrictions (i.e. there is a path expression or node expression in that is not satisfied), we would like to compute a new graph database ′ consistent with respect to that minimally difers from . This new database ′ is usually called a repair of with respect to , following some formal definition for the semantics of ‘minimal diference’.
Here we consider set repairs, in which the notion of minimal diference is based on sets of
nodes and edges. While we could provide a notion of distance between arbitrary data-graphs
via an adequate definition of symmetric diference, it has been the case that the complexity of
ifnding such repairs is quite high, so it is common to consider set repairs where one graph is
obtained from the other by only adding or only deleting information [
We say that a data-graph = (, , ) is a subset of a data-graph ′ = ( ′, ′, ′) (written as ⊆ ′) if and only if ⊆ ′ and for all , ′ ∈ it happens that (, ′) ⊆ ′(, ′) and () = ′(). In this case, we also say that ′ is a superset of . Definition 3 (Subset and superset repairs). Let be a set of restrictions and a data-graph. We say that ′ is a subset repair (resp. superset repair) or ⊆ -repair (resp. ⊇ -repair) of if: (a) ′ |= , (b) ′ ⊆ (resp. ′ ⊇ ), and (c) there is no data-graph ′′ such that ′′ |= and ′ ⊂ ′′ ⊆ (resp. ′ ⊃ ′′ ⊇ ). We note the set of subset (resp. superset) repairs of with respect to as ⊆ -(, ) (resp. ⊇ -(, )).
Example 4. In Example 1, by deleting the node with value Margot Robbie we obtain a ⊆ -repair of the graph database.
Preferences Now we introduce the two preference criteria that we will use to induce orderings
on the set of repairs. In the manner done in [
When considering a way to select one among various possible subset or superset repairs, one approach is to consider that diferent edge labels and data values are prioritized diferently by being assigned diferent weights. These weights can be aggregated to obtain a measure of the weight of a whole data-graph, and this aggregated value can then be compared for all the possible repairs to obtain a preferred repair based on the natural ordering of non-negative integers.
Definition 6 (Weight-based preferences). Given a weight function , we define that 1 < 2 if (1) < (2).
If 1 < 2, we say that 1 is -preferred to 2 in the context of superset repairs, while we say that 2 is -preferred to 1 in the case of subset repairs. We say that is -preferred if is <-minimal for superset (resp. <-maximal for subset).
Example 7. Consider a context where data-graphs represent physical networks, and where edges represent two diferent quality levels of connection (e.g. varying robustness, resistance to physical attacks) which we call ↓low and ↓high. Let = { _, 2→} be a set of restrictions, where _ = _* 2→ =↓low↓low⇛↓high↓low ∪ ↓low↓high ∪ ↓high↓high ∪ ↓high ∪ ↓low .
_ expresses the notion of directed connectivity, and 2→ establishes that if a node can be reached by two low-quality edges, then it is also possible to reach it by a ‘good’ path. That is, it can be reached in either only one step, or in two steps but using at least one high-quality edge.
We could consider a weight function that attempts to represent the costs of building nodes and connections in this network. For example, it could assign a uniform weight to all data values () = 20, a low cost for low-quality connections (↓low) = 1, and higher costs for high-quality connections (↓high) = 5.
Now, given a data-graph that does not satisfy the restrictions, a -preferred superset repair can be interpreted as the most cost-efective way of making a superset of the network that satisfies the restrictions while minimizing the costs given by . For a full example, see Figure 2.
The weight function (over Σ and Σ) is considered fixed in general, and it should be an ‘easy’ function to compute. That is, given a reasonable encoding for Σ ⊔ Σ, we expect that () ≤ 2(||) for every ∈ Σ ⊔ Σ and some polynomial (), and also assume that the result of () should be computable in polynomial time over ||, the size of . Other kinds of restrictions could be made upon (for example, that () ≤ (||) for some polynomial ()) (a) b low high c lw o d high low e (b) low b low low high c low high d high low (c) low b low low high e
e c low high d low low depending on the kind of weight function wanted to be modeled, but we note that, without any restriction, could even be an uncomputable function.
The second type of preference criteria we study is based on multisets.
Definition 8 (Multisets). Given a set , its set of finite multisets is defined as ℳ<∞() = { : → N | () ̸= 0 only for a finite number of }. Given a strict partial order (, <), the multiset ordering (ℳ<∞(), <) is defined as in [19, 20]: 1 < 2 if 1 ̸= 2 and for all ∈ , if 1() > 2(), then there exists some ∈ such that < and 1() < 2().
If (, <) is a strict partial (resp. total) order, then (ℳ<∞(), <) is a partial (resp. total) order. If (, <) is a well-founded order1, then we have that (ℳ<∞(), <) is also a well-founded order [19].
Definition 9. Given a finite data-graph over Σ and Σ, we define its and data values as the multiset ℳ over Σ and Σ such that: multiset of edges ℳ() = {︃|JK| |J=K| ∈ Σ ∈ Σ.
Note that all these multisets of edges and data values belong to ℳ<∞() with = Σ ⊔ Σ. 1ℳ < 2ℳ.
Definition 10 (Multiset-based preferences). Let 1, 2 be two finite data-graphs over Σ and Σ, and let < be a partial order defined over = Σ ⊔ Σ. We say that 1 < 2 if 1I.e. for all ⊆ , if ̸= ∅ then there exists ∈ such that ̸< for every ∈ .
If 1 < 2, we say that 1 is ℳ-preferred to 2 in the context of superset repairs, while we say that 2 is ℳ-preferred to 1 in the case of subset repairs. We say that is ℳ-preferred if is <ℳ-minimal for superset (resp. <ℳ-maximal for subset). Example 11. Consider the data-graphs from Figure 2. Ignoring any possible data value, observe that the multisets corresponding to graphs b) and c) are (with the informal multiset notation): {low, low, low, low, low, high, high, high} and {low, low, low, low, low, low, high, high}, respectively. Assuming low > high, then in this case data-graph b) is ℳ-preferred to c).
In this section we consider subset and superset repairs and Ω-preferred criteria where Ω ∈ {, ℳ}, using diferent subsets of Reg-GXPath for ℒ.
We will always consider the weight function : Σ ⊔ Σ → N fixed and eficiently computable: given a codification of ∈ Σ ⊔ Σ of size the value () is computable in (). This implies that, for any data-graph , () is also computable in (||).
In the same manner, when considering multiset-preferred repairs, we will assume that the order < defined over Σ ⊔ Σ can be computed eficiently: given , ∈ Σ ⊔ Σ it is possible to decide if < in polynomial time on the representation on both and . Thus, we can decide whether 1 < 2 in (|1| + |2|). Furthermore, we assume that the order < is well founded. This implies that there are no infinite descending chains c1 > c2 > . . .
Note that the notions of weight-based and multiset-based preferences induce an ordering over finite data-graphs, which does not admit infinite descending chains. Hence, if a superset repair exists, then there is also a (weight-based or multiset-based) preferred repair. On the other hand, the number of subsets of a given data-graph is finite, so if a repair exists, there must necessarily be a preferred repair.
The complexity of the problems when the set of expressions is fixed is commonly denominated data complexity. Most lower bounds we derive apply to this case.
For the case of ⊆ -repairs, it was proved in [21] that deciding whether there exists a non-trivial repair (i.e. diferent from the ∅ data-graph) is an NP-complete problem for a fixed set of Reg-GXPath expressions, and that the problem is tractable if we only allow node expressions from Reg-GXPath as ℒ. Observe that: Proposition 12. The problem of deciding whether has a non-trivial ⊆ -repair with respect to can be reduced to the problem of deciding whether has a non-trivial Ω-preferred ⊆ -repair with respect to .
Given a fixed weight function (resp. an ordering <), the existence of a ⊆ -repair ′ of with respect to implies the existence of a preferred ⊆ -repair for (and vice versa). Therefore, it follows directly from Proposition 12 and the aforementioned results in [21] that: Theorem 13. The problem of deciding whether there exists a non-trivial Ω-preferred ⊆ -repair for a given data-graph and a set of expressions is NP-complete for a fixed set of Reg-GXPath path expressions.
When ℒ ⊆ Reg-GXPath, a subset repair can be computed in polynomial time and, furthermore, it is unique [21]. Therefore, it must be the preferred one: Theorem 14. Given a data-graph , a set of Reg-GXPath expressions , and a preference criteria Ω, there exists an algorithm that computes the Ω-preferred ⊆ -repair of with respect to .
There is a restriction set containing only Reg-GXPath expressions such that computing -preferred ⊇ -repair is already intractable: Theorem 15. Given a data-graph , a set of Reg-GXPath expressions and a natural number , let Π be the problem of deciding whether there exists a -preferred ⊇ -repair of with respect to whose weight is bounded by . Then, there exists a set of positive node expressions and a weight function such that the problem is NP-complete.
Notice that we could have equivalently defined Π as the problem of deciding whether there exists some data-graph ′ ⊇ such that ′ |= and (′) ≤ (i.e., requiring minimality is not necessary).
Proof. The problem is in NP in general: if there exists a repair of with respect to , due to [21, Theorem 24], then there is one in ‘standard form’. The size of this repair is bounded by (|| + ||), and by inspecting the proof of the theorem and considering that is a non-negative function, it can be shown that the preferred repair always has this ‘standard form’. Then, a positive certificate consists of a data-graph ′ such that |′| ≤ (|| + ||), ′ |= , ⊆ ′ and (′) ≤ .
For the hardness, we reduce 3-SAT to Π, with fixed. For the reduction, we consider Σ ⊇ { value_of, appears_in, appears_negated_in} and Σ ⊇ { , , ⊤, ⊥}. We define the weight function as () = 2 for ∈ Σ ∪ {appears_in, appears_negated_in} and (value_of) = 1.
Given a 3-CNF formula with variables 1, . . . , and clauses 1, . . . , we build a data-graph , a set of Reg-GXPath node expressions and define a number such that is satisfiable if and only if has a superset repair ′ with respect to such that (′) ≤ .
We define the graph as = (, , ) where: = { | 1 ≤ ≤ } ∪ { | 1 ≤ ≤ } ∪ {⊥, ⊤} (, ) = (, ) = ∅ for every other pair , ∈ ⎪⎪⎧{appears_in, appears_negated_in} if and ¬ appear in ⎪ ⎨⎪{appears_in} if only appears in ⎪⎪{appears_negated_in} if only ¬ appears in ⎪ ⎪ ⎩∅ otherwise () = for ∈ {⊥, ⊤} () = for 1 ≤ ≤ ( ) = for 1 ≤ ≤ .
The structure of is codified in the appears edges. We define = () + , and we want any superset repair of with respect to with weight to codify an assignment of the ‘node’ variables by using the edges value_of. In order to do this we define the Reg-GXPath expressions 1 = ⟨[̸=]∪ ↓value_of [⊤]∪ ↓value_of [⊥]⟩ 2 = ⟨[̸=]∪ ↓−appears_in↓value_of [⊤]∪ ↓−appears_negated_in↓value_of [⊥]⟩.
The expression 1 forces every variable node to have a value edge directed to a boolean node, while the expression 2 forces every clause to be ‘satisfied’ in any repair of . Therefore, we define = { 1, 2}. Now we show that is satisfiable if and only if has a superset repair with respect to with weight at most () + .
=⇒ ) Let be a valuation on the variables of that evaluates to true. We then ‘add’ edges to in the following way: if () = ⊤ we add the edge (, value_of, ⊤), and otherwise we add (, value_of, ⊥). This graph satisfies both expressions from and has cost () + , since (value_of) = 1.
⇐= ) Let ′ be a superset repair of with respect to with weight at most () + . Since every superset repair of has to add at least value edges and they cost 1 unit each we know that ′ has to be exactly the original graph plus value edges (one for each node variable). Then we can define a valuation of the variables of by using this edges: if the edge (, value_of, ⊤) is present in ′ we define () = ⊤, and otherwise () = ⊥. Since 2 is satisfied in ′ this assignment must satisfy .
The hardness of Π implies that, unless P = NP there is no algorithm to compute -preferred ⊇ -repairs for fixed sets of Reg-GXPath expressions.
Furthermore, computing a multiset preferred repair is also a hard problem for simple Reg-GXPath expressions: Theorem 16. Given a data-graph , a set of Reg-GXPath expressions , an edge label a ∈ Σ, and a natural number , let Πℳ be the problem of deciding whether has a ℳ-preferred ⊇ repair ′ with respect to such that ′ has at most edges with label a. Then, there exists a set of positive node expressions and a well-ordering < such that the problem is NP-complete. Proof. The proof is analogous to the one of Theorem 15, considering the order value_of < appears_in < appears_negated_in < < < ⊤ < ⊥ and = .
It follows that the hardness of Πℳ implies the hardness of computing ℳ-preferred ⊇ -repairs for fixed sets of Reg-GXPath expressions.
Remark 17. In the case of ⊇ -repairs, it was proved in [21] that deciding whether there exists at least one repair is an undecidable problem for a fixed set of Reg-GXPath expressions, and NP-hard if Reg-GXPath ⊆ ℒ . Meanwhile, it was shown that if ℒ ⊆ Reg-GXPath and the restriction set is fixed, or rather if ℒ ⊆ Reg-GXPath, then there are polynomial-time algorithms to compute a superset repair. Theorems 15 and 16 show that these tractable cases become intractable when considering preferred repairs.
Looking at the proof of Theorem 15 it is clear that assigning a non zero weight to the edges is necessary to achieve the hardness result. If we assume that (a) = 0 for all a ∈ Σ we can show that: Theorem 18. There exists an algorithm that given a data-graph and a set of Reg-GXPath expressions computes a -preferred ⊇ -repair in polynomial time whenever satisfies that (a) = 0 for all a ∈ Σ.
Proof. The standard form described in [21, Theorem 24] minimizes the number of nodes added, and the number of standard forms is bounded by 2||. Therefore, if is fixed, it is possible to search for the one with smallest weight in polynomial time.
If ⊆ Reg-GXPath then it is actually possible to compute a ⊇ repair even in combined complexity (when is part of the input). Nonetheless, it is not possible to compute a -preferred one, even when ignores edge labels: Theorem 19. There is a fixed function that assigns 0 cost to all edge labels such that the problem Π (see Theorem 15) is NP-complete in combined complexity when restricting that ⊆ Reg-GXPath.
Proof. We reduce 3-SAT to our problem. Given a formula on variables 1, . . . and clauses 1, . . . , we will construct a data-graph and a set of Reg-GXPath expressions such that is satisfiable if and only if has a ⊇ -repair ′ with respect to such that (′) ≤ () + . We denote by , the th literal of , for 1 ≤ ≤ and 1 ≤ ≤ 3. For example, if 3 = (1 ∨ 3 ∨ ¬4) then 3,1 = 1 and 3,3 = ¬4. The fixed weight function is defined as () = 1 for ∈ Σ, and () = 0 otherwise.
Let Σ ⊇ { down} and Σ ⊇ { : ∈ N} ∪ {¬ : ∈ N} ∪ { : ∈ N}, and let us define = (, , ) as: = { : 1 ≤ ≤ } (, ) = ∅ for , ∈ ( ) = for 1 ≤ ≤ We also define = { : 1 ≤ ≤ } ∪ { : 1 ≤ ≤ } where = ⟨↓down [= ∨ ¬=]⟩
The formula ensures that in any repair there is a node with a data value related to a literal that satisfies . The formula ensures that in every repair there is either a node with data value or ¬.
We now show that is satisfiable if and only if has a ⊇ -repair with respect to bounded by () + :
=⇒ ) If is satisfiable then there is a valuation of its variables : { : 1 ≤ ≤ } → {⊤, ⊥} that satisfies every clause. If we add to the set of nodes { () : 1 ≤ ≤ } with data values ( ()) = if () = ⊤ and ( ()) = ¬ otherwise, and every possible edge, then the obtained data-graph satisfies and has weight () + .
⇐= ) Let ′ be a ⊇ -repair of with respect to such that (′) ≤ () + . Observe that in order to satisfy each ′ must have a node with data value or ¬. Since the weight is bounded by () + we can conclude that there is either a node with data value or one with data value ¬, but not both. We can define a valuation on the variables 1, . . . , as () = ⊤ if and only if there is a node in ′ such that () = . Such valuation satisfies because all the are satisfied in ′.
The approach of restricting the priority criteria to only consider data values can be carried on in the same way for the ℳ-criteria, by asking only for an order over Σ rather than both Σ and Σ. Then, it is possible to prove theorems analogous to both Theorems 18 and 19.
In this work, we analyze preferred repairing for data-graphs. We specifically focus on the problem of deciding whether a data-graph has a non-trivial preferred repair under two diferent data-aware preference criteria, one based on weights and the other based on multiset orderings. We showed that in some cases, these criteria do not make the repair decision problem harder than the version lacking preferences.
Some questions in this context remain open, such as that of finding refined tractable versions
of the problem that might be based on real-world applications. Alternative definitions of types of
repairs for data-graphs [
In the definition of preferred repairs presented in this work, we never discuss how to handle scenarios with multiple solutions. While introducing a notion of preference reduces the set of repairs of interest, this does not address the problem of choosing one in the presence of several options. In practice, the preference criterion should be adjusted based on the general use case, in order to reduce the set of obtained repairs to a size that is acceptable in expectation. Still, to avoid choosing one repair over another, one could ask for the information that is contained in every possible repair: this is precisely the problem of consistent query answering, whose complexity remains open in this context. However, based on the results presented in this work, some observations can already be made: for example, in the case of subset repairs considering positive node expressions as integrity constraints, we proved that there is a unique preferred repair computable in polynomial time, which therefore implies that the CQA problem can be solved eficiently as well. Artificial Intelligence, volume 28, 2014. [18] T. Lukasiewicz, M. V. Martinez, G. I. Simari, Complexity of inconsistency-tolerant query answering in datalog+/–, in: OTM Confederated International Conferences On the Move to Meaningful Internet Systems, Springer, 2013, pp. 488–500. [19] N. Dershowitz, Z. Manna, Proving termination with multiset orderings, Communications of the ACM 22(8) (August 1979) 465–476. [20] G. Huet, D. C. Oppen, Equations and rewrite rules: A survey, in: Formal Language Theory,
Elsevier, 1980, pp. 349–405. [21] S. Abriola, S. Cifuentes, M. V. Martínez, N. Pardal, E. Pin, On the complexity of finding set repairs for data-graphs, Journal of Artificial Intelligence Reasoning 76 (2023) 721–759. URL: https://arxiv.org/abs/2206.07504. doi:10.48550/ARXIV.2206.07504.