Based on practical observations on rule-based inference on RDF data, we study the problem of redundancy elimination in RDF in the presence of rules (in the form of Datalog rules) and constraints (in the form of so-called tuple-generating dependencies). To this end, we investigate the in uence of several problem parameters (like restrictions on the size of the rules and/or the constraints) on the complexity of detecting redundancy. The main result of this paper is a ne-grained complexity analysis of both graph and rule minimisation in various settings.
(
When storing the graph G = GD [ GO in an RDF Store that supports
inference over rules (
We thus want to be able to answer the general question about redundancy of
both triples and rules. However, it is often important to limit the minimisation of
RDF graphs in such a way that certain consistency conditions must be preserved.
These consistency conditions can be expressed by means of constraints [10]. We
shall restrict ourselves here to constraints in the form of so-called tuple-generating
dependency (tgd) constraints, which are a generalisation of the familiar
foreignkey dependencies in the relational database world. Roughly speaking, a tgd may
be viewed as a generalised rule \read" as constraint. So, for instance, if we read
rule (
Note that tgds can be more general than (Horn) rules in that they allow
otherwise unbound, existential variables in the head, possibly occurring in a
larger conjunct. That is, tgds are { rather than rules { constraining queries (in
the head) \triggered" by bindings coming from a query in the body ; for instance,
a constraint
(
The primary goal of our work is a systematic complexity analysis of both graph and rule minimisation under constraints. To this end, we investigate the in uence of several problem parameters (like restrictions on the size of the rules and/or the constraints) on the complexity of detecting redundancy. A rst important step in this investigation has been recently made by Meier [11]. He studied the following problem: Given a graph G, a set R of rules and set C of tgds, can G be reduced to a proper subgraph G0 G, such that G0 still satis es C and the closure of G0 under R coincides with the closure of G under R? For the special case that both the rules in R and the constraints in C have bounded size (referred to as b-boundedness), this problem was shown to be NP-complete in [11]. In this paper, we want to extend the work initiated in [11] and provide a much more ne-grained analysis of the complexity, e.g., by weakening or strengthening restrictions such as b-boundedness and by considering redundancy elimination that only preserves RDF entailment (rather than keeping the closure of the original graph under the original rules unchanged).
We shall come up with a collection of complexity results, ranging from
tractability to 3P -completeness. Additionally, we address the orthogonal
problem of rule minimisation, which has not been studied so far. We shall also discuss
further variations of the graph and rule minimisation problem. For instance, the
rules and tgds in [11] do not allow variables in predicate positions, which is a
severe restriction in the sense that many of the common RDF inferences rules
are not covered (e.g., all except rules (
Organisation of the paper and summary of results. In Section 2, we recall some basic notions and results. A conclusion and an outlook to future work are given in Section 6. Sections 3{5 contain the main results of the paper, namely:
Graph Minimisation. In Section 3, we provide a comprehensive complexity analysis of the RDF graph minimisation problem, both when full reconstruction of the graph or only RDF entailment is required. We study various settings which result from di erent restrictions on the rules and/or tgds like restricting their size, considering them as xed, omitting them, or imposing no restrictions at all. Our complexity results range from tractability to 3P -completeness.
Rule Minimisation. In Section 4, we consider the problem of minimising the set of rules. We show that the problem of nding redundant rules with respect to a given RDF graph is NP-complete for b-bounded rules and not harder than 2P for arbitrary rules. Note that rule minimisation is closely related to the eld of Datalog equivalence and optimisation. We therefore discuss how the large body of results in this area can be fruitfully applied to the problems studied here.
Problem Variations. In Section 5, we analyse the complexity of further problems which are either variations of or strongly related to the graph and rule minimisation problems mentioned above. For instance, rather than asking if an RDF graph contains redundant tuples, we consider the problem whether an RDF graph can be reduced below a certain size. We show that this problem is NP-complete also in those settings where the graph minimisation problem is tractable. We also discuss the e ect of allowing blank nodes in predicate positions in the Datalog rules and of requiring only that the answers to a given set of queries must be preserved by the minimisation of the graphs or rules. Due to lack of space, proofs are only sketched. While for most of the hardness proofs we only describe the idea of the reduction, membership proofs are either also informal or even omitted. All proofs are worked out in detail in [12]. 2
Let U , B, and L denote pairwise disjoint alphabets for URI references, Blank nodes (or variables) and Literals, respectively. We denote unions of these sets simply by concatenating their names.5 An RDF statement (or triple) is a statement of the form (s; p; o) 2 UB U UBL, and an RDF graph is a set of triples. In this paper, we do not distinguish between variables and blank nodes, but just note that blank nodes/variables appearing in the data are understood to be existentially quanti ed within the scope of the whole RDF graph they appear in. We write elements from B (U ) as alphanumeric strings starting with an upper case letter (lower case letter or number), elements from L as quoted strings, and { inspired by the common Turtle [13] syntax { RDF statements as white-space separated triples and RDF graphs as '.' separated lists of triples in curly braces.
It is convenient to de ne the notion of entailment between two RDF graphs via the interpolation lemma from [9, Section 2] rather than in a model-theoretic way: an RDF graph G1 entails G2, written G1 j= G2 if a subgraph of G1 is an instance of G2, that is, if there exists a graph homomorphism, i.e., a blank node mapping : B ! UBL such that (G2) G1, where (G) denotes the graph obtained by replacing every variable B 2 B with (B). A homomorphism h0 is an extension of a homomorphism h if h0(B) = h(B) for all B on which h is de ned. Given G1, G2, deciding whether there exists a homomorphism G2 ! G1 (and also G1 j= G2) is well known to be NP-complete.
We de ne a basic graph pattern (BGP) as a set of generalised triples (s0; p0; o0) 2 UBL UBL UBL, a lter condition as a conjunct of the unary predicates uri( ), blank( ), literal( ) (denoting the unary relations U , B, and L, respectively). A ltered basic graph pattern (FBGP) is a BGP conjoined with a lter condition, the latter containing only variables already appearing in the BGP. Given an FBGP P , we write BGP (P ) and F (P ) to denote its components, i.e. its BGP and its lter condition, respectively.
We de ne an RDF tuple-generating dependency (tgd) constraint (or simply constraint) r as Ante ) Con, where the antecedent Ante is an FBGP and the consequent Con is a BGP. A constraint Ante ) Con is a short-hand notation for the rst-order formula 8x Ante(x) ! (9y)Con(x; y) (where y denotes the blank nodes occurring in Con only, while x are the remaining blank nodes) Hence, a constraint Ante ) Con is satis ed over an RDF graph G if for each homomorphism on x mapping BGP(Ante) to G, there exists an extension h0 of h to y s.t. h0(Con) G. To increase the readability, we will sometimes explicitly write out the quanti ers and variable vectors. RDF rules (or simply rules), are syntactically restricted constraints, where all variables appearing in Con also appear in Ante (akin to the common notion of safety [14] in Datalog). In the following, we will call RDF rules with an empty lter condition Datalog rules.
considering typed literals separately. We de ne the closure of a graph G with respect to a set R of rules, written ClR(G) as usual by the least x-point of the immediate consequence operator.
We say that a rule or constraint is b-bounded if both, antecedent and consequent contain at most b triples. For a given graph G or a given set R of rules, we use XG,XR (X 2 fU; B; Lg) to denote X \ (G), resp. X \ (R), where by ( ) we denote the signature of a graph or ruleset, that is, the subset of UBL used in G, or R, respectively. Finally, we write [n] to denote the set f1; : : : ; ng. 3
In this section, we study the complexity of RDF graph minimisation. For di erent restrictions on the input parameters, the complexity varies between tractability and 3P -completeness. Formally, we consider the following two basic problems: De nition 1. Let MINI-RDFj=(G; R; C) be the following decision problem: INPUT: RDF graph G, set R of RDF rules, set C of tgds (G satis es C). QUESTION: Is there a G0 G s.t. ClR(G0) j= ClR(G) and G0 satis es C? De nition 2. Let MINI-RDF (G; R; C) be the following decision problem [11]: INPUT: RDF graph G, set R of RDF rules, set C of tgds (G satis es C). QUESTION: Is there a G0 G s.t. ClR(G) = ClR(G0) and G0 satis es C?
The MINI-RDF problem and the minimization of RDF graphs via entailment aim at two kinds of redundancy elimination: In MINI-RDF , triples which can be restored via the rules are considered as redundant while graph minimization via entailment allows us to replace a graph G by a subgraph G G if G j= G holds (see [20]). The MINI-RDFj=(G; R; C) problem combines these two approaches and thus yields the strongest redundancy criterion. Nevertheless, in most cases, its complexity is not higher than for MINI-RDF (see Theorem 1).
It is easy to see that the condition ClR(G) = ClR(G0) in De nition 2 is equivalent to G ClR(G0). The following lemma shows that similarly, for MINIRDFj=, it is enough to show ClR(G0) j= G rather than ClR(G0) j= ClR(G). Lemma 1. Let G1, G2 be RDF graphs and R a set of rules. Then the following equivalence holds: ClR(G2) j= ClR(G1) , ClR(G2) j= G1.
Theorem 1. For MINI-RDFj= and MINI-RDF , the complexity w.r.t. di erent assumptions on the input (arbitrary, b-bounded, or xed rule set; arbitrary, bbounded, xed, or no constraints) is as depicted in Table 1.
The following lemma justi es that we do not have to give an explicit completeness proof for each entry in Table 1, and points out a proof plan for Theorem 1. 1 5 9 2 3 4 6 7 8 10 11 12
R arb., C bb
xed
R arb., C
(
xed
(
xed, C arb.
(
xed xed, C = ; NP-complete NP-complete NP-complete
NP-complete NP-complete NP-complete
NP-complete NP-complete NP-complete MINI-RDF
NP-complete NP-complete NP-complete
NP-complete [11] NP-complete
in P
NP-complete NP-complete in P Lemma 2. The graph in Figure 1 correctly describes the dependencies between the problems (identi ed by their line number) in Table 1, i.e.: If there is an arrow from A to B, then B is a special case of A.
Hence an arrow from A to B means that membership results for A hold also
for B, and that hardness results for B apply also to A. Therefore, to prove
Theorem 1, it su ces to show the membership for (
The most general case, (
The following properties lead to the cases of lower complexity: If R is a b-bounded set, then ClR(G0) can be computed in polynomial time [11, Proposition 9] and if C is a b-bounded set, then testing if G0 satis es C is in PTIME [11, Proposition 3]. For the tractable cases, note that if C = ;, then not all subgraphs of G have to be checked, but only those missing exactly one triple from G. Lemma 3. The problems MINI-RDFj=(G; R; C) and MINI-RDF (G; R; C), for xed R and arbitrary C, are 3P -hard.
Proof. 3P -hardness is shown by reduction from the well-known 3P -complete
problem QSAT3, of which we only give an informal description here. Let an
instance of QSAT3 be given by F = 9x18y19x2 Vin=1 Ci, with Ci = (li;1 _
li;2 _ li;3) (clearly, the restriction to 3-CNF is w.l.o.g.). The graph G created
contains on the one hand triples encoding truth assignments on clauses (e.g.
f0 h1 a001 : 0 h2 a001 : 1 h3 a001g for the assignment (false; false; true)), and on
the other hand triples encoding the two possible truth assignments for variables
(e.g. fvi q1 a01 : vi q1 a10g for xi 2 x1 where vi is a new URI for each xi and the
URI a01 (resp. a10) denotes that xi evaluates to false, hence :xi evaluates to
true (resp. xi to true and :xi to false), together with further triples that allow
us to actually refer to the truth value of xi (resp. :xi)) under a selected truth
assignment. The rules and constraints are chosen in such a way that (
Proof. As NP-hardness of MINI-RDFj= follows easily from the coNP-hardness of testing if G is lean, we concentrate on MINI-RDF and prove its NP-hardness by reduction from the 3-SAT problem. First, we x the rules and tgds as R = ffX0 in I : X active Ig ) fX0 active Igg and C = ffX active I : X in J g ) fX active J g; fX clash X0 : X active I : X0 active I0 : Y in J g ) fY active J gg.
Now let an instance of 3-SAT be given by the formula F = C1 ^ ^ Cn, where Ci = (li;1 _li;2 _li;3) and the li;j are literals. W.l.o.g., we assume that every variable appears negated and unnegated in F . Then we construct an RDF graph G = fli;j in ci j i 2 [n]; j 2 [3]g [ fli;j active ci j i 2 [n]; j 2 [3]g [ fxj clash xj j xj in F g, where we introduce new URIs ci (for every clause Ci) and xj ; xj (for every variable xj in F ), and li;j = xj (resp. xj ) if li;j = xj (resp. :xj ). Intuitively, the triples in G with predicate in encode the literals in F . If a triple with predicate active remains in the selected subgraph G0 then the corresponding literal in F is set to true. The triples with clash keep track of dual literals. tu 4
In this section, we study the rule minimisation problem of RDF graphs. Although there is a huge amount of literature in the Datalog world addressing related problems (as query containment), the particular nature of the problems we study, requires a distinguished complexity analysis. Note that rules for RDF, when written as Datalog rules, have a xed predicate arity of three, which makes problems computationally easier than in the general Datalog setting (see, e.g. [15]). Depending on whether we consider the Datalog rules as b-bounded or not, we obtain complexity results from NP-completeness to 2P -membership. The rule minimisation problem is formally de ned as follows. As the RDF graph remains unchanged, constraints are irrelevant here.
De nition 3. Let RDF-RULEMINj=(G; R) be the following decision problem: INPUT: An RDF graph G and a set R of RDF rules.
QUESTION: Does there exist R0 R s.t. ClR0 (G) j= ClR(G)? De nition 4. Let RDF-RULEMIN (G; R) be the following decision problem: INPUT: An RDF graph G and a set R of RDF rules.
QUESTION: Does there exist R0 R s.t. ClR0 (G) = ClR(G)? For the case that the set of rules is b-bounded, we can pinpoint the complexity of the problem to NP.
Theorem 2. Deciding RDF-RULEMINj=(G; R) for a set R of b-bounded rules (for xed b) is NP-complete.
Proof. The hardness is shown by reduction from the 3-SAT problem. The idea of the reduction is, given some formula F in 3-CNF, to provide in the graph G an encoding of all combinations of truth values under which a clause evaluates to true, and to design the set R of rules such that the triples derivable by R encode which literals occur together in some clause in F . Further, R is chosen such that ClR0 (G) j= ClR(G) holds for any subset R0 R i all triples derivable by R can be mapped into G. This mapping then de nes a valid satisfying truth assignment for F . 2 Theorem 3. The problem RDF-RULEMIN (G; R), for a b-bounded set R of rules, can be decided in PTIME, while for arbitrary rules R, both, RDF-RULEMIN (G; R) and RDF-RULEMINj=(G; R) are in 2P . Proof. In the b-bounded case, the closure can be computed e ciently: It su ces to compare the closure of G under R with the closure of G under every subset of R missing exactly one rule. For arbitrary rules, the same strategy can be used, but now an NP-oracle is needed to test if a rule is applicable. For RDFRULEMINj=, this oracle can then also be used to test for entailment. 2
In order to reduce the complexity of the problems RDF-RULEMIN (G; R) and RDF-RULEMINj=(G; R), one could seek for approximations of those problems. In fact, one option is to check for redundant rules in the set R of given Datalog rules; or whether some rule is subsumed by another rule from R. The rst problem is known to be tractable while the test for rule subsumption is NP-complete (see [16]). The latter result can be shown to hold also for rules of bounded arity (which we deal with here); but becomes tractable in the case of b-bounded rules. Further methods (e.g., folding and unfolding of rules) are well understood for logic programs (see [17]), and could also apply to our domain. An in-depth analysis how to use those results in our setting is left for future work.
In this section, we discuss some further problems which are variations of or strongly related to the problems studied in the previous sections. We start by a variation of the graph minimisation problem. But now we ask if G can be replaced by a subgraph G0 whose size is bounded by some given bound k (rather than an arbitrary subgraph G0 G). Formally, we study the following problem. De nition 5. Let MINI-RDFcard(G; R; C; k) be the following decision problem: INPUT: An RDF graph G, a set R of RDF rules, a set C of tgds and integer k. QUESTION: Does there exist a subgraph G0 G with jG0j k, s.t. G0 satis es C and G ClR(G0)? It can be easily veri ed that for all cases in Table 1 that are at least NP-hard, the complexity for MINI-RDFcard does not change. Intuitively, this is because the nondeterministic algorithms for solving these problems all start with \guess a subgraph G0 G", which can be easily changed to \guess a subgraph with at most k triples". Therefore, the only two interesting cases are MINI-RDF with a b-bounded or xed set R and no constraints, as they can be decided in PTIME. We show that for MINI-RDFcard, the complexity goes up to NP-completeness. Theorem 4. The problem MINI-RDFcard(G; R; C; k) is NP-complete if C = ; and R is either considered as xed or a set of b-bounded rules (for xed b). Proof. The hardness proof is by reduction from the Vertex Cover problem. We give the basic ideas of this reduction. Given some graph G = (V; E), the RDF graph Grdf contains one distinct triple for every v 2 V . The intuition is that the subset of those triples contained in a valid subgraph G0 Grdf describes a vertex cover. We further have three rules, one that (given G0 G) adds all edges covered by the remaining vertices in G0, one that (by repeated application) checks whether all edges are covered, and nally one rule that, if indeed all edges are covered, allows to restore the vertices from Grdf n G0. To allow to express according rules, Grdf contains triples encoding further information (like e.g. neighbourhood of vertices and edges). But as they cannot be derived by any rule, they must remain unchanged in any valid G0 Grdf . Further, their number (say K) only depends on G, such that there exists a vertex cover of size k i there exists a valid G0 Grdf of size K + k. 2 Next we want to identify the sources of the complexity of MINI-RDFj= and MINIRDF for the cases where C is allowed to contain arbitrary tgds. We show that the complexity is independent of the rules, but arises mainly from the question whether there exists some non-empty subgraph that satis es all constraints. Theorem 5. Let G be a RDF graph and C a set of tgds. Deciding whether there exists some ; =6 G0 G s.t. G0 satis es C is 3P -complete.
Proof. Membership follows from Theorem 1. Hardness is shown by a modi cation of the reduction given in the proof of Lemma 3. We give the intuition of these modi cations. In the aforementioned proof, the intuitive meaning of the rules, together with the requirement G ClR(G0), was that for each vi 2 x1, either fvi q1 a01g or fvi q1 a10g has to remain in the subgraph G0. However, this can be also formulated as a constraint. By introducing an additional triple for every vi 2 x1 (e.g. fvi opt vig) that is enforced to be contained in any non-empty subgraph, the tgd fV opt V g ) fV q1 Ag does the job. 2
From the (full) proof of Lemma 4, it follows that for MINI-RDFj=, one source of the NP-hardness is just to decide the entailment. However, similarly to the last theorem, we can show that for b-bounded tgds, just testing for the existence of a valid subgraph already contains the full hardness too.
Theorem 6. Let G be an RDF graph and C a set of b-bounded tgds. Deciding whether there exists some ; 6= G0 G s.t. G0 satis es C is NP-complete. Proof. Membership follows from Theorem 1. Hardness is shown by reduction from the SAT problem. The reduction is very similar to the one of Lemma 4, only that all the implicit information about which triples must not be removed from G (expressed by not providing rules to derive them) now have to be made explicit as tgds. This however no longer allows for a xed set of tgds, but makes the number of tgds dependent on F .
Let an arbitrary instance of SAT be given by the formula F = Vn i=1 Ci with Ci = (li;1 _ _ li;ki ) (where li;j are literals). We assume that every variable in F occurs negated and unnegated. Introducing two new URIs xi and xi for every variable xi in F , and one new URI ci for every clause in F , we de ne G = fli;j in ci j i 2 [n]; j 2 [ki]g [ fli;j active ci j i 2 [n]; j 2 [ki]g [ fxj clash xj j xj in F g [ fci clause ci j i 2 [n]g and C = f fX active I : X in J g ) fX active J g; fX clash X0 : X active I : X0 active I0 : Y in J g ) fY active J g; fI clause Ig ) fX active Igg [ ffA B Cg ) fci clause cig j i 2 [n]g [ ffA B Cg ) fli;j in cig j i 2 [n]; j 2 [ki]g [ ffA B Cg ) fxj clash xj g j xj in F g where li;j = x if li;j = x and li;j = x if li;j = :x . 2 Note that the above proof would work { by a grounding of the last constraints and introducing some additional constraints { as well if no blank nodes in the predicate positions were allowed. However, the proof would be less compact.
We now show that the complexity of the problems remains unchanged by allowing additional predicates uri (:), blank (:), lit (:) to restrict the type of a value in a Datalog rule, that is, allowing general RDF rules as de ned in Section 2. Note that for every x 2 U [ B [ L occurring in some RDF-graph G (i.e. for every element of the active domain) it can be easily recognised whether it belongs to U , B or L: This could be either decided using syntactic criteria, or by a lookup in U , B and L (although those sets are supposed to be countable in nite, one can assume that UG, BG and LG, i.e. the elements of the active domain, are the \ rst" elements of these sets). Therefore, determining the type of some element requires at most polynomial time in the size of G. Therefore, for every element x of the active domain of G, we create a ground atom Bt(x), Ut(x) or Lt(x), depending on the type of x. By encoding an atom blank (X) as triple fX blank Xg in G, we can make this information available for rule application without increasing the complexity of the problem.
The same argument allows us to overcome the problem that the closure w.r.t.
a rule set R contains invalid RDF triples (containing e.g. a blank node in a
predicate position). Depending on whether invalid triples are allowed in intermediate
results or not, we can pursue one of the following two strategies: (
We conclude this section by discussing a further variant of (graph or rule) minimisation that guarantees completeness only w.r.t. a given set of conjunctive queries (CQs). Such a minimisation is of high interest, e.g. when importing data into an RDF Store that provides a narrow query interface only. Below we give a formal de nition for the CQ-variant of the MINI-RDF problem. De nition 6. MINI-RDF ;CQ (G; R; C; Q) is the following decision problem: INPUT: An RDF graph G, a set R of RDF rules, a set C of tgds (G satis es C), and a set Q of CQs, de ned by BGPs.
QUESTION: Is there a G0 G s.t. (
We proved a collection of complexity results for minimisation problems over RDF graphs where we considered various restrictions on the rules and tdgs. One such restriction was b-boundedness [11]. We note that this restriction can be relaxed by bounding not necessarily the size of the rules (or tgds) but only the maximal number of blank nodes occurring in the rules (or tgds) | in the Datalog world, Vardi [18] showed that such a restriction decreases complexity.
The minimisation problems considered here are driven by practical needs to represent RDF data compactly or tailor them to engines supporting di erent rule sets. Our results also provide a basis for eliminating redundancies in existing practically relevant rule sets, such as OWL2RL [8]. We believe that our results will gain even more relevance with the advent of novel standards such as the W3C rule interchange format (RIF) which will allow one to enrich RDFS and OWL with Web-publishable custom rule sets [19].
We have brie y discussed further variants of minimisations like (graph or rule) minimisations that guarantee completeness with respect to a given set of conjunctive queries (CQs). We have sketched that the hardness results from Sections 3 and 4 still hold when we take CQs into account. Identifying the precise complexity of RDF minimisation relative to a set of CQs is an important task for future work. As another direction of future work, we plan to cast the obtained results into practical algorithms to \compress" RDF graphs and rule sets, investigate related relevant problems such as \trading" triples for rules, or vice versa, and experimentally evaluating e ects of such transformations on query answering with dynamic inference such as sketched in [2].