-Provenance and annotation are intimately con- temporal RDF [10] propose methods of adding annotations nected. On the one hand provenance can be regarded as a to RDF triples to express belief, trust, or temporal properties. form of annotation, on the other hand, in order to understand Can we simply follow the work for relational databases in nheoewd taoncoancvceoyunatnnofothaotiwontshefrodmatasowuarscedderaitvaedto-deitrsivperdovdeantaa,nwcee. developing a general model for such annotations? Here we Following a successful line of database research in which elements have to start by looking not at query languages for RDF, of a database are annotated with algebraic terms that describe but at the inference rules for the ontologies such as those the provenance of those elements, we develop an algebra of of RDFS [1]. Given annotations on the base triples, what annotations for RDFS that differs from that developed for should be the annotations on an inferred triple? Indeed in [15], rcealnatbioenaulseddatfaobracsoesm. pWuteinsghoawnnhootwatiosuncshonaninafnenrroetdatitorniplaelsgetbhraat [16], [12], with an initial goal applying fuzzy logic to RDFS provide information on belief, trust and temporal aspects of data proposes an algebra similar in many respects to that of [8]. as well as providing a framework for default reasoning. In this paper we propose a somewhat more general - and possibly simpler - algebra to serve this purpose. Our proposals I. INTRODUCTION differ from the semirings in [8] in two ways. First, there are With the increasing interest in provenance in both databases situations in which we do not want commutativity and second, and ontologies, there have been a number of proposals and while the number of triples inferred in an RDFS graph is systems for annotation of the underlying data with information always finite, the derivations can be unbounded. We therefore concerning time, belief, and various aspects of provenance. need an extra condition to prevent “infinite annotations”. This The question that has been repeatedly posed in databases [17], condition precludes the possibility of bag semantics, which is [5], [2] is what happens to these annotations when a query useful for relational algbra but appears to be inapplicable to is applied? Are they ignored or are they somehow passed ontologies. Also in [8] there is a compact representation - a through the query? In fact generic prototypes [4] and systems polynomial - of terms in the semiring algebra. In the algebra that are specific to some domain [6] have been developed we develop, the compact representation is somewhat different. for propagating annotations through queries. Suppose, for To introduce annotation algebras, we give two simple examexample, we take two tables S and T in which the individual ples of annotating an RDF graph shown in Fig. 1(a) (a dashed tuples have been annotated. How should we annotate the tuples arrow represents a triple, which can be inferred from the rest in the join of S and T ? An obvious answer is to put on of the graph). any output tuple the union of the annotations on the two Example 1: A temporal extension of RDF was introduced contributing tuples. This does not always make sense; for in [10], [9]. It consists of attaching to every RDF triple a set example if the input tuples are annotated with the set of people intervals that represents the times at which the triple is valid. who believe that this tuple is true or with the set of database An example of a temporal annotation of the graph is shown in versions for which the tuple is actually in the database, it Fig. 1(b): Picasso worked as a cubist from 1908 to 1919, paints might be more appropriate to annotate a join tuple with the are created by painters at least since engravings in Chauvetintersection of the relevant annotations. Pont-d'Arc cave from about 29,000BC, and so on. The point This problem has resulted in a variety of proposals for here is that an annotation for the inferred triple was obtained propagating annotations through queries. Notably, by using by an intuitive calculation (f1908 1919g \ f1906 1921g) [ a semiring model for annotations, in [8] a tuple is annotated (f1937g \ f 29; 000 N owg) = f1908 1919; 1937g. with a term in a semiring algebra that describes the provenance Example 2: In [15] fuzzy annotations of RDF are used to of the tuple - how it was formed by the operations of the describe degree of trust. To every triple a real in the range relational query that constructed it. By suitable instatiatons [0; 1] is attached. Such an annotation is shown in Fig. 1(c). The operations of the semiring, one can realize various extensions annotation for the inferred triple was calculated as max(0:8 to relational databases such as probabilistic databases, multi- 0:4; 0:3 1) = 0:32. set semantics and certain kinds of constraint databases. The There is an obvious similarity between these examples: the semiring model also generalizes a number of other models for calculations are both of the general form (a b) (c d), provenance [5], [2]. and the calculations for the inferred triple are performed by Turning to ontologies, proposals have also been suggested suitably instantiating the operators and . In fact [16], for the annotation of RDF [13]. Named graphs [3] and both of the annotation domains form so-called BL-algebras
type type
type: 0.8 type: 0.32
Paints : 0.3 (c) dom: 1 [11], which in general preserve the properties of the deductive system [16].
Before describing these constructions in more detail we should briefly connect this work with the general issue of provenance. Our first observation is that an algebraic annotation or a triple of the form we have described is a synopsis of how that triple was derived – which is surely part of its provenance. The second is that exogenous provenance information such as who created a triple or when it was created can be added following the proposals of [3]. We would also like to compute such annotations for an inferred triple. Our proposals provide a method for tranferring the provenance annotations of explict triples to those that are derived.
Outline. This work has two aims. The first is to determine what algebraic structure is necessary for an annotation domain to keep the behavior of the deductive system the same as in the standard case. The second is to find “the most general” of such structures, which allows annotation of RDF graphs by elements of the general structure, apply inference rules, and then obtain annotations from specific domains on demand. In the following sections we review RDFS, introduce a new annotation algebra and provide some evidence that this is the appropriate algebra for RDFS. We give a freeness result that allows us to represent the terms of this annotation algebra and give some examples of the use of the algebra.
Given a set of RDF URI references U1, let T be the set of RDF triples of the form (s; p; o) 2 U U U. Here s; p and o are called subject, predicate and object correspondingly. An RDF graph (or simply graph) is a finite set of triples G T .
The RDF specification[13] includes RDF Schema (RDFS) [1] which is a vocabulary of reserved words designed to describe relationships between resources and properties. In this work we use the df = fsp; sc; type; dom; rangeg fragment of RDFS [14]. The elements of df represent sub-property, sub-class, domain, and range properties correspondingly. It is widely accepted that df is a stable core of RDFS.
An interpretation of an RDF graph is a tuple I = ( R; P ; C ; P J K; CJ K; I ) where – R is a nonempty set of resources, 1For the sake of simplicity we do not consider blank nodes and literals. Their inclusion does not change the results of this work. – – C – P J K : – C : – I J: KU !
P is a set of property names (not necessarily disjoint from R),
R is a set of classes, P ! 2 R R is a property extension function, C ! 2 R is a class extension function,
P is an interpretation mapping.
R [ The interpretation I is a model for a graph G over df, denoted by I j= G, iff the conditions in Tab. I hold2. A graph G entails G0, denoted G j= G0, if every model of G is a model of G0.
A sound and complete deductive system for entailment [14] is presented in Tab. II. An instantiation of an inference rule r from the system is a replacement of the variables A; B; C; X , and Y, occurring in the rule, by references from U. If there is an instantiation RR0 of r such that R G, then the graph G0 = G [ R0 is the result of an application of r to G. A graph G0 is inferred from G, denoted by G ` G0, iff G0 is obtained from G by successively applying rules in Tab. II. This entailment can be checked by computing the closure of G, which is the maximal graph which can be inferred from G. It can be done in quadratic time [14].
Definition 1: Given an algebra K with an elements set K containing a distinguished element ? a K-annotated RDF graph (or simply an a-graph, if K is clear) is a function G : T ! 2K such that for each t 2 T holds ? 2 G(t) and the set Supp(G) = ft : v j v 2 G(t); v 6= ?g is finite.
If v 2 G(t) we write t : v 2 G and call it an a-triple. An a-graph G is schema-acyclic, if the subgraphs f(s; e; o) : v j (s; e; o) : v 2 Supp(G)g; e = sc; sp; do not contain non-trivial loops. The semantics for a-graphs is given in the following definitions.
Definition 2: A K-annotated interpretation is a tuple I = ( R; P ; C ; P J K; CJ K; I ) where R; P ; C and I are the same as for the standard interpretation and P J K; CJ K are defined as follows: – for each p 2 P holds P JpK : R R ! K, – for each c 2 C holds CJcK : R ! K.
To define models for annotated RDFS we need more
structure on the algebra K. Let and be binary operations on
K and ?, > be distinct constants in it. For every a; b 2 K
2The form of conditions in our definition of model is slightly different
from that in [14], but they are equivalent per se. It is done to simplify the
comparison with notion of model for annotated RDFS given in Sect. III.
(
– for each (s; p; o) 2 G holds pI 2
(
P ;
P and (sI ; oI ) 2 P JpI K.
P ; C ; C ; C and y 2
C and y 2
P ;
P .
– if (p; q); (q; r) 2 P JspI K then (p; r) 2 P JspI K;
J K and (p; q) 2 P JspI K then (x; y) 2 P JqK.
– if (x; y) 2 P p
(
– if x 2 C c
(
J K and (c; p) 2 P JJrdaonmgIeKIthKetnhexn 2y C2JCcKJ;cK. – if (x; y) 2 P JpK and (c; p) 2 P – if (x; y) 2 P p we write a b iff there exists c 2 K such that a c = b. The addition operation will be used to combine annotations for the same triple and the ? constant represents the fact, that there is no information about a triple. The product operation will be used to join annotations when applying inference rules and > represents the maximal annotation.
Definition 3: Let K = hK; ; ; ?; >i be an algebra of type (2; 2; 0; 0). The K-annotated interpretation I is a model for an a-graph G, denoted I j= G, iff the conditions in Tab. III hold. An a-graph G entails H , denoted G j= H , if for every I j= G holds I j= H .
By these definitions, each (non-annotated) RDF graph G can be considered as an a-graph G0 = ft : > j t 2 Gg [ E, if K = f?; >g and E = ft : ? j t 2 T g. In this case, the definition of model for an a-graph coincides with the standard.
IV. A DEDUCTIVE SYSTEM FOR ANNOTATED RDFS AND
DIOIDS
Definition 4: An algebra K = hK; ; ; ?; >i is a dioid
iff it is an idempotent semi-ring, i.e.
(
A dioid is >-dioid iff
(
Note, that >-annihilation entails idempotence from (
An instantiation of a rule from the deductive system in Tab. IV is a replacement of variables A; B; C; X , and Y by elements of U, and variables v; v1; v2, and v3 by elements of K, such that all relations for annotations hold. An application of a rule to an a-graph G and a deduction of an a-graph G0 from G, denoted by G ` G0, is defined exactly the same way as for the standard case.
Note, that the system in Tab. IV differs from the one in Tab. II only by the presence of annotations and the generalisation rule ( ) which combines annotations for the same triple. Thus, that is natural to expect the new system to behave the same as the standard one. Particularly, they should coincide if K = f?; >g. To obtain it we need some properties of K.
Definition 5: Let R be the set of all inference rules of the
form T1 T2 from Tab. IV and I ns(r) the set of all instantiations
of a rulTe r 2 R.
(
– for each (s; p; o) : v 2 G holds pI 2 P and v
(
C and y 2 P .
–– PP JJdtoympeIIK(Kx(x;y;y))isisdedfiefinendedonolnylyfofrorxy22
– P JrangeI K(x; y) is defined only for x 2
(
–– PP JJsppK(IxK;(py;)q) P JPsJpsIpKI(pK(;qq;)r) P JPqJKs(xp;IyK()p.; r);
(
(
(A; sp; C) : v1 v2 (b) (X ; A; Y) : v1 (A; sp; B) : v2 : (X ; B; Y) : v1 v2 (*) Generalisation: (X ; A; Y) : v1 (X ; A; Y) : v2 :
(X ; A; Y) : v1 v2 (a) (X ; A; Y) : v ; (b) (A; sp; A) : v (e; sp; e) : >
As in the standard case, the important notion is the closure cl(G) = f j G ` f gg of an a-graph G. To compute it we need a representation of an a-graph G, which is a finite set of a-triples RG such that RG [ E = G, E = ft : ? j t 2 T g. The set Supp(G) by the definition is a representation of G, but we also want to have a possibility to work with representations which contain an finite number of ?-annotated triples.
Proposition 2: Let G be an a-graph and K a >-dioid. For every representation RG of G there exists an representation Rcl(G) of cl(G) which can be computed in polynomial time in the size of RG if the complexities of and are polynomial bounded.
Let K and K0 be two algebras. For any function h : K ! K0 and K-annotated graph G denote h(G) the set of K0-annotated triples formed from G by applying h to each annotation.
Proposition 3: Let h : K ! K0 and K; K0 be >-dioids. For every K-annotated graph G the set h(G) is a K0-annotated graph and holds cl(h(G)) = h(cl(G)) iff h is a dioid homomorphism.
Prop. 3 enables us to obtain an a-graph from another one without recomputing annotations for inferred triples. The next step is to develop a “universal” annotation, i.e. an annotation from which we can obtain any other one by applying a corresponding dioid homomorphism.
Given an alphabet define an subsequence order on the set of words : u u0 iff for some u1; : : : ; un; w1; : : : wn 1 2 holds u = u1u2 : : : un and u0 = u1w1u2w2 : : : wn 1un. A finite set m is an antichain if for all u u0, u; u0 2 m, holds u = u0. Let min(m) be the set of minimal elements (w.r.t. ) of m. On the set of antichains M [ ] we define: m1 + m2 = min(m1 [ m2); m1 m2 = min(fw1w2 j w1 2 m1; w2 2 m2g); Call M[ ] = hM [ ]; +; ; ;; f gi, where is the empty string, a string dioid over generators . Note, that a string dioid is a >-dioid. The following proposition says, that it is “the most general” of all >-dioids.
Proposition 4: (
Hence, string dioids consititute an important and general subclass of >-dioids. We now show how they can be applied to annotate RDF graphs. Let G be a K-annotated graph and X a set of triple ids of triples from Supp(G). We associate to G an “abstract” version which is a (X [ ;)-annotated graph G consisted of the same triples as G, but the annotation of each of them is its id if it has one, and ; otherwise.
Theorem 2: For every K-annotated graph G holds cl(G) = Eval cl(G), where : X ! K is a valuation which associates the annotation of an a-triple in G to its id.
This theorem gives rise to the following strategy for annotating RDF graphs. Given a graph G we are to annotate it with elements from several domains. However, we would like to infer triples and their annotations only once, without recomputing the annotations for each annotation domain. In this case we construct an “abstract” version G of G by annotating triples with their ids. Then we can apply inference rules and obtain an abstract annotation from the string dioid over the set of ids for each triple. Finally, as soon as we need to get annotations from a specific domain we need to make sure that it is a >-dioid, define a homomorphism by attaching specific annotations to triples in G and then apply it to abstract annotations of previously inferred triples.
In this section we introduce several annotation domains for RDF graphs those are >-dioids.
Temporal RDF [16]. This model treats the Ex. 1. The temporal domain KT = hKT ; T ; T ; ?T ; >T i is defined as follows. Consider temporal intervals [ 1; 2] where 1;2 2 P = Z [ f 1; +1g, 1 < 2. Two intervals [ 1; 2] and [ 3; 4] are adjacent iff 2 + 1 = 3. The set KT is the set of all pairwise disjoint and non-adjacent sets of intervals. On KT a partial order is defined: 1 2 iff for each I1 2 1 there exists I2 2 2 such that I1 I2. For KT we have: 1 T 2 = inff j i; i = 1; 2g, 1 T 2 = supf j i; i = 1; 2g, ?T = ; and >T = P. The domain KT forms an BL-algebra and hence a >-dioid.
Fuzzy RDF [15] treats the Ex. 2. The domain here is KF = h[0; 1]; max; F ; 0; 1i, where F is any t-norm of BL-algebra. If F is an ordinary multiplication as in Ex. 2, then the domain becomes probabilistic. As KT domain, KF is a >-dioid.
Default RDF. In both of the previous domains the product operation in the dioid is commutative. Next we introduce an example of -noncommutative annotations.
Suppose we want to represent – in an RDF graph – information about an attribute attached to resources modelled by the graph. The straightforward way is to introduce a new property to the vocabulary of the graph and handle it as usual. Nevertheless, in some situations this way can be not optimal: If we have a broad system of classes and values of the attribute for subclasses and elements of a class are usually the same, then it is natural to keep the default attribute value for the class and the value for a resource only if it differs from usual one of the class it belongs to.
For a substantiation, consider an RDF graph denoted in Fig. 2 representing a (part of) botanical taxonomy3. The triples of this graph have annotations which store values of an attribute PublishedBy for every taxon in the graph. The division Pinophyta was introduced by Carl Linnaeus, so the triple (P lantae; sc; P inophyta) is annotated by Linnaeus. The subsequent taxons down to family Araucariaceae keep this attribute value, so we annotate all sctriples between Pinophyta and Araucariaceae with a special value ? which means “derived from above”. The same value keeps for genus Araucaria and species Araucaria Araucana. But genus Wollemia was introduced by David Noble as well as its only species Wollemia Nobilis, so the annotations for the triples (Araucariaceae; sc; W ollemia) and (W ollemia; sc; W:N obilis) are N oble and ? correspondingly. Thus, to find out from the graph who introduced a taxon we need to go up from its node along the tree until we find an edge with an annotation differs from ?. An annotation value for a triple here represents not the value of the attribute by itself, but its difference with the value of higher triple in the tree. Hence, it is natural to phisically keep such annotations in a memory only it they differ from ?. That is why if the value of an attribute for a resource in most cases is determined by a class it belongs to and the number of attributes are large, the advantage in memory can be sufficient.
Before we define the default domain formally, note, that the situation in general case can be more complicated than in the latter example, because a df subgraph of a graph does not nesessarily have a tree structure. Therefore, in certain cases we need to combine different annotations for a triple. To this effect we require a set of attirbute values to have a union operation and the lowest element, i.e. to be a semilattice. In many cases (as in the taxonomy example) this set has no structure, but it is possible to enrich it with the lowest element Unknown and the greatest element Error. The latter is justified by situations 3This is just an example and the actual information may be incorrect. . . .
sc: ?
Plantae sc: Linnaeus Pinophyta sc: ? . . . sc: N oble when from one source we get an attribute value for a resource, but from another source we get a different value for the same resource which contradicts with the first one. The union of this information is inconsistent and requires a manual intervention, which can be flagged by Error annotation.
Let A be an attribute with a domain hA; t; 0i which is a semilattice with union t and the lowest element 0. Consider an A-default domain KA = hA? [ f??; >?g; A; A; ??; >?i, where A? = (A fT rue; F alseg) and ??, >? are new special symbols. Note, that the meanings of ?? and an annotation with 0 are different: The first one says that a triple is not in the support of a graph and the second says that the value of the attribute is minimal according to t. The second boolean component of A? corresponds to ? in the taxonomy example above, i.e. it is T rue in an annotation for a triple iff the actual value of the attribute is the union of the first component of the annotation with values those can be derived from triples above, and F alse overwise. The operations are defined as follows: (a1; b1) (a1; b1)
A (a2; b2) = (a1 t a2; b1 _ b2); A (a2; b2) = (a1 t a2; b2) iff b1 = T rue; (a1; b1) iff b1 = F alse: These operations extend to elements ?? and >? in a way to keep the properties of ? and > in the dioid. Next, we describe the meaning of this operations. The addition A is applied when we union annotations about the same triple. Hence, the values a1 and a2 are joined by the semilattice operation t and the possibility to derive values from a df structure above exists only if it exists in any of the considering annotations. The product A is applied when we infer triples by transitivity of sc or similar inference rule from Tab. IV. If b1 = T rue we union the current value a1 with the derived value a2 and the possibility of father deriving depends on b2. If b1 = F alse, we just keep the annotation (a1; b1) which override any annotation -noncommutative >-dioid. from a structure above. Finally, KA can be easily checked to be
To use the A-default dioid KA for storing values of an attribute A for resources we assume (0; T rue)-annotation for a triple by default and do not keep it in a memory. As soon as we need the real value of the attribute for a resource a we infer a triple (a; type; r) and get the first component of annotation for it. (Here r is the root of df subgraph of the considered graph; if it does not exist, we can always introduce it.)
Although annotation algebras have been studied for database query languages [8] and have also recently been investigated for RDF query languages [7], we have suggested an alternative and more natural algebra for the annotation of RDFS, and we
W. nobilis have given some examples of its use. There may be some mileage to be gained by combining these two algebras. One of the applications of the proposed algebra is a system for default reasoning about certain annotations on RDF resources, which may also prove to be a useful mechanism for physically storing those annotations. We would like to find similar mechanisms for efficiently storing default annotations on triples.
We are grateful to Marcelo Arenas, Boris Motik, Floris Geerts and Alex Simpson for helpful discussions. This work was supported by a grant from the UK Engineering and Physical Sciences Research Council.