Konstantinos Karanasos

Ioana Manolescu

P2P Views Over Annotated Documents

We consider the efficient, scalable management of XML documents in structured peer-to-peer networks based on distributed hash table (DHT) indices and present an approach for answering queries by exploiting materialized views deployed in the DHT network independently by the peers. We describe how our approach can be employed to also handle RDF-annotated documents and provide algorithms to index and materialize the views in the DHT, as well as rewrite the queries using such views.

I. INTRODUCTION

In recent years, more and more software tools, including the most user-friendly ones, such as text editors, have started to export their contents into some structured document format, such as HTML or XML. Moreover, large-scale organizations need to produce, deploy and exploit large volumes of data, and in particular structured XML data. Publication of such resources is inherently distributed. One could consider uploading all published content to a single site. However, this raises some scalability problems, which may require acquiring dedicated hardware, and introduces a single point of failure. In order to deal with such content, we have presented the VIP2P platform [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF], which enables efficient management of XML documents on a distribute hash table (or DHT, in short [START_REF] Dabek | Towards a common API for structured P2P overlays[END_REF]). VIP2P exploits the materialized views deployed on the DHT independently by the peers, to answer an interesting dialect of tree pattern queries.

At the same time, annotations have become very popular as a means to add information to a given document. HTML Meta tags, Dublin Core [START_REF]Dublic core metadata initiative[END_REF] and social networks' tagging are among the most common methods to express annotations. Here, we designate by annotation any simple statement in the style of the RDF standard [START_REF]RDF: Concepts and Abstract Syntax[END_REF], attaching to a given subject (or resource, such as a document, or a small portion of text) a named property, with a certain value. Using documents and annotations provides the flexibility to handle a variety of application scenarios in which documents or RDF alone would not be suitable. As an example, think of a Web page containing a news item, annotated by a human reader or a text analysis tool to point out the person names appearing in the page, her positions within various institutions etc. or to express subjective opinions regarding the document. One could suggest modifying the Web page to incorporate the additional information of the annotations. However, this is not always feasible, since the author of the annotations may be distinct from, and have no control over, the author of the original document; furthermore, the original document should be readable also to those that are not interested in the extra information. Using only RDF to model all the content, on the other hand, is not appropriate since end users are familiar with, and expect to use structured documents.

To extent the capabilities of VIP2P, we have built AnnoVIP, which is capable of handling more complex queries and views and, thus, addresses applications such as the join manipulation of documents and annotations. At the core of content sharing in AnnoVIP stand materialized views over the whole network content. Each peer may define views, describing patterns of inter-connected documents and annotations, that the peer is interested in. Once a view is established, its definition will be indexed in the DHT network. When documents or annotations are published, by looking up in the DHT, the publishing peer learns if its new content may contribute to some view, and if yes, it sends the respective data to the view. After publication, this lookup is repeated periodically to identify contributions to views defined later on. Thus, views are updated over time, in the manner of long-running, de-centralized subscriptions.

A further step in content sharing in AnnoVIP is materialized view-based query rewriting. Here, we consider the situation when a peer issues an ad-hoc query, which it has not declared as a local view. The peer then looks up in the DHT the existing view definitions, and may rewrite its query based on the views. From a rewriting, a distributed query plan is derived and evaluated. When available, pre-computed materialized views may lead to efficient query evaluation.

The novelty of AnnoVIP stems from its built-in dual support for documents and annotations at arbitrary granularity (one can annotate a document, an element, or even a text fragment). Maintaining and exploiting materialized views for efficient query processing, over such interconnected corpora of documents and annotations requires new algorithms, further complicated by the distribution on the DHT. This report is organized as follows. Section II discusses the data model of AnnoVIP and Section III presents the query and view language used. View materialization is described in Section IV, whereas view-based query rewriting is presented in Section V. We relate AnnoVIP to existing works in Section VI.

II. DATA MODEL

The basic kind of content we consider consists of XML documents. Each document d published by peer p has an URI allowing to uniquely determine d inside p and in the whole network.

Since we consider handling annotated documents as a very significant application that could be addressed by our system, we have enabled AnnoVIP to target content at very different granularity levels. Thus, one can refer to a document, an element, a text node, or even a fragment of text, e.g., a phrase of particular significance, or a person's name inside a text. Therefore, we consider that any fragment of a document d, whatever its size, has an URI. Such URIs are implemented by (offset, length) pairs identifying the fragment in the serialization of d. Moreover, the URI of d can be easily obtained from the URI of any fragment of d. This holds in many common URI schemes, such as XPointer [START_REF]XML Pointer Language[END_REF], where d.U RI is a prefix of all the URIs of elements in d.

Our model assumes that any XML element has a child labeled URI, whose value is the actual URI of the element. However, URI-labeled nodes are virtual, that is, they do not actually appear in the elements (although as we will explain, they are needed for querying documents and annotations). In a similar manner, any fragment can be seen as a node, endowed with an URI.

The second class of content we consider concerns annotations, which may be either produced by human users, possibly with the help of some tools, or by automated modules (e.g. recognizing named entities within a document). For simplicity, we consider that all annotations have been brought to an RDF format. Thus, the basic unit of content here is a triple t=(s, p, o), specifying the value o of property p for the resource s. We assume triples are serialized following the XML syntax for RDF [START_REF]RDF/XML Syntax Specification[END_REF]. As customary in RDF, s, p and o range over the set of all URIs, plus the set of String values in the case of o.

III. QUERY AND VIEW LANGUAGE

Views and queries are defined in the same language, which can be seen as joins over a specific flavor of tree patterns. VIP2P supports a tree pattern dialect P, a comprehensive presentation of which can be found in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF]. Here we provide a brief overview of P and then we describe how it was extended to the dialect P for the needs of AnnoVIP.

Each tree pattern node carries a name label, corresponding to an element or attribute name or a word appearing in a text node in some document or annotation (we will use w to denote the word w). Pattern edges correspond either to the child (/) or the descendant (//) relationships between nodes; we assume that a text word is a child of its closest enclosing element or ancestor node. Due to the special role we attach to URIs, we impose that an URI-labeled view node always appears as a child (not descendant) of another node in the view. Each node may be decorated with zero or more among the following labels: id, standing for structural identifier 1 ; cont, standing for the full XML subtree rooted at the node; and val, standing for the concatenation of all text descendants of the node, in document order. An id, cont or val label attached to a node 1 By comparing the structural identifiers of nodes n 1 and n 2 , one can decide n 1 is an ancestor of n 2 or not. Many popular examples exist, e.g. [START_REF] Al-Khalifa | Structural joins: A primitive for efficient XML query pattern matching[END_REF], [START_REF] Tatarinov | Storing and querying ordered XML using a relational database system[END_REF].

denotes the fact that the structural ID, the content or the value, respectively, of the node belong to the pattern result. Finally, each node may be labeled with a predicate of the form [val=c] where c is some constant.

We have generalized the tree pattern language to include patterns consisting of more than one tree patterns, joined using some value equality predicates. Formally, let tp 1 , tp 2 , . . . , tp n ∈ P be tree patterns. We define a pattern p ∈ P by combining the above tree patterns using value joins between the values of some elements of the tree patterns, and denote it as the algebraic expression p = σ pred (tp 1 × tp 2 × . . . × tp n ), where pred is the conjunction of all value equality predicates. Thereinafter, we use p.t 1 , p.t 2 , . . . , p.tp n to designate the tree patterns included in the pattern p.

Due to the value joins, more complex views and queries can be defined now. Furthermore, value joins are an important feature for the exploitation of documents and annotations.

In fact, whenever one wants to retrieve (some part of) a document that is the subject of an annotation, one join is needed; similarly, whenever one wants to "chain" two triples by ensuring that the subject of one is the value of the other, a similar join is needed. These joins are not a feature of one given RDF serialization; rather, they derive from the model built in the very idea of annotation, which is: identify resources by their URI, and have annotations refer to them by their URIs. Value joins are thus naturally present whenever one seeks to jointly exploit resources and related annotations.

Pattern Semantics

In [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF] we defined an embedding φ : tp → d of the tree pattern tp ∈ P in document d as a function associating d nodes to tp nodes, preserving node labels and ancestor-descendant (and parent-child) relationships [START_REF] Amer-Yahia | Tree pattern query minimization[END_REF]. For a document set D, the semantics of tp over D, denoted tp(D), are defined as the concatenation of all tp(d), d ∈ D. Let now p be a pattern belonging to the generalized pattern language P presented above, with p.tp 1 , p.tp 2 , . . . , p.tp n being the tree patterns included in p and pred the conjunction of the value equality predicates. We observe that the embedding of each of these tree patterns may be found in different documents of D. We define the semantics of p over D, denoted p(D), as the algebraic expression p(D) = σ pred (p.tp 1 (D) × p.tp 2 (D) × . . . × p.tp n (D)). More intuitively, p(D) represents the join (according to the value equality predicates included in pred) of the semantics of p.tp 1 , p.tp 2 , . . . , p.tp n over D.

IV. VIEW MATERIALIZATION

Assume peer p decides to establish a view v ∈ P . Then, when a peer p d publishes a document d affecting v, p d needs to find out that v exists. To that effect, view definitions are indexed for document-driven lookup as follows. For any label (node name or word) appearing in the definition of the views v 1 , v 2 , . . . , v k , the DHT will contain a pair where the key is the label, and the value is the set of view URLs v 1 , v 2 , . . . , v k .

When a peer p d publishes a document d, p d performs a lookup with all d labels (node names or words) to find a superset S a of the views that d might affect. Then, p d evaluates v(d) for each v ∈ S a . The case of materializing views consisting of only one tree pattern is presented in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF]. Assume now that a view in S a contains more than one tree patterns and some value joins between them. It is not possible to materialize such a view only by considering document d, as p d needs to know if and where, in the whole network, some other content may satisfy a value join with d. A first solution could be to maintain, instead of a tree pattern join view, one view per each tree pattern, and compute view tuples incrementally as new tuples are added to each tree pattern, in the style of incremental maintenance for join views [START_REF] Gupta | Maintaining views incrementally[END_REF]. However, this may lead to accumulating an unbound amount of data, if e.g. many documents matching one view tree pattern are published, which do not join with any other document or annotation.

We will now describe a more efficient technique for the case when join predicates do not involve URI attributes. Assume, as above, peer p d publishes a document d. Let v ∈ S a be a view consisting of two tree patterns, tp 1 and tp 2 , with a value join between node n 1 of tp 1 and n 2 of tp 2 . If there is an embedding of tp 1 in d, instead of storing the whole tuple in tp 1 , we store only the value of n 1 and the URI of d. Assume now a document d is published and there is an embedding of tp 2 in d . The publishing peer searches the (value,URI) pairs and finds immediately the documents with which he could join, by comparing his n 2 value with the available n 1 values. Thus, he receives the appropriate documents, joins with them and provides new tuples to the view extent.

Moreover, we have devised a particular technique to treat the materialization of views including joins over URI attributes. This is the case whenever a view queries documents with annotations, as the view will involve joins over virtual URI attributes. Notice that annotations are necessarily published after the content they refer to. Thus, when a new document is published, it will not contribute (yet) to join views requiring specific annotations over the document. On the contrary, when a newly published annotation matches a join view, the URI of the annotated element appears in the annotation and the document enclosing this element can thus be identified. The peer that has published the annotation then asks the document peer to compute its corresponding tuples, which are joined with the tuples extracted from the annotation and sent for storage at the site of the view.

V. VIEW-BASED QUERY REWRITING

The rewriting of a query using a set of materialized views is in the crux of the problem we examine. Let q be a P query, and e(v 1 , v 2 , . . . , v n ) be an algebraic expression over the P views in V. We say e(V) is an equivalent rewriting of q, if and only if for any database D, e(v 1 (D), v 2 (D), . . . , v k (D)) = q(D). Several new algorithms are presented in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF], which are, though, restricted to tree pattern views and queries. Here we provide an extension to these algorithms to support the rewriting of tree pattern join queries by possibly exploiting tree pattern join views.

Algorithm 1: Subset-enum

Input : tree pattern query tq ∈ P, tree pattern view set TW (views belonging to P) Output: all minimal canonical rewritings of tq based on TW P R ← ∅ First, we present a slightly different version of the algorithm Subset-enum (Algorithm 1), which was initially described in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF]. This algorithm takes as input a tree pattern query tp ∈ P and a set of tree pattern views TW (belonging to P), and returns all minimal canonical rewritings of tq based on TW. It iterates over all subsets QTW ⊆ TW whose cardinality is at most equal to the number of nodes of tq (|QTW| ≤ |tq|), all embedding combinations from the views into tq, and accumulates rewritings in the set P R. A rewriting r is non-minimal if another rewriting r ∈ P R uses a subset of r's views. We notice that in line 4, the algorithm Views-torewriting is invoked. This algorithm, which is also described in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF], takes a tree pattern query, a set of tree pattern views, as well as their embeddings to the query, and builds a single algebraic expression over all the views, or fails.

1 foreach QTW = {v 1 , v 2 , . . . , v k } ⊆ TW, |QTW| ≤ |tq| 2 do foreach tuple φ 1 , φ 2 , . . . φ k of embeddings from 3 v 1 , v 2 , . . . ,
We now present the algorithm Pattern-rewriting (Algorithm 2), which executes an end-to-end rewriting, given a tree pattern join query q ∈ P and a set of tree pattern join views V. The algorithm starts by executing a pruning step (line 1), during which, any view that will certainly not participate in the rewriting of q is pruned, whereas the rest are added to the set W. In particular, if a view v ∈ P appears in a rewriting of q, then there exists an embedding φ : qt → q for every tree pattern qt ∈ P included in v, such that:

1)

φ preserves node names 2) if n is a parent of m in v, φ(n) is an ancestor of φ(m) 3) if m has a value predicate [val = c 1 ] in q and φ(n) = m, for some v node m, then m must not have a value predicate [val = c 2 ], if c 1 = c 2 .
Moreover, let m be a node in a tree pattern t 1 and n be a node in a tree pattern t 2 . Let φ 1 and φ 2 be the embeddings of t 1 and t 2 in q, respectively. If t 1 is joined with t 2 through the predicate m.val = n.val, then φ 1 must be joined with φ 2 through the predicate φ 1 (m).val = φ 2 (n).val.

View expansion (line 2) then follows. This step is described in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF] in detail, so we don't further analyze it here. Once the view expansion is completed, the algorithm iterates over all Algorithm 2: Pattern-rewriting Input : query q ∈ P consisting of the tree patterns q.t 1 , q.t 2 , . . . , q.t m ∈ P, view set V (views belonging to P ) Output: all minimal canonical rewritings of q based on V U ← prune(V, q) subsets W ⊆ W, trying to find all possible rewritings using the views in W. To this end, in each iteration, a set TW is built (line 5), containing all the tree patterns (belonging to P) appearing in the views (belonging to P ) of W. We should remark here that so as to reduce our search space, we used the lemma concerning the bound on the minimal rewriting size, proven in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF], according to which, a minimal canonical rewriting of q uses at most |q| views, where |q| is the number of nodes that q contains. Then, every tree pattern qt ∈ P appearing in q is rewritten based on TW (lines 7-8), using the Algorithm 1, and the equivalent rewritings of every qt are stored in a set P R(qt). In order to build rewritings for the whole query (lines 9-11), we take one rewriting from every set P R(qt), check whether all views included in TW are used in this combination, add all value equality predicates appearing in the views of W, as well as any other projection, value selection or value join needed, and examine whether the emerging expression is an equivalent rewriting of q. The expressions that constitute a rewriting of q, are added to the set R, which is the output of the algorithm.

1 W ← ∪ v∈V expand(v) 2 R ← ∅ 3 foreach W ⊆ W, |W| ≤ |q| do 4 TW ← ∪ v∈W (∪ tp∈v v.tp) 5 P R ← ∅ 6 foreach qt ∈ {q.t 1 , q.t 2 , . . . , q.t m } do 7 P R(qt) = Subset-enum(qt,TW) 8 foreach combination rc = (r 1 , r 2 , . . . , r m ), such 9 that r 1 ∈ P R(q.t 1 ), r 2 ∈ P R(q.t 2 ), . . . ,
We should notice that in line 8 of Pattern-rewriting, we use Subset-enum to discover the equivalent rewritings of a tree pattern over a set of tree pattern views. Nevertheless, in [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF], we have described three more algorithms for this purpose: Increasing-Subset-Enumeration, Dynamic Programming Rewriting, Depth-First Rewriting. Thus, Subset-enum could be substituted by any of the other three algorithms.

VI. RELATED WORKS

Our approach relates to many works on XML indexing in DHT networks [START_REF] Abiteboul | XML processing in DHT networks[END_REF], [START_REF] Galanis | Locating data sources in large distributed systems[END_REF], [START_REF] Rao | An internet-scale service for publishing and locating XML documents (demo)[END_REF], over which it improves by allowing to declare and exploit complex materialized views to speed-up the processing of specific application queries. In [START_REF] Manolescu | Materialized views for P2P XML warehousing[END_REF], we have provided algorithms which handle efficiently tree pattern views in large networks (1000 peers). This work is the first to jointly consider documents and annotations, and as a consequence, we added value joins to the views and to the queries. Numerous recent works have targeted efficient RDF querying in a centralized setting [START_REF] Weiss | Hexastore: sextuple indexing for semantic web data management[END_REF] and based on DHTs [START_REF] Liarou | Evaluating conjunctive triple pattern queries over large structured overlay networks[END_REF]. The specificity of our work is to first, combine documents and annotations and second, focus on view maintenance and viewbased rewriting.

Within the WebContent project [START_REF]The WebContent Semantic Web platform[END_REF], we have devised a DHT-based platform integrating two types of DHT content indices [START_REF] Abiteboul | Webcontent: efficient P2P warehousing of web data (demo)[END_REF]. However, this still did not provide sufficient leeway to establish efficient data access support structures. Moreover, the biggest performance problems we encountered while using the system [START_REF] Abiteboul | Webcontent: efficient P2P warehousing of web data (demo)[END_REF] were due to the frequent joins generated by document-and-annotations queries.

  v k into tq do e ← Views-to-rewriting(TW, φ 1 , φ 2 , . . . φ k )

	4
	5	if e is an equivalent rewriting then
	6	add e to P R
	7	remove from P R non-minimal rewritings
	8	return P R