Adrien Basse

Fabien Gandon

Isabelle Mirbel

Moussa Lo

Incremental characterization of RDF Triple Stores

Keywords: RDF, graph mining, structure d'index, codage DFS RDF, graph mining, index structure, DFS coding

Many semantic web applications integrate data from distributed triple stores and to be efficient, they need to know what kind of content each triple store holds in order to assess if it can contribute to its queries. We present an algorithm to build indexes summarizing the content of triple stores. We extended Depth-First Search coding to provide a canonical representation of RDF graphs and we introduce a new join operator between two graph codes to optimize the generation of an index. We provide an incremental update algorithm and conclude with tests on real datasets.

Introduction

Many semantic web applications face the problem of integrating data from distributed RDF1 triple stores. Several solutions exist for distributed query processing (see [START_REF] Battle | Bridging the semantic web and web 2.0 with representational state transfer (rest)[END_REF], [START_REF] Stuckenschmidt | Index structures and algorithms for querying distributed rdf repositories[END_REF]) and SPARQL 1.1 Federation2 defines extensions to the SPARQL 3 Query Language to support distributed query execution. These extensions allow us to formulate a query that delegates parts of the query to a series of services but one issue remains: how to automate the selection of triple stores containing relevant data to answer a query. This is especially true in the context of the Linking Open Data where numerous and very heterogeneous datasets are interlinked allowing interesting queries across several sources. To decompose and send queries targeting only relevant stores, we need a means to describe each store: an index structure which provides a complete and compact description of the content of the triple store. Imagine you are interested in Tim Berners-Lee's activities and want to find his publications and some of his personal information. Figure 1 shows RDF graphs from two independent datasets: DBPedia4 and DBLP 5 . Knowing what kind of knowledge is maintained by each store allows us to conclude that we have to combine publication information from DBLP with personal information from DBpedia. Figure 1 also illustrates what kinds of content one may frequently encounter in each dataset and therefore what kind of knowledge one can expect to gain when accessing these datasets. Therefore, automatically identifying descriptive content for a triple store is a key problem. To build indexes summarizing the content of triple stores and to use this indexes to guide distributed query processing we are interested in structure of SPARQL query. According to the information kept in the indexes, [START_REF] Harth | Data summaries for on-demand queries over linked data[END_REF] and [START_REF] Umbrich | Comparing data summaries for processing live queries over linked data[END_REF] classify the approaches adressing the problem of selection relevant sources. Some approaches (Inverted URI Indexing approaches) use as indexed items the URIs in the source. Others approaches (Schema-level Indexing approaches) use as indexed items the properties and/or URIs of classe of nodes in the source. Finally, there is a family of approaches (Multidimensional Histograms approaches and QTree approaches) which "combine description of instance and schema-level element". The approach we propose belongs to family of Schema-level Indexing approaches and uses particular graphs as indexed items. Chosing graph as indexed items instead of uri, node and/or property or triple allow us to keep the structure of the information itself and in the futur to be able to decompose the distributed query into graph pattern (basic or group pattern graph (eg. http://www.w3.org/TR/sparql11-query/)) to determine relevant sources. Section 2 describes our indexed item and its canonical representation nammed DFSR (Depth-First Search coding for RDF) code. Section 3 details the induction algorithm to build the different levels of the index structure. Section 4 discusses results of experiments. Section 5 presents an incremental algorithm to update the index structure when changes occur in the triple store. Section 6 surveys related works.

2 Indexed item and DFSR CODING Figure 2 shows an RDF graph describing people and containing cycles, blank nodes and multityped resources. We will use this example to explain our indexed item and its canonical representation. For the sake of readability we omit namespaces in the remaining paper (rdf :type instead of http://www.w3.org/1999/02/22-rdf-syntax-ns#type for instance). Following the definition of graphs in [START_REF] Baget | Griwes: Generic model and preliminary specifications for a graph-based knowledge representation toolkit[END_REF] and [START_REF] Harth | Data summaries for on-demand queries over linked data[END_REF] we propose the following definitions to describe and explain our indexed items (Infered RDF graph pattern). Inria subject of many RDF typed triples {(n, rdf : type, t i ), 1 < i < k} then we define its (conjunctive) type as the intersection of all object {t i , 1 < i < k} of this RDF typed triples and note it as t 1 ∧ t 2 . . . ∧ t n . Definition 4.(Infered RDF triples (IRDF triples).) A Infered RDF triples of a RDF untyped triple (s, p, o) is the set of RDF triples {(s, p, o)} ∪ {(s, rdf : type, t i ), 1 < i < n} ∪ {(o, rdf : type, c j ), 1 < j < m}. To ensure that each node has at least one type we give by default the type rdf:resource to each node. Definition 5.(Infered RDF graph (IRDF graph).) A RDF graph I is the Infered RDF graph of a RDF graph G if and only if I is the union of all IRDF triples of the RDF untyped triples of G. Definition 6.(Infered RDF graph pattern (IRDF graph pattern), instance of a IRDF graph pattern.) A RDF graph P is the infered RDF graph pattern of an IRDF graph I if there is a mapping function M such that • M maps URI, blank node and litteral to blank node.

• {(s, p, o)}∪{(s, rdf : type, t i ), 1 < i < n}∪{(o, rdf : type, c j ), 1 < j < m} is an IRDF triples in I if and only if {(M (s), p, M (o))} ∪ {(M (s), rdf : type, t i ), 1 < i < n} ∪ {(M (o), rdf :
type, c j ), 1 < j < m} is an IRDF triples in P.

If P is the IRDF graph pattern of a RDF graph G, we also say that G is an instance of P.

Intuitively, to obtain an IRDF graph pattern from an IRDF graph G we replace in G the nodes of RDF untyped triples and subject of RDF typed triples with blank nodes. Definition 7.(Size of IRDF graph pattern.) The size of an IRDF graph pattern I is its number of untyped RDF triples or the number of its IRDF triples.

Throughout the paper we use a linear textual notation and a graphical notation form to represent IRDF graph pattern. A node of a untyped triple is labelled by its type and its label. The URI of nodes are replaced by character * to represent blank nodes. Figure 3 shows an example of IRDF graph pattern with instance in Figure 2 and its corresponding linear textual form and concise graphical notation form. To represent IRDF graph pattern in the index structure and improve the efficiency of some operations on graph as equality between graphs, isomorphism test, we use a canonical form of IRDF graph pattern. The canonical form proposed is an extention of Depth-First Search (DFS) coding of [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] to the IRDF graph pattern. [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] introduced a mapping of graphs to DFS codes.

An edge e with n(e) = (n i , n j ) of an undirected labelled graph G is presented by a 5-tuple, (i, j, l G (n i ), t G (e), l G (n j )), where i and j denote the positions (DFS discovery times) of nodes n i and n j following a Depth-First Search. (l G (n i ) and (l G (n j ) are respectively the labels of n i and n j and t G (e) is the label of the edge between them. i < j means n i is discovered before n j during the Depth-First Search. When performing a Depth-First Search in a graph, [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] construct a DFS tree and defines an order. The forward edge set contains all the edges in the DFS tree while the backward edge set contains the remaining edges. The forward edges are arranged in DFS order with their discovery times during the Depth-First Search. Two backward edges linked to a same node are arranged in lexicographic order. Given a node n i , all of its backward edges should appear after the forward edge pointing to n i . The sequence of 5-tuple based on this order is a DFS code. A graph may have many DFS codes and a DFS lexicographic order allows us to determine a canonical label called the minimum DFS code. [START_REF] Han | Fsp: Frequent substructure pattern mining[END_REF][START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF][START_REF] Yan | Closegraph: Mining closed frequent graph patterns[END_REF][START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] discuss DFS coding in the context of undirected labelled graphs. For directed labelled graphs [START_REF] Maduko | Graph summaries for subgraph frequency estimation[END_REF] captures the edge directions: in the 5-tuple We assign the code 0 to literals. Figure 4 shows an IRDF graph pattern with instances in Figure 2 and its DFSR code. To choose the first 5-tuple of the minimum DFSR code we use a lexicographic order on the IDs of properties as in [START_REF] Maduko | Graph summaries for subgraph frequency estimation[END_REF]. Therefore, the first 5-tuple in a minimum DFSR code is the one corresponding to the untyped RDF triple with the minimum property in the IRDF graph pattern. When an IRDF graph pattern has more than Inria one untyped RDF triple with minimum property we use a lexicographic order on the IDs of the subjects first and the objects if needed to choose our first 5-tuple. When an IRDF graph pattern has n (n > 1) minimum RDF triples (same property, subject and object) we compute n DFSR codes and choose the minimum one following DFSR order. By adding a lexicographic test between subjects and between objects we reduce the cases where we have more than one minimum RDF triple and therefore we reduce the number of DFSR codes computed. In Figure 4 the node Lecturer ∧ Researcher has the discovery time 1 because hasFather is the minimum property following lexicographic order and Lecturer ∧ Researcher is the subject of this triple.

(i, j, l G (n i ), t G (e), l G (n j )) if i > j it means that (l G (n i ), t G (e), l G (n j ))
From Lecturer∧Researcher, we do a Depth-First Search using lexicographic order on properties, subjects and object to obtain the other discovery times.

J = K ∪ G K ∪ H K .
To construct our index structure our algorithm relies on these three definitions and the following principles: if an IRDF graph pattern I has instances in a RDF triple store then all IRDF graph pattern corresponding to a subset of IRDF triples of I has at least as many instances as I in the triple store. Level-wise, this gives rise to an efficient construction of DFSR code hierarchy in three phases.

Phase 1: Initialization and enumeration of size 1 DFSR codes

The initialization builds a mapping between each property, type of subject and object with an integer according to the lexicographic order. For instance, age in Figure 2 is mapped to 1 and Person is mapped to 11. Then to build the first level of the index structure, our algorithm performs a SPARQL query to retrieve all the distinct IRDF graph patterns of size 1 in the triple store. From the list of IRDF graph patterns and the mapping created in the initialization phase, the minimum DFSR codes of size 1 are built. We do not use the kernel notion between levels 1 and 2. A procedure is used to compute the integers corresponding to the property, type of subject and object of each IRDF graph pattern. These integers are the last three elements of the 5-tuple representing the DFSR code (the first and second elements are the discovery times of subject and object). Since we have an IRDF graph pattern of size 1, the discovery time of the subject is 1 and the object one is 2. Algorithm of phase 1 is shown in the following:

procedure DFSROneEdge () P: set of graph patterns of size 1 var level1 = {} identifier = 0, subject, object, property: integer 1. for all edges e in P do 2.

subject= mapping(e.subjects) 3. object = mapping(e.objects) 4.

property = mapping(e.property) 5.

identifier = identifier +1 6.

d=new DFSR(identifier,1,2, subject, property, object) 7.

if not(level1.contain(d)) 8. level1 = level1 ∪ {d} Algorithm 1. Phase 1: Building of level 1 of the index structure.

Phase 2: Building of size 2 DFSR codes

We fill the second level of the index structure with DFSR codes of size 2 built from DFSR codes of size 1. Algorithm 2 searches for couples of DFSR codes of size 1 which share a node and join them to obtain a DFSR code of size 2. We distinguish three cases: Case 1: The 5-tuples of the two joined DFSR codes share an identical subject. In the resulting DFSR code of size 2 the 5-tuple obtained from the minimum DFSR code keep its discovery times (1 for its subject and 2 for its object) and begins the sequence of 5-tuple. The discovery times of 5-tuple arose from the other DFSR code are (1, 3). After building DFSR codes of size 2 we check if the corresponding IRDF graph patterns have at least one instance in the RDF triple store (candidate evaluation phase). Only IRDF graph patterns with at least one instance in the RDF triple store have their minimum DFSR code added in the index structure. For each DFSR code added in the index, our algorithm marks the two DFSR codes joined to obtain it, as they are included in the resulting DFSR code. With this mark we are able at the end of the algorithm to show all IRDF graph pattern in the index or only the IRDF graph pattern with maximal coverage (IRDF graph pattern without mark). Figure 5 shows an instance of DFSR code of size 2 built from 2 DFSR codes of size 1 in case 1. IRDF graph patterns of size 1 joined to build IRDF graph patterns of size 2 that are kept after the evaluation phase are marked as disposable (they become redundant with the IRDF graph patterns of size 2) so at the end we are able to show all IRDF graph patterns in the index structure or only the IRDF graph patterns with maximal coverage (the concise index).

Case 2: The subject of the 5-tuple of one joined DFSR code is identical to the object of the 5-tuple of the other joined DFSR code. In the resulting DFSR code of size 2 the 5-tuple obtained from the minimum DFSR code keep its discovery times (1, 2). If the 5-tuple of the minimum DFSR code is the one that shares its subject, the 5-tuple of the other DFSR code has for discovery times [START_REF] Battle | Bridging the semantic web and web 2.0 with representational state transfer (rest)[END_REF][START_REF] Baget | Griwes: Generic model and preliminary specifications for a graph-based knowledge representation toolkit[END_REF]. Otherwise the 5-tuple of the other DFSR code has for discovery times [START_REF] Basse | Frequent graph pattern to advertise the content of rdf triple stores on the web[END_REF][START_REF] Battle | Bridging the semantic web and web 2.0 with representational state transfer (rest)[END_REF]. The remaining process is similar to the one detailed in case 1.

Case 3: The 5-tuples of the two joined DFSR codes share an identical object. In Inria Building, checking and initializing the DFSR code of size 2 follow the same process as in case 1.

procedure The three previous cases are not disjoint. So, the result of a join operation may be zero to four DFSR codes. During the candidate evaluation phase, DFSR codes are translated into RDF to search if the candidate IRDF graph pattern has at least one instance in the triple store. Therefore, our algorithm constructs from a DFSR code a SPARQL query to search instances of the corresponding IRDF graph pattern.

Phase 3: recursive discovery of graph patterns of size n.

At this step, the join operator is applied on two DFSR codes of size s -1 (s > 2) to obtain a DFSR code of size s. Our algorithm searches for couples of DFSR codes that share a kernel. Before keeping the DFSR code resulting from the join operation, the algorithm checks (i) if the newly generated IRDF graph pattern is not redundant with an IRDF graph patterns already generated at the current level and (ii) if the IRDF graph pattern has at least one instance in the RDF triple store. The DFSR codes of size s -1 joined to obtain a kept DFSR code of size s are marked as disposable. For example the join operation in Figure 5 for all DFSR codes d2 in P do 3.

if(kernel(d1,d2)) then { 4. d = join(d1,d2,kernel) 5.

for each DFSR code di in d 6.

if (1) First (line 6), we search if there is an edge in d G , which has a node with the discovery time t G and which is unique in the kernel. If it is the case, then the corresponding edge in d H provides the discovery time t H1 corresponding to t G . This process could be assimilated to the first step of an isomorphism test between two DFSR codes. A complete isomorphism test is done only when we could not find a unique tuple. In most cases, only this first case is required and the algorithm does not need isomorphism test. Figure 6 shows an example of such a computation. (2) If the first case fails the sub-procedure timePossibles() returns all the candidate discovery times. In our algorithm the sub-procedure chooseOne returns the time t H1 in d H corresponding to t G in d G . To do that, each candidate discovery time is compared to t G by searching every path going through the node corresponding to t G . Figure 7 shows an example of such a case. (1) The two specific tuples are linked to the kernel by one node, with two subcases: a) The two unlinked nodes of the specific edges are different or both typed as literal. In the only resulting graph pattern, the two nodes remain unlinked. We set to 0 the discovery time t H2 in d H corresponding to the discovery time of the other node of e G in d G . The final sorting process resets all the discovery times following a Depth-First-Search. Figure 8 shows an example of such a case. b) The two unlinked nodes of the specific edges are identical and not literals. In this case we obtain two IRDF graph patterns. The first (Figure 9 (1)) is obtained following the case a) with t H2 =0. The second graph pattern (Figure 9 (2)) is obtained by merging the two unlinked nodes of the specific edges. So the discovery time t H2 in d H corresponding to the discovery time of the other specific node of e G in d G is set to the discovery time of the unlinked node of e H in d H . Figure 9 shows such a case.

(2) Only one of the specific tuple is linked to the kernel by two nodes. The second specific edge is linked to the kernel by one node. To optimize, we choose to add the second specific edge to the first IRDF graph pattern thus we do not need to compute the search a second time. In this case we obtain one graph pattern. Like in case 1.a the unlinked node of the second specific edge Inria has its discovery time set to 0. Figure 10 shows an example of such a computation.

(3) The two specific tuples are linked to the kernel by their two nodes. In the unique IRDF graph pattern resulting from the join, the two specific tuples are still linked to the kernel with their two nodes. To retrieve the time t H2 in d H corresponding to the discovery time of the other specific node of e G in d G we rely on the process used to find the discovery time of the first linked node. Figure 11 shows an example. Part 3 (line 12 to 18). After computing the two discovery times t H1 and t H2 , lines 12 to 18 add the 5-tuples e G and e H to DFSR code d H . At first we reset the discovery times of e G with t H1 and t H2 . Then the 5-tuples e G and e H are added in d H that is sorted. As in phase 2, IRDF graph patterns of size s-1 joined to build IRDF graph patterns of size s that are kept after the evaluation phase are marked as disposable. Finally, note that we combine in our algorithm like [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] the growing and checking of subgraphs into one procedure, thus accelerating the mining process. Our algorithm stops at level s if there is no pattern of size s with at least one instance in the store. At the end of this process the DFSR codes kept in the index are translated in RDF graphs and can be loaded in a dedicated named graph of the triple store allowing anyone to query the index in SPARQL. For instance deciding whether a query can find answers in a store amounts to solving an ASK with the pattern of that query on the named graph containing the index.

Experiments and performances

Our algorithm relies on the CORESE/KGRAM ( [START_REF] Corby | Querying the semantic web with the corese search engine[END_REF][START_REF] Corby | Web, graphs and semantics[END_REF]) implementing SPARQL 1.0 and SPARQL 1.1 recommendations with some minor modifications and some extensions. The building of the index of an RDF triple store is done after all the inferences (mostly the RDFS entailments) have been done and the dataset has been enriched with the derivations they produced. More details on the formal semantics of the underlying graph models and projection operator are available in [START_REF] Baget | Griwes: Generic model and preliminary specifications for a graph-based knowledge representation toolkit[END_REF]. Our algorithm is designed for endpoints publishing data. If an endpoint restricts accesses the algorithm is run on the public part for the public index and/or the full index being part of the base will be subject to access control like the rest of the base. In this paper, we focused on generating indexes and considered access control out of scope. We tested our algorithm on a merge of three datasets: personData of DBPedia exhibiting IRDF graph patterns in form of stars (cf. [START_REF] Gandon | Agents handling annotation distribution in a corporate semantic web[END_REF][START_REF] Gandon | Un modele d'index pour la résolution distribuée de requetes sur un nombre restreint de bases d'annotations rdf[END_REF]); a foaf dataset used by our team in teaching semantic Web and ensuring the presence of blank nodes, multi typed nodes and cycles; and a tag dataset extracted from delicious with paths and stars combined as structure of IRDF graph patterns. The resulting dataset contains 149,882 triples and includes arbitrary IRDF graph patterns. We obtain the results shown in Figure 12: RP represents the number of IRDF graph patterns not kept because redundant with other IRDF graph patterns of the same size. M P is the number of IRDF graph patterns marked as disposable. U P is the number of unmarked IRDF graph patterns in the final index structure and JO is the number of join operations done. The sum of M P and U P is the number of IRDF graph patterns in the index structure. Figure 13 shows the number of IRDF graph patterns not kept because they had no instances in the RDF triple store (N F ) and Figure 14 shows the computation times (CT ) in second per level. We can distinguish 4 periods in our computation:

• Level 1: The computation time of the SPARQL query at level 1 depends strongly on the size of the triple store. In our case the computation time of level 1 is greater than computation time of levels 2 to 6 due to the large size of our triple store in relation to the low number of join operation computed at levels 2 to 6.

• Level 2 to 6: The computation time is near zero due to the low number of join operation computed.

• Level 7 to 13: The number of IRDF graph patterns in the index structure and so the number of join operations increases quickly involving a high number of triple store access Inria • Level 14 to 22: NF and RP are the two ways used to avoid an overflow of IRDF graph patterns. From level 14 all the candidate IRDF graph patterns have at least one instance in the RDF triple store (N F = 0 in Figure 13). The number of IRDF graph patterns generated decreases and is equal to 1 at level 22. From level 14 the algorithm converges quickly and the computation time is near zero from level 19.

The percentage of IRDF graph patterns marked disposable is 90.44%. The number of redundancies between join operations is high and one of our perspectives is to reduce it. Complexity Analysis. In graph query processing, the complexity time of level 1 is Θ(na) + T q where na is the number of triples in the RDF store and T q is the time to compute the Sparql query of level 1. T q depends also to the number of triples in the RDF store. The complexity time of level 2 is Θ(nb 2 1 )(T q 2 + O(ni 2 )) where nb i is the number of IRDF graph patterns of size i (i > 0), ni 2 is the average number of instances of IRDF graph pattern of size 2 and T q 2 is the average time to compute a Sparql query finding instances of a IRDF graph pattern of size 2. The complexity time of level s > 2 is Θ(nb 2 s-1 [s s + T q s + ni s ]) where s is the level, T q s is the time to compute the Sparql query finding instances of an IRDF graph pattern of size s, ni s is the average number of instances of IRDF graph pattern of size s in the triple store.

Incremental changes of the index when updating the store

Insertion or deletion of annotations in the triple store may cause changes to the index and it is important to have an incremental algorithm to update it. We use listeners on the triple store to register for events we are interested to update the index.

Insertion of annotations in the triple store.

When an annotation, that represented by a RDF graph containing several triples, is inserted, we distinguish four phases to update the index structure: (1) initialization, (2) update of level 1, (3) update of level 2, (4) update of level n > 2. We perform a SPARQL query to retrieve the IRDF graph patterns of size 1 from the given annotation and build their corresponding DFSR codes using the procedure DFSROne (algorithm 1). From the list of DFSR codes of size 1 obtained in this phase the algorithm updates the index structure. Phase 2 -update of level 1: We check if each DFSR code in the list obtained in the initialization phase is already or not in the level 1 of the index structure. If a DFSR code is not in the index structure it is inserted at the level 1. If a DFSR code is already in the index structure it makes no change to the level 1 of the index structure. In any case we keep the corresponding DFSR code in the list of inserted codes that may cause insertions at level 2 of the index structure. Phase 3 -update of level 2: The DFSR codes, in the list of inserted DFSR codes at level 1, are joined with the other DFSR codes at level 1 which 5-tuple share at least one node following algorithm 2. The resulting DFSR codes are classified in three categories: Category 1: The resulting DFSR code is already in the index and was generated using the same join operation (same DFSR codes joined). This DFSR code makes no change to the level 2. Category 2: The resulting DFSR code is already in the index structure and was generated using another join operation. The DFSR code is inserted in level 2 and marked disposable. Category 3: The resulting DFSR code is not in the index structure. The new DFSR code is inserted in the level 2 with a new identifier. At the end of each category we add the identifier of this DFSR code in the list of inserted code because it may cause insertions at level 3. Phase 4: update of level n (n > 2). The DFSR codes in the list of inserted codes at level n-1 are joined with the other DFSR codes at level n-1 which share a kernel following algorithm 3. The resulting DFSR codes are classified in three categories as in phase 3 and their identifiers are added in the list of inserted codes at level n.

Our algorithm stops at level s (s > 1) if there is no identifier of DFSR code in the list of inserted codes at level s -1. It means that we have no DFSR code in level s generated from a DFSR code in the list built at level s -1. Complexity Analysis. The complexity time of the update of level 1 is Θ(nb 1 ) where nb 1

Inria

Figure 14: Computation time per level is the number of IRDF graph patterns of size i (i > 0). The complexity time of level 2 is Θ(nb 1 * nb 2 + nb 1 (T q 2 + ni 2 )) where ni 2 is the average number of instances of IRDF graph pattern of size 2 and T q 2 is the average time to compute a Sparql query finding instances of an IRDF graph pattern of size 2. The complexity time of level s > 2 is Θ(nb s-1 (nb maj (s s + nb s + T q s + ni s ))) where s is the level, nb maj is the number of IRDF graph patterns updated in level s -1, T q s is the time to compute the Sparql query finding instances of an IRDF graph pattern of size s, ni s is the average number of instances of IRDF graph pattern of size s in the triple store.

Deletion of annotations in the triple store

When an annotation is deleted from the triple store we distinguish 3 phases to update the index structure: (1) initialization, (2) update of level 1, (3) update of level n > 1. Phase 1 -Initialization phase: The process is identical with the initialization phase in case of insertion of annotation. At the end of this phase we obtain a list of DFSR code of size 1 corresponding to the IRDF graph patterns build from the deleted annotation. Phase 2 -update of level 1: For each DFSR code in the list obtained in initialization phase, we check with a SPARQL query if it has still some instances in the triple store to keep it in the index. We distinguish two cases: Case 1: An IRDF graph pattern has still instances in the triple store. We add the identifier of this DFSR code obtained in phase 1 in a list named checkList because it may cause deletions in level 2. Case 2: An IRDF graph pattern has no instance in the triple store. The DFSR code obtained in phase 1 is deleted from the level 1 of the index structure and its identifier is added in a list named delList because all the DFSR codes of level 2 generated from it have to be deleted. Phase 3: update of level n (n > 1). We iterate on the DFSR codes previously inserted in delList and checkList. Iteration on delList codes: Each DFSR code of level n generated from a DFSR code which is in the delList list of level n -1 is deleted from the index structure and we add it in the delList list of level n. Iteration on checkList codes: Each DFSR code of level n generated from a DFSR code which is in the checkList list of level n -1 is checked in the triple store. We distinguish two cases: Case 1: There is no instance of the IRDF graph pattern corresponding to the DFSR code in the triple store. The DFSR code is deleted from the index structure and we add it to delList at level n. Case 2: There is at least one instance of the IRDF graph pattern corresponding to the DFSR code in the triple store. We add the DFSR code to the checklist of level n. To update the level n + 1 the lists checklist and delList generated at level n are used. The algorithm stops when the higher level of the index has been updated or when the lists checkList and delList at level n -1 are empty. Complexity Analysis. The complexity time of the update of level 1 is Θ(nb 1 * T q 1 ) where nb i is the number of IRDF graph patterns of size i (i > 0) and T q i is the average time to compute a Sparql query finding instances of a IRDF graph pattern of size i > 0. The complexity time of level s > 1 is Θ(nb 2 s (nbd s-1 + nbv s-1 ) + nbd s-1 * nbv s-1 * T q s ) where nbd s-1 and nbv s-1 are respectively the number of graph patterns in delList and checkList of level s -1.

Related work

A usual representation of an index structure is a hierarchy organized into different levels according to the size of the indexed items. In the literature, approaches differ with regards to the structure of the indexed items. By extending the join index structure studied in relational and spatial databases, [START_REF] Han | Join index hierarchies for supporting efficient navigations in objectoriented databases[END_REF] proposed, as basic indexing structure: pairs of identifiers of objects of two classes that are connected via direct or indirect logical relationships. [START_REF] Stuckenschmidt | Index structures and algorithms for querying distributed rdf repositories[END_REF] extended this approach to propose an index built as a hierarchy of paths. [START_REF] Vanetik | Computing frequent graph patterns from semistructured data[END_REF] and [START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] proposed a hierarchical index structure including both path-patterns and star-patterns. [START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] showed some disadvantages of path-based approaches, and in particular that part of the structural information is lost and that the set of paths in a dataset is usually huge. To overcome these difficulties, [START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] proposed to use frequent subgraph patterns as basic structures of index items since a graph-based index can significantly improve query performance over a path-based one. The approaches to frequent graph pattern discovery iterate mainly on two phases: the generation of candidate patterns and the evaluation of candidate patterns. The key computational issues are (i) managing and processing redundancies (this problem is particularly challenging due to the NP-hard subgraph isomorphism test), (ii) reducing the size of the index structure and (iii) proposing a join operator to compute efficiently a graph pattern of size s from two graph patterns of size s-1 sharing s-2 edges. Among the different algorithms we distinguish mainly two approaches to deal with redundancies: (1) Algorithms using a canonical form to efficiently compare two graph representations and rapidly prune the redundancies in the set of generated candidates. [START_REF] Inokuchi | An apriori-based algorithm for mining frequent substructures from graph data[END_REF] uses an adjacency matrix to represent a graph, defines a canonical form for normal forms of adjacency and proposes an efficient method to index each normal form with its canonical form. [START_REF] Han | Fsp: Frequent substructure pattern mining[END_REF][START_REF] Maduko | Graph summaries for subgraph frequency estimation[END_REF][START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF][START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] rely on a tree representation which is more compact than an adjacency matrix and maps each graph to a unique minimum DFS code as its canonical label. To discover frequent graph-patterns, [START_REF] Vanetik | Computing frequent graph patterns from semistructured data[END_REF] builds candidate graph patterns using frequent paths and a matrix that represents the graph with nodes as rows and paths as columns. [START_REF] Vanetik | Computing frequent graph patterns from semistructured data[END_REF] uses a canonical representation of paths and path sequences and defines a lexicographical ordering over path pairs, using node labels and degrees Inria of nodes within paths. (2) Other algorithms propose a join operator such that every distinct graph pattern is generated only once. Indeed the major concerns with the join operation are that a single join may produce multiple candidates and that a candidate may be redundantly proposed by many join operations [START_REF] Kuramochi | Frequent subgraph discovery[END_REF]. [START_REF] Huan | Efficient mining of frequent subgraphs in the presence of isomorphism[END_REF] introduces a join operation such that at most two graphs are generated from a single join operation. The FFSM-Join of [START_REF] Huan | Efficient mining of frequent subgraphs in the presence of isomorphism[END_REF] completely removes the redundancy after sorting the graphs by their canonical forms that are a sequence of lower triangular entries of a matrix representing the subgraph. To reduce the database accesses some approaches like [START_REF] Kuramochi | Frequent subgraph discovery[END_REF] use the monotony of the frequency condition to eliminate some candidates. As several approaches of frequent subgraph discovery, ( [START_REF] Huan | Efficient mining of frequent subgraphs in the presence of isomorphism[END_REF][START_REF] Inokuchi | An apriori-based algorithm for mining frequent substructures from graph data[END_REF][START_REF] Kuramochi | Frequent subgraph discovery[END_REF][START_REF] Yan | gspan: Graph-based substructure pattern mining[END_REF] for instance) we generate candidate graph patterns of size s by joining two patterns of size s -1. To avoid joining each pair of patterns we add information in each DFSR code to know exactly which pairs of patterns share a kernel and thus can be joined. In the candidate evaluation phase, most of the algorithms ( [START_REF] Huan | Efficient mining of frequent subgraphs in the presence of isomorphism[END_REF][START_REF] Inokuchi | An apriori-based algorithm for mining frequent substructures from graph data[END_REF][START_REF] Kuramochi | Frequent subgraph discovery[END_REF] for instance) compute the frequencies of candidates with respect to the database content and all frequent subgraph patterns are kept in the index structure. Our index is a hierarchy, not a partition as proposed by [START_REF] Dolby | Scalable grounded conjunctive query evaluation over large and expressive knowledge bases[END_REF] and [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF], and it is designed to be used by machines and humans to understand the content that can be found in a triple store. Their partition may look like the roots of our index but the canonical form defined in [START_REF] Fokoue | The summary abox: Cutting ontologies down to size[END_REF] is not equivalent to ours. We also collapse multiple instantiations into conjunctive types wherever possible. In addition, our approach does not require a DL reasoner, does not require the schemas for coherence checking and does not limit to conjunctive queries. When a class or a relationship between two classes is updated [START_REF] Han | Join index hierarchies for supporting efficient navigations in objectoriented databases[END_REF] proposes an incremental update propagation of their partial and complete join index hierarchy starting at the level 1. The update affects only one base join indice (basic element of the index) at level 1 and may affect some join indices at higher levels exactly determined by [START_REF] Han | Join index hierarchies for supporting efficient navigations in objectoriented databases[END_REF]. The base join index hierarchy [START_REF] Han | Join index hierarchies for supporting efficient navigations in objectoriented databases[END_REF] is updated using only the first step of the algorithm proposed for partial and complete join index hierarchy. To handle insertion or deletion of graphs in a graph database, [START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] proposes an index maintenance algorithm. To update the index [START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] simply update for each involved fragment its list of graphs containing this fragment. [START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] notes the quality of the index degrades after a lot of insertions and deletions and propose recomputing the index from scratch. We proposed to use patterns as basic structures of index items like [START_REF] Yan | Graph indexing: A frequent structure-based approach[END_REF] but extended to directed labelled multigraph data structure in RDF. To eliminate the redundancies in producing the patterns our algorithm combines the two above-cited alternative solutions during the candidate generation phase: (1) we use trees to represent IRDF graph patterns and a DFSR coding to efficiently compare two IRDF graph patterns and to eliminate redundancies. Then we propose a join operator on two DFSR codes to generate at most four different DFSR codes. Our DFSR coding already extending [START_REF] Maduko | Graph summaries for subgraph frequency estimation[END_REF] consists in identifying exactly how edges must be linked during the join operation. In some cases the identification of join point is costly in term of CPU time because it is similar to an isomorphism test. (2) in the candidate evaluation phase the triple store is accessed to eliminate patterns without instance. Note that the pruning step in the candidate evaluation phase is not necessary in our case because our join operator generates only patterns which respect the monotony of the frequency. Note also that we improve the algorithm we proposed in [START_REF] Basse | Frequent graph pattern to advertise the content of rdf triple stores on the web[END_REF] to address cyclic graphs, blank nodes and multityped resources. We also added incremental algorithms to update the index when the content of the store changes.

Conclusion

In this paper, we presented incremental algorithms to extract and maintain a compact representation of the content of a triple store. We proposed a new DFS coding for RDF graphs, we provided a join operator to significantly reduce the number of generated patterns and we gave the possibility to reduce the index size by keeping only the graph patterns with maximal coverage. In this paper, the motivating scenario was the case of applications exploiting distributed triple stores and justifying the needs for indexes in order to allow humans and machines to know what kinds of knowledge contributions they can expect from a source. The problem of decomposing a query and routing the sub-queries using these indexes remains a research challenge in itself and a perspective for future work.

Figure 1 :

 1 Figure 1: RDF graphs from of DBPedia and DBLP dataset

Figure 2 :

 2 Figure 2: Example of RDF store

  Definition 1.(RDF triple, RDF graph). Given U a set of URI with optional fragment identifier at the end (URIref), L a set of plain and typed Literal and B a set of blank nodes. A RDF triple is a 3-tuple (s, p, o) ∈ {U ∪ B} × U × {U ∪ B ∪ L}. s is the node subject of the RDF triple, p the predicate of the triple and o the node object of the triple. A RDF graph is a set of RDF triple. Definition 2.(RDF typed triple, RDF untyped triple.) A RDF typed triple is a 3-tuple (s, p, o) ∈ {U ∪ B} × {rdf : type} × {U ∪ B ∪ L}. A RDF untyped triple is a 3-tuple (s, p, o) ∈ {U ∪ B} × {U \ rdf : type} × {U ∪ B ∪ L}. Definition 3.(Type of node.) In a RDF graph G, if a node n is subject of one RDF typed triple (n, rdf : type, t) then its type or class is the object (t) of this RDF typed triple. If a node n is

Figure 3 :

 3 Figure 3: Graphical notation form and linear textual form

Figure 4 :

 4 Figure 4: Graph pattern and its minimum DFSR code

Figure 5 :

 5 Figure 5: Example of join on two DFSR codes with identical subject

  is successful (meaning we have at least one instance of Lecturer ∧ Researcher with a name and a father in the RDF triple store) and the IRDF graph pattern of size 1 [Lecturer∧ Researcher:*]-name->[Literal:*] and [Lecturer ∧ Researcher:*]-hasParent-> [Male ∧ Person:*] are marked as disposable. So at the end of the process, all unmarked IRDF graph patterns represent the IRDF graph patterns with maximal coverage. The join sub procedure returns one or two DFSR codes. The procedure DFSRN checks for each DFSR code returned if it is not redundant and has at least one instance.procedure DFSRNEdges (P: set of DFSR code previous level) var levelN = {} identifier = 0 1. for all DFSR codes d1 in P do 2.

Algorithm 4 .

 4 Join operator for phase 3 Line 1 and 2 of the join procedure take away from each DFSR code the 5-tuple corresponding to the Specific IRDF triples of G and H in relation to K. In line 3 we keep in d G and d H the 5-tuples corresponding to kernel k. We can decompose the remaining lines in three parts: Part 1 (line 1 to 9). The aim of the first part of the algorithm is to find the discovery time t H1 to link one of node of the specific 5-tuple in the first DFSR code d G to the kernel of the second DFSR code d H under consideration to generate a new DFSR code of size s. After Line 3 we have in d G and d H only the 5-tuples in kernel k. Lines 4 and 5 retrieve the node of e G (resp. e H ) and its discovery time t G (resp. t H ) with respect to the kernel in d G (resp. d H ). To map the discovery time t G in d G to a discovery time t H1 in d H we distinguish two cases:

Figure 6 :

 6 Figure 6: Example of joining two IRDF graph patterns of size 2, case 1.

Figure 7 :

 7 Figure 7: Example of joining two DFSR codes of size 4, case 2.

Figure 8 :

 8 Figure 8: Join two graph patterns, when the two unlinked nodes of the specific edges are different.

Figure 9 :

 9 Figure 9: Join two graph patterns when the two unlinked nodes of the specific edges are identical.

Figure 10 :

 10 Figure 10: Join two graph patterns with one of specific edges linked to kernel by two nodes.

Figure 11 :

 11 Figure 11: Join two graph patterns with the two specific edges linked to kernel by two nodes.

Figure 12 :

 12 Figure 12: Number of IRDF graph patterns, redundancies and join operation used by level

Figure 13 :

 13 Figure 13: Number of IRDF graph patterns not kept

23 10 4and performances 14 5

 1014 Indexed item and DFSR CODING 4 Detailed induction algorithm to create a full index 7 3.1 Phase 1: Initialization and enumeration of size 1 DFSR codes . . . . . . . . . . . 7 3.2 Phase 2: Building of size 2 DFSR codes . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Phase 3: recursive discovery of graph patterns of size n. . . . . . . . . . . . . . . Experiments Incremental changes of the index when updating the store 15 5.1 Insertion of annotations in the triple store. . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Deletion of annotations in the triple store . . . . . . . . . . . . . . . . . . . . . . 17

  is a backward edge. We adopted this coding to generate canonical labels for RDF graph patterns and called them DFSR codes. Definition 8.( DFSR code.) A DFSR code D of an IRDF graph pattern I is a sequence of 5-tuple such that for each untyped triple (s, p, o) in I corresponds a 5-tuple (i, j, N (t s ), N (p), N (t o )) in D where t s is the type of node s, t o is the type of node o, N maps a string (type of node or property in I) to integer in such way that the resulting integer maintain lexicographical order of string, i (resp. j) denote the position of node s (resp. o) following a Depth-First Search in the set of RDF untyped triple of I. Definition 9.(Size of DFSR code.) The size of a DFSR code is the number of its 5-tuples. An IRDF graph pattern may have many DFSR codes and we define a linear order in a set of DFSR to determine a canonical label of an IRDF graph pattern. Definition 10.(5-tuple order.) 5-tuple order is a linear order (≺ T ) in a 5-tuple set defined as follows. If t 1 = (a 1 , a 2 , a 3 , a 4 , a 5 ) and t 2 = (b 1 , b 2 , b 3 , b 4 , b 5 ) are two 5-tuples of integer then • t 1 ≺ T t 2 if and only if ∃i, 1 ≤ i ≤ 5, such that a j = b j if j < i and a i < b i . • t 1 = t 2 if and only if ∀i, 1 ≤ i ≤ 5, a i = b i . If d 1 = (e 1 , e 2 , . . . , e n ) and d 2 = (f 1 , f 2 , . . . , f n ) are two DFSR codes of size n with e k and d k 1 ≤ k ≤ n are 5-tuples, then • d 1 ≺ D d 2 if and only if ∃i, 1 ≤ i ≤ n, such that e j = f j , j < i and e i < f i , • d 1 = d 2 if and only if ∀i, 1 ≤ i ≤ n, e i = f i .

	Definition 11.(DFSR order.) DFSR order is a linear order (≺ D ) in a DFSR code set defined
	as follows. Definition 12.(Minimum DFSR code.) Given an IRDF graph I and its set of DFSR codes D,
	the minimum DFSR code of I is the minimum DFSR code in D following the DFSR order ≺ D .
	The minimum DFSR code is a canonical label of I.
	To compute DFSR codes, we replace at first each type of node and property in the RDF triple
	store by an integer ID in such way to maintain lexicographical order of string (URI type and
	URI property). From the RDF triple store of Figure 2 we obtain the following mapping of
	classes and properties: age = 1, city = 2, hasAddress = 3, hasF ather = 4, hasf riend = 5,
	hasP arent = 6, name = 7, street = 8, Lecturer ∧ Researcher = 9, M ale ∧ P erson = 10,
	P erson = 11, Resource = 12.

  Algorithm 3. Phase 3: Building the level s (s > 2) of the index structureThe detail of the join operator is shown in the following.subProcedure join (d G , d H , k) 1. e G = edgeNotInKernel(d G ,k) 2. e H = edgeNotInKernel(d H ,k) 3. d G = d G -e G ; d H = d H -e H 4. t G = linkToKernel(d G , e G ) Inria 5. t H = linkToKernel(d H , e H ) 6. t H1 = uniquEdgeThrougth(d G ,d H ,t G ) H2 =secondTime(e H ,e G ,t G ,t H ) 12. d H .setKernel(concat(d G .id,d H .id)) 13. e G .setKernel(d G .id) 14. e H .setKernel(d H .id) 15. for all time t in t H2 do { 16.

	7. if t H1 < 0 then { //no unique time
	8.	times = timesPossible()
	9.	t H1 = chooseOne(times, d G , d H )
	10. }
	11. t e G .setDiscoveries(t H1 ,t)
	17.	d H .addEdge(e G ) ; d H .addEdge(e H )
	18.	d H .sort()
	19.	res.add(d H )
	20. }
	return res
			(di not in levelN) {
		7.	if(di is frequent) then {
		8.	di.kernel=concat(d1.identifier,
		d2.identifier)
		9.	d.identifier=identifier+1
		10.	identifier =identifier+1
		11.	levelN = levelN ∪ di
		12.	marked(d1)
		13.	marked(d2) }}
		14.	else { //di already in levelN
		15.	marked(d1)
		16.	marked(d2) } }

http://www.w3.org /RDF

http://www.w3.org/2007/05/SPARQLfed/

http://www.w3.org/TR/rdf-SPARQL-query

http://dbpedia.org

http://www4.wiwiss.fu-berlin.de/dblp/ RR n°7941

RR n°7941

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399