Gabriela Montoya
email: gabriela.montoya@univ-nantes.fr

Luis-Daniel Ibáñez

Hala Skaf-Molli

Pascal Molli
email: pascal.molli@univ-nantes.fr

Maria-Esther Vidal
email: mvidal@ldc.usb.ve

GUN: An Efficient Execution Strategy for Querying the Web of Data

Keywords:

Local-As-View (LAV) mediators provide a uniform interface to a federation of heterogeneous data sources to attempt the execution of queries against the federation. LAV mediators rely on query rewriters to translate mediator queries into equivalent queries on the federated data sources. The query rewriting problem in LAV mediators has shown to be NP-complete, and there may be an exponential number of rewritings, making unfeasible the execution or even generation of all the rewritings for some queries. The complexity of this problem can be particularly impacted when queries and data sources are described using SPARQL conjunctive queries, for which millions of rewritings could be generated. We aim at providing an efficient solution to the problem of executing LAV SPARQL query rewritings while the gathered answer is as complete as possible. We formulate the Result-Maximal k-Execution problem (Re-MakE) as the problem of maximizing the query results obtained from the execution of only k rewritings. Additionally, a novel query execution strategy called GUN is proposed to solve the ReMakE problem. Our experimental evaluation demonstrates that GUN outperforms traditional techniques in terms of answer completeness and execution time.

Introduction

Querying the Web of Data raises the issue of semantic heterogeneity between a large number of data sources. Local-as-view (LAV) mediation [START_REF] Levy | Answering queries using views[END_REF] is a wellknown and flexible approach to perform data integration over heterogeneous data sources. A LAV mediator relies on views to define semantic mappings between a uniform interface defined at the mediator level, and local schemas or views that describe the integrated data sources. A LAV mediator relies on a query rewriter to translate a mediator query into the union of queries against the local views. Additionally, new data sources can be included into LAV mediators without affecting the definition of the existing ones; thus, LAV mediators are well suitable to integrate sources from the Web of Data [START_REF] Abiteboul | Web data management[END_REF]. Nevertheless, the query rewriting problem has shown to be NP-complete, and the number of rewritings can be exponential even if mediated queries and local views are conjunctive queries [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF][START_REF] Arvelo | Compilation of query-rewriting problems into tractable fragments of propositional logic[END_REF]. For example, a LAV mediator with 140 conjunctive views can generate 10,000 rewritings for a conjunctive query with 8 goals [START_REF] Konstantinidis | Scalable query rewriting: a graph-based approach[END_REF]. This query rewriting problem complexity can be exacerbated by the usage of mediator queries and local views defined as SPARQL conjunctive queries. SPARQL queries are commonly comprised of a large number of triple patterns and many of them are defined on general predicates that can be answered by the majority of the data sources, i.e., rdf:type or rdfs:seeAlso. Additionally, these triple patterns can be grouped into chained connected star-shaped sub-queries [START_REF] Vidal | Efficiently Joining Group Patterns in SPARQL Queries[END_REF]. Finally, a large number of variables can be projected out. Thus, the conjunction of all these properties impacts on the complexity of the query rewriting problem and conduces to the explosion of the number of query rewritings. For example, a query with 12 triple patterns that comprised three chained star-shaped sub-queries can be rewritten using 300 views in billions of rewritings, if general predicates are used in the triple patterns. This problem is even more challenging considering that statistics cannot be always collected from the sources, and there are not clear criteria to rank or prune the generated rewritings [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF]. Therefore, it is not realistic to generate or execute such a huge number of rewritings, and we aim at providing an efficient solution to the problem by considering only k LAV SPARQL query rewritings, where k corresponds to the first k rewritings produced by a LAV rewriter. We devised the Result-Maximal k-Execution Problem (ReMakE) as an extension of the Query-Rewriting-Problem (QRP) as follows: given a subset R k of size k of a solution R of a QRP for a query Q, the ReMakE problem is to evaluate a set of rewritings R ′ containing R k and contained in Q such that R ′ is result-maximal. Furthermore, we propose the Graph-Union execution strategy (GUN) as a solution to the ReMakE problem. Unlike traditional techniques, GUN relies on wrappers that populate an RDF graph that is locally managed by the execution engine. This approach takes advantage of the relatively low cost of the RDF-Graph union operation to construct an aggregation of the data retrieved from the views. This approach attempts at executing the original mediator query directly on the graph union and consequently, it may find results hidden to the k first rewritings. For a given set of rewritings, GUN always gathers at least all the answers collected by a traditional engine by executing the rewritings independently. If all relevant views identified by the rewriter are in R k , GUN guarantees to return the complete answer without further processing of rewritings. Thus, the execution time of GUN depends on the number of the relevant views that comprise the rewritings in R k , which is usually considerably lower than the total number of rewritings.

We compare GUN against traditional strategies in an experiment on synthetic data generated by the Berlin SPARQL benchmark tool [START_REF] Bizer | The berlin sparql benchmark[END_REF] and views proposed by Castillo-Espinola [START_REF] Castillo-Espinola | Indexing RDF data using materialized SPARQL queries[END_REF]. We measure execution time and answer completeness for a benchmark of queries. In the experiments, we can observe that GUN retrieves much more results in less time than existing engines. The amount of main memory required to maintain a GUN graph is in general higher than the one required to execute traditional approaches; however, improvements in execution time and results are substantial enough to consider it a good trade-off.

The paper is organized as follows: Section 2 states preliminaries, while Section 3 formalizes the ReMakE problem. Section 4 presents the GUN query execution strategy as a solution for the ReMakE problem. Section 5 reports our experimental study. Section 6 summarizes related work; and finally, conclusions and future work are outlined in Section 7.

Preliminaries

We assume that a federation of data sources is integrated using the mediatorwrapper architecture proposed by Wiederhold [START_REF] Wiederhold | Mediators in the architecture of future information systems[END_REF]. Mediators provide a uniform interface to autonomous and heterogeneous data sources; they also implement the tasks of rewriting an input query into queries against the data sources, and merging data collected from the selected sources. Wrappers are software components that solve interoperability between sources and mediators by translating data collected from the sources into the schema and format understood by the mediators. Particularly, GUN-based mediators rely on wrappers able to solve resource identification and perform the corresponding RDF transformations to conform source data into the mediator RDF schema.

Formally, a conjunctive query Q over a database or mediator schema D has the form Q( X) :-P 1 ( X1 ), . . . , P n ( Xn ) where Q, P 1 , . . ., P n are predicates name of some finite arity, and X, X1 , . . ., Xn are tuples of variables. These predicates constitute the global schema. We define the body of the query as body(Q) = {P 1 ( X1 ), . . . , P n ( Xn )}. Any non-empty subset of body(Q) is called a subgoal of Q, singleton subgoals are called atomic subgoals. Predicates in the body stand for relations of D, while the head Q represents the answer relation of the query over D. We consider queries that are safe, i.e., X ⊆ n i=1 Xi , and call Q(D) the result of executing Q over D.

In the spirit of [START_REF] Konstantinidis | Scalable query rewriting: a graph-based approach[END_REF], we define a view v as a safe query over D, we establish the difference between the extension of v, denoted ext(v), and its evaluation over D, v(D), and assume the relation ext(v) ⊆ v(D) to state two important hypothesis: there may be data belonging to the database that is not available to the extensions, and the extensions never hold data that is not in the database.

A rewriting of a query Q over a database D with a set of views V is a conjunctive query r(x) :v 1 ( x1 ), . . . , v m ( xm ) where, v i ∈ V . A query rewriting is contained in Q, if for all database D and set of views V over D, the result of executing r in V is contained in the result of executing Q on D, i.e., r(V ) ⊆ Q(D).

Maximally Contained Query Rewriting Problem (QRP). Given a conjunctive query Q and a set of views V = { v 1 , . . . , v n } over a database D, QRP is to find a set of rewritings R, called the solution of the QRP, such that:

-For all extensions of the views in the bodies of all rewritings in R, the union of the results of executing each query rewriting in the views V is contained in the result of executing Q in D, i.e., r∈R r(ext(v 1 ), . . . , ext(v n )) ⊆ Q(D) -R is maximal, i.e., there is no other set R ′ , such that:

r∈R r(ext(v 1 ), . . . , ext(v n )) ⊂ r ′ ∈R ′ r ′ (ext(v 1 ), . . . , ext(v n )) ⊆ Q(D)
For a set R of rewritings, we define the set of relevant views Λ(R) = {v | v ∈ body(r) ∧ r ∈ R} as the set of views in the rewritings in R, and its execution R(D) = r∈R r(D). We also call ext(Λ(R)), the extension of the elements in Λ(R).

The main drawback of existing query rewriting problem solutions for LAV [START_REF] Levy | Answering queries using views[END_REF][START_REF] Konstantinidis | Scalable query rewriting: a graph-based approach[END_REF][START_REF] Arvelo | Compilation of query-rewriting problems into tractable fragments of propositional logic[END_REF][START_REF] Halevy | Answering queries using views: A survey[END_REF] is that the size of the set R can be exponential in the number of query subgoals [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF][START_REF] Halevy | Answering queries using views: A survey[END_REF]. Therefore, more than executing or generating an enormous number of rewritings, it is more realist to solve the problem of gathering data considering only k rewritings while obtaining an answer as complete as possible.

3 Result-Maximal k-Execution Problem (ReMakE)

In this section, we formalize the problem of obtaining the maximal set of results from a given subset of the rewritings of a query over a set of views.

Result-Maximal k-Execution Problem (ReMakE). Given a subset R k of size k of a solution R of a QRP of a query Q and a set of views V over a database D, ReMakE is to find a set of rewritings R ′ over the set of views in the bodies of the rewritings of R k , such that:

r k ∈R k r k (ext(Λ(R k ))) ⊆ r ′ ∈R ′ r ′ (ext(Λ(R k ))) ⊆ Q(D)
and that is result-maximal, i.e., that there is no another set R ′′ such that:

r ′ ∈R ′ r ′ (ext(Λ(R k ))) ⊂ r ′′ ∈R ′′ r ′′ (ext(Λ(R k ))) ⊆ Q(D)
We define this problem over the extensions of the views, as they are the real datasets where the query will be evaluated. It is important to note that the ReMakE problem only uses the query rewritings as an input and they could be obtained using any query rewriter, therefore, it is independent of the approach used to solve QRP. We also highlight that ReMakE is independent of the format of the data inside the extensions of the views, the wrappers would transform any format to the mediator schema.

To illustrate the problem, consider the generic set of rewritings in Figure 1, and suppose we can only execute the first five query rewritings. It could exist a rewriting comprised of some combination of views that were gathered for evaluating these five rewritings but that is not in the first five rewritings. ReMakE aims to consider all the rewritings that could be obtained from the already materialized views, hence in Figure 1 answers for rewriting r n would be also obtained.

r1 (x) :-v1 ( w) , v2 (ȳ) , v3 (z) r2 (x) :-v1 ( w) , v4 (ā) , v3 (z) r3 (x) :-v1 ( w) , v5 b , v6 (c) r4 (x) :-v1 ( w) , v7 d , v8 (ē) r5 (x) :-v1 ( w) , v8 (ē) , v7 f k = 5 . . . . . . . . . . . . rn (x) :-v1 ( w) , v4 (ā) , v6 (c)
Fig. 1: Illustration of the Result-Maximal k-Execution problem. Some combinations of views materialized during the execution of a subset of rewritings (R k ) could correspond to valid rewritings that does not belong to R k .

Definition 1. The Sets I (IRI Identifiers), B (Blank Nodes), L (Literals) and Υ (Variables) are four infinite and pairwise disjoint sets. We also define

T = I ∪ B ∪ L. An RDF-Triple is 3-tuple (s, p, o) ∈ (I ∪ B) × I × T . An RDF-Graph is a set of RDF-Triples. Definition 2. A mapping µ from Υ to T is a partial function µ : Υ → T . The domain of µ, dom(µ)
, is the subset of Υ where µ is defined.

Definition 3. A triple pattern is a tuple t ∈ (I ∪ Υ ∪ L) × (I ∪ Υ ) × (I ∪ Υ ∪ L).
A Basic Graph Pattern is a finite set of triple patterns. Given a triple pattern t, var(t) is the set of variables occurring in t, analogously, given a basic graph pattern B, var(B) = ∪ t∈B var(t). Given two basic graph patterns B 1 and B 2 , the expression B 1 AN D B 2 is a graph pattern.

Definition 4. Given a triple pattern t and a mapping µ such that, var(t) ⊆ dom(µ), µ(t) is the triple obtained by replacing the variables in t according to µ. Given a basic graph pattern B and a mapping µ such that var(B) ⊆ dom(µ), then µ(B) = ∪ t∈B µ(t).

Definition 5. Two mappings µ 1 , µ 2 are compatible (we denote µ 1 µ 2 ) iff for all ?X ∈ (dom(µ 1 ) ∩ dom(µ 2 )), then µ 1 (?X) = µ 2 (?X). This is equivalent to say that µ 1 ∪ µ 2 is also a mapping.

Definition 6.

Let Ω 1 , Ω 2 two sets of mappings. The join between Ω 1 and Ω 2 is defined as:

Ω 1 ⋊ ⋉ Ω 2 = {µ 1 ∪ µ 2 | µ 1 ∈ Ω 1 ∧ µ 2 ∈ Ω 2 ∧ µ 1 µ 2 } Definition 7.
Given an RDF-Graph G, the evaluation of a triple pattern t over G corresponds to:

[[t]] G = {µ | dom(µ) = var(t) ∧ µ(t) ∈ G}.
The evaluation of a basic graph pattern B over G is defined as:

[[B]] G =⋊ ⋉ t∈B [[t]] G . The evaluation of a Graph Pattern B ′ of the form (B 1 AND B 2 ) over G is as follows: [[B ′ ]] G = [[B 1 ]] G ⋊ ⋉ [[B 2 ]] G
We consider that our database is an RDF-Graph G. A conjunctive query over a general database is analogous to the following query over an RDF-Graph:

Q(x) = SELECT x WHERE F (p 1 (x 1 )) AND . . . AND F (p n (x n ))
where F is a translation function from predicates to triple patterns as defined in [START_REF] Baget | Translations between rdf(s) and conceptual graphs[END_REF] or a customized one. The definitions of variables, head and body are the same. As the definitions of views and rewritings are based on the definition of query, they remain equivalent, together with the definitions of QRP and ReMakE. We define the evaluation of a rewriting [[r(x)]] G as:

[[r(x)]] G = [[v 1 (x 1 ), . . . , v m (x m )]] G = ([[p a (x a )]] ext(v1) ⋊ ⋉ • • • ⋊ ⋉ [[p z (x z )]] ext(v1) ) ⋊ ⋉ • • • ⋊ ⋉ ([[p α (x α )]] ext(vm) ⋊ ⋉ • • • ⋊ ⋉ [[p β (x β )]] ext(vm) )
where p a . . . p z ∈ body(v 1 ) and p α . . . p β ∈ body(v m ). Note that this definition captures the practical implementation of the execution engine, where we materialize each call to a view (or more precisely, to its extension) and then, perform the joins between the sub-results. Traditionally, plans like Left Linear, Right Linear or Bushy Trees [START_REF] Chaudhuri | An overview of query optimization in relational systems[END_REF] are used to evaluate the rewritings over the extension of the views present in each rewriting; but to solve the ReMakE problem, we should ensure that any relevant combinations of obtained views are not missed, even if these combinations are not part of the rewritings in R k . Fig. 2: Left Linear execution of the rewriting r of query Q. Views origin, opinions, market and offers are loaded, but it is not possible to produce any results since the join for Offer is empty. Prefixes are omitted to improve legibility. Consider a query Q over a dataset generated with the Berlin Benchmark [START_REF] Bizer | The berlin sparql benchmark[END_REF], which offers information about products, their offers and users' reviews. Q is defined as: "Products of type t that are sold by vendors from Germany, and their rating evaluation".

Empty

Q(Product, Vendor, Rating) :-type(Product, t), product(Offer, Product), vendor(Offer, Vendor), country(Vendor, de), reviewfor(Review, Product), rating1(Review, Rating).

Considering the following four views: i) origin: "Products' type, producer, and features", ii) market: "Products' offers, price and vendors", iii) offers: "Offers' vendor, countries and validity", iv) opinions: "Products' reviews, ratings and reviewers". A possible rewriting of Q is: r(Product,Vendor,Rating) :-origin(Product,t, 0, 1), opinions(Review,Product, 5,Rating), market(Offer,Product, 2, 3), offers(Offer,Vendor,de, 4).

Figure 2 shows the execution of the rewriting of the query Q following a left linear execution plan. In this execution, the RDF Graphs retrieved from the sources through the views are used to execute this rewriting. Notice that while executing the plan some intermediate results are produced, like those corresponding to the evaluation of the join between origin and opinions; however, these intermediate results are dismissed without being used to produce answers. A pertinent solution of the ReMakE problem must take advantage of these retrieved data. We now define our solution to the ReMakE problem as follows:

Graph Union (GUN). Given R k a subset of a set of rewritings R of a query Q over a set of views V , apply Q to the union of the extensions of the views in the bodies of the elements of R k :

GU N (R k ) = [[Q]] ext(Λ(R k ))

Results

(P roduct, V endor, Rating) (prod1,ven1,rat1) Figure 3 shows the execution with GUN associated with the rewriting of query Q. For each view in the rewriting, we retrieve all its answers and store them into an aggregate RDF-Graph. As we are using the Local-As-View approach, views are expressed in terms of the global schema, and we can run the original query and execute joins that are not considered in the rewritings, like the one between market and offers through Vendor. Therefore, GUN takes advantage of all retrieved data to produce an answer for the user. GUN is affordable in the context of the Semantic Web thanks to the simplicity of the RDF data model. Implementing the same idea in relational databases would require to create the universal relation, which may have a prohibitive cost.

Proposition 1. Graph Union is a solution to the ReMakE problem, i.e.,

r∈R k [[r]] ext(Λ(R k )) ⊆ [[Q]] ext(Λ(R k )) (1)
[[Q]] ext(Λ(R k )) ⊆ [[Q]] G ( 2
)
And it is result-maximal.

Proof. As by construction of the views and their extensions v∈V

[[v]] G ⊆ G, then ext(Λ(R k ))
⊆ G, making straightforward to see that (2) holds. For (1) note that the set Λ(R k ) can be considered as a set of views over the graph Λ(R k ), then by the containment property, each member of R k is contained in Q. As we are applying the original query Q, it is clear that there is no rewriting that can return more results than Q, meaning that GUN is maximal.

GUN's Properties

In this section, we state some properties of GUN. Given a query Q and a set of views V on a database D, let V R the set of relevant views, R the set of rewritings of Q over V , and R k a subset of R.

-Answer Completeness:

If GUN is performed over R k with Λ(R k ) = Λ(R),
then GUN will produce the complete query answer i.e.,

Λ(R k ) = Λ(R) ⇒ GU N (R k ) = Q(D)
. By definition of QRP, only the relevant views contribute to the answer, therefore, if GUN's aggregation graph contains all the relevant views, then we can ensure that GUN will produce the complete answer. -Effectiveness: We define the Effectiveness of GUN for a given R k as:

GUNEffect(R k ) = |GUN (R k )| -| r k ∈R k r k (ext(Λ(R k )))| |Q(D)| -| r k ∈R k r k (ext(Λ(R k )))|
intuitively, GUN has more effectiveness if it finds answers that are not found by the execution of

r k ∈R k r k (ext(Λ(R k ))).
If |Q(D)| -| r k ∈R k r k (ext(Λ(R k )))| = 0,
then, the effectiveness is defined to be 0. Note that effectiveness and answer completeness are related by the following relation:

r k ∈R k r k (ext(Λ(R k ))) ⊂ Q(D) ⇒ (GUNEffect(R k ) = 1 ≡ GUN (R k ) = Q(D))
When the execution of R k does not produce the complete answer, then, GUN's effectiveness for R k equals to one iff GUN produces complete answers.

-Execution Time Independency of k: the execution time of GUN does not depend on the number of rewritings executed (k). It depends on the number of relevant views present in R k . Execution time is the elapsed time between the generation of R k rewritings and their execution time. This includes the time required to obtain the data from the wrappers, the time required to add the obtained data to the graph and the time required to execute the query plan on the graph. -Non-blocking: GUN solves the ReMakE problem under the assumption that Λ(R k ) fits in main memory. If not, GUN can only approximate it, for example, by splitting R k into disjoint R k1 and R k2 such that Λ(R k1 ) and Λ(R k2 ) fit in memory. Then, execute GUN (R k1 ), clear the memory, and execute GUN (R k2 ). Therefore, GUN is a non-blocking execution strategy i.e., running out of memory will not prevent GUN to execute at the expense of non-maximality of the answer, as the combined effectiveness of GUN (R k1 ) and GUN (R k2 ) is in general less than this of GUN (R k ).

Experimental Evaluation

To setup the experimental evaluation, we used the Berlin SPARQL Benchmark tool (BSBM) [START_REF] Bizer | The berlin sparql benchmark[END_REF] to generate a dataset of 5,000,251 triples, using a scale factor of 14,091 products. We used the 18 queries and the 10 views proposed in [START_REF] Castillo-Espinola | Indexing RDF data using materialized SPARQL queries[END_REF]. These queries are very challenging for a query rewriter since their triple patterns can be grouped into chained connected star-shaped sub-queries, that have between 1 and 13 subgoals, with only distinguished variables.

We defined 5 additional views to cover all the predicates in the queries. From these 15 views, we produced 300 views by horizontally partitioning each original view into 20 parts, such that each part produces 1/20 of the answers given by the original view. Queries and views information is shown in Tables 1a and1b. The size of the complete answer was computed by loading all the views into a persistent RDF-Store (Jena-TDB) and executing the queries over it. The number of rewritings was obtained using the models counting feature of the SSDSAT [START_REF] Izquierdo | An expressive and efficient solution to the service selection problem[END_REF] rewriter.

As we can see in Table 1a, the number of rewritings may be very large, making unfeasible their full execution. Furthermore, the time to generate the rewritings is not negligible, and in some cases (Q2, Q3 and Q7) SSDSAT could not generate them after 72 hours. We chose to compute 500 rewritings, as this was the best compromise we could find between number of rewritings and generation time, i.e., 500 is the larger number of rewritings (multiple of 50) that could be produced for all queries (but Q2, Q3 and Q7) in less than 15 hours. Additionally, we do not have any statistics about the sources to select the best rewritings or to shrink the set of relevant views. Q1 execution reached a timeout of 48 hours. Some general predicates like rdfs:label are present in the most of the views; therefore, the queries that have a triple pattern with these predicates will have a large number of relevant views, but not all of these views will contribute to the answer. The size of a view corresponds to the number of triples that can be accessed through that view. Detailed information about the definition of the queries and views can be found in the project website 3 .

We implemented wrappers as simple file readers. For executing rewritings, we used one named graph per subgoal as done in [START_REF] Le | Rewriting queries on sparql views[END_REF]. The Jena 2.7.44 library with main memory setup was used to store and query the graphs. We used the Left Linear Plans implemented by Jena as a representative of traditional query execution techniques.

Experimental Results

The analysis of our results focus on four aspects: answer completeness, effectiveness, execution time and non-blocking as defined in section 4.1.

To study the answer completeness of GUN, we executed the GUN and Jena strategies over R k rewritings, we counted the number of rewritings to have the complete answer. Table 2 shows that GUN is able to achieve the complete answer for 12 queries whereas Jena is able to do so only for 6 queries. For queries Q9, Q11, Q13 and Q17, GUN produced complete answers because at the reported k, Λ(R k ) = Λ(R). For the rest of the queries, the non aggregated relevant views did not contribute to produce more results. Detailed information about the ratio of relevant views for each R k can be found in the project's website.

To demonstrate the effectiveness of GUN, we executed the GUN and Jena strategies over R k with k ∈ {80, 160, 320, 500}, counted the number of answers and computed the effectiveness. Table 2 shows that GUN has effectiveness 1 for k = 80 for half of the queries, moreover, in 5 of these 7 queries, the maximum effectiveness remains even after Jena executes 500 rewritings. In 4 cases, GUN is not effective because Jena already found the complete answer for this value of k. Finally, in Q6 and Q14, GUN found more results than Jena. Effectiveness values are not monotonic, since they can increase when considering a rewriting that contains a view that contributes to produce results in GUN and not in Jena. However, they can decrease after executing a rewriting that does not add new views to GUN, but produces results for Jena.

Regarding the execution time, we want to: 1) demonstrate that GUN execution time does not depend on k, but on |Λ(R k )|, and 2) compare GUN's execution time with Jena's. Table 3a shows total execution time, the detailed values of the execution time are available in the project website. For all queries GUN has better execution time, and for all but Q6 with k = 80, is more than twice faster. When k = 500, the difference is dramatic, varying from almost 4 times faster (Q13) to 680 times faster (Q4). Table 3b shows total execution time and number of loaded views for GUN. Execution time grows linearly in |Λ(R k )|, this is particularly visible in Q4 and Q13.

If we compare the times detailed in section 4.1, we notice that the dominating time is the wrapper time. GUN loads views into the aggregated graph only once, whereas Jena reloads them for each executed rewriting. Note that if we try to cache the views in Jena to avoid reloading, it would consume more memory and could consume even more memory than GUN if the views have overlapped information, as it is the case in our setup.

Finally, we analyzed GUN's and Jena's memory consumption to demonstrate that in spite of complex queries and many relevant views: 1) GUN is not blocking, and 2) to compare memory used by GUN with respect to Jena. For GUN, we count the number of triples of the aggregated graph. For Jena, we report an upper bound, that is, the maximum number of triples loaded for executing a rewriting in R k . Table 4 summarizes the results. Neither GUN nor Jena consumes all the available memory (8GB). GUN needs to load more triples than Jena, varying from less than twice to 12 times more, in all cases except for Q10 with k ≥ 320. GUN's aggregation is in general larger than the sum of the named graphs of the most memory-consuming rewriting in R k . In summary, GUN is effective with better execution time at the cost of higher memory consumption. However, in our experimentation GUN never exhausts the available memory in spite of the challenging setup. This makes it a very appealing solution for the ReMakE problem.

Related Work

In recent years, several approaches have been proposed for querying the Web of Data [START_REF] Acosta | Anapsid: An adaptive query processing engine for sparql endpoints[END_REF][START_REF] Basca | Avalanche: Putting the Spirit of the Web back into Semantic Web Querying[END_REF][START_REF] Harth | Data summaries for on-demand queries over linked data[END_REF][START_REF] Hartig | Zero-knowledge query planning for an iterator implementation of link traversal based query execution[END_REF][START_REF] Ladwig | Sihjoin: Querying remote and local linked data[END_REF]. Some tools address the problem of choosing the sources that can be used to execute a query [START_REF] Hartig | Zero-knowledge query planning for an iterator implementation of link traversal based query execution[END_REF][START_REF] Ladwig | Sihjoin: Querying remote and local linked data[END_REF]; others have developed techniques to adapt query processing to source availability [START_REF] Acosta | Anapsid: An adaptive query processing engine for sparql endpoints[END_REF][START_REF] Hartig | Zero-knowledge query planning for an iterator implementation of link traversal based query execution[END_REF]. Finally, frameworks to retrieve and manage Linked Data have been defined [START_REF] Basca | Avalanche: Putting the Spirit of the Web back into Semantic Web Querying[END_REF][START_REF] Hartig | Zero-knowledge query planning for an iterator implementation of link traversal based query execution[END_REF], as well as strategies for decomposing SPARQL queries against federations of endpoints [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF]. All these approaches assume that queries are expressed in terms of RDF vocabularies used to describe the data in the RDF sources; their main challenge is to effectively select the sources, and efficiently execute the queries on the data retrieved from the selected sources. In contrast, our approach attempts to semantically integrate data sources, and relies on a global vocabulary to describe data sources and provide a unified interface to the users. Thus, in addition to efficiently gather Table 4: Maximum number of triples loaded by a rewriting in R k in Jena. The number of triples of the aggregated graph of GUN. and process the data transferred from the selected sources, it decides which of the rewritings of the original query need to execute to efficiently and effectively produce the query answer.

Two main paradigms have been proposed to define the data sources in integration systems. The LAV approach is commonly used because it permits the scalability of the system as new data sources become available [START_REF] Ullman | Information integration using logical views[END_REF]. Under LAV, the appearance of a new source only causes the addition of a new mapping describing the source in terms of the concepts in the RDF global vocabulary. Under GAV, on the other hand, entities in the RDF global vocabulary are semantically described using views in terms of the data sources. Thus, the extension or modification of the global vocabulary is an easy task in GAV as it only involves the addition or local modification of few descriptions [START_REF] Ullman | Information integration using logical views[END_REF]. Therefore, the LAV approach is best suited for applications with a stable RDF global vocabulary but with changing data sources whereas the GAV approach is best suited for applications with stable data sources and a changing vocabulary. Given the nature of the Semantic Web, we rely on the LAV approach to describe the data sources in terms of a global and unified RDF vocabulary, and assume that the global vocabulary of concepts is stable while data sources may constantly pop up or disappear from the Web.

The problem of rewriting a global query into queries on the data sources is one relevant problem in integration systems [START_REF] Levy | Querying heterogeneous information sources using source descriptions[END_REF], and several approaches have been defined to efficiently enumerate the query rewritings and to scale when a large number of views exists (e.g., MCDSAT [START_REF] Arvelo | Compilation of query-rewriting problems into tractable fragments of propositional logic[END_REF], GQR [START_REF] Konstantinidis | Scalable query rewriting: a graph-based approach[END_REF], Bucket Algorithm [START_REF] Levy | Querying heterogeneous information sources using source descriptions[END_REF], MiniCon [START_REF] Halevy | Answering queries using views: A survey[END_REF]). Recently, Le et al, [START_REF] Le | Rewriting queries on sparql views[END_REF] propose a solution to identify and combine GAV SPARQL views that rewrite SPARQL queries against a global vocabulary, and Izquierdo et al [START_REF] Izquierdo | An expressive and efficient solution to the service selection problem[END_REF] extends the MCDSAT with preferences to identify the combination of semantic services that rewrite a user request. A great effort has been made to provide solutions able to produce query writings in the least time possible, however, to the best of our knowledge, the problem of executing the query rewritings against the selected sources still remains open.

We address this problem and propose GUN, a query processing technique for RDF store architectures that provide a uniform interface to data sources that have been defined using the LAV paradigm [START_REF] Levy | Answering queries using views[END_REF]. GUN assumes that the query rewriting problem has been solved using an off-the-shell query rewriter (e.g., [START_REF] Izquierdo | An expressive and efficient solution to the service selection problem[END_REF][START_REF] Konstantinidis | Scalable query rewriting: a graph-based approach[END_REF]), which may produce a large number of query rewritings. GUN implements a query processing strategy able to execute a reduced number of query rewritings of and generate a more complete answer than the rest of the engines in less time, as it was observed in our experimental results.

Because GUN is able to answer mediator queries even in presence of a very large space of query rewritings, it constitutes a relevant contribution to the implementation of integration systems, and provides the basis for feasible semantic integration architectures in the Web of Data.

Conclusion and Future Work

Performing complex queries on different data sources raises the severe issue of semantic heterogeneity. Local-as-View mediators is one of the main approaches to solve it. However, the high number of rewritings needed to be executed represents a severe bottleneck. We proposed the ReMakE problem, that consists in maximizing the number of results obtained by considering only k rewritings (R k ). We also proposed GUN, a solution to this problem, it uses the RDF data model and takes advantage of the low cost of graph union operation.

Compared to state-of-the-art approaches, GUN provides an alternative way to improve performance at the execution engine level rather than at the rewriter level. This makes GUN usable with any LAV rewriter guaranteeing to achieve greater or equal answer completeness for the same R k . Our experiments demonstrate that GUN gain is real, i.e., its effectiveness is equal to one for 57% of the queries for the values of k until 80. It remains equal to one for 38% of the queries for the values of k until 500.

Furthermore, GUN consumes considerably less execution time than Jena in all the cases; the difference in execution time is tremendous, up to 681 times. However, this improvement in effectiveness and execution time is at the cost of an additional memory consumption of up to 12 times. This work opens new perspectives to improve LAV approach for the Semantic Web. First, we would like to measure the effectiveness degradation when executing on low-memory setups, and include some heuristics to minimize it. As GUN creates materialized views for processing rewritings, we plan to evaluate the impact on the effectiveness and the execution time when performing inference tasks on the graph union. Finally, because GUN is mostly dependent on the ratio of views in rewritings divided by the number of relevant views, an interesting perspective is to modify rewriters to optimize the number of views in the first k rewritings.

Fig. 3 :

 3 Fig. 3: GUN execution of the rewriting r of query Q. Results are produced, at the cost of building and querying over an aggregated graph. Prefixes are omitted to improve legibility.

Table 1 :

 1 We say that GUN is effective for a given R k if GUNEffect(R k ) > 0 Queries and their answer size, number of rewritings, number of relevant views (RV) and views size.

	Query Answer Size # rewritings # of RV
	Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17	3.33E+07 2.99E+05 2.03E+05 1.42E+02 2.82E+05 9.84E+04 1.12E+05 2.82E+05 1.41E+04 1.49E+06 1.49E+06 2.99E+05 2.99E+05 2.82E+05 1.41E+05 1.41E+05 9.84E+04	1.61E+09 6.37E+21 3.52E+24 6.02E+03 1.30E+07 1.22E+05 1.15E+12 4.08E+04 2.00E+01 9.76E+05 3.24E+03 2.37E+08 2.41E+04 8.08E+05 4.64E+09 8.36E+04 2.02E+03	260 260 280 240 240 100 180 100 20 260 80 260 260 180 280 100 100	Views V1-V20 147,327 Size V21-V40 133,992 V41-V60 41,463 V61-V80 22,410 V81-V100 4,515 V101-V120 53,131 V121-V140 32,511 V141-V160 90,873 V161-V180 21,138 V181-V200 9,836 V201-V220 4,515 V221-V240 4,515 V241-V260 67,364 V261-V280 81,313 V281-V300 840,470
	Q18	2.82E+05	3.12E+08	240	(b) Views size
		(a) Query information

Table 2 :

 2 Values of k for obtaining the Complete Answers (CA) for queries Q4-Q6, Q8-Q18; using GUN and Jena. GUN's Effectiveness for different values of k. Effectiveness for Q9 is not reported here since it only has 20 rewritings.

Table 3 :

 3 Execution Time (ET) for GUN and Jena. Impact of Number of Relevant Views (RV) over Execution Time in GUN.

GUN: a solution to the ReMakE problemIn this section, we explain how to solve the ReMakE problem by taking advantage of the relatively low cost of the RDF-Graph union. We use definitions of SPARQL semantics of[START_REF] Pérez | Semantics and complexity of sparql[END_REF]:

https://sites.google.com/site/graphunion/

http://jena.apache.org/

Acknowledgments. The final publication is available at http://link.springer.com/chapter/10.1007%2F978-3-642-40285-2_17.


Maher Assaad
email: maher.assaad@aurak.ae

Israel Yohannes

Amine Bermak
email: eebermak@ee.ust.hk

Dominique Ginhac
email: dominique.ginhac@u-bourgogne.fr

Fabrice Meriaudeau
email: fabrice.meriaudeau@u-bourgogne.fr

DESIGN AND CHARACTERIZATION OF AUTOMATED COLOR SENSOR SYSTEM

Keywords: Color sensor, light sensor, analog to digital converter (ADC), flash ADC

The paper presents a color sensor system that can process light reflected from a surface and produce a digital output representing the color of the surface. The end-user interface circuit requires only a 3-bit pseudo flash analog-to-digital converter (ADC) in place of the conventional/typical design comprising ADC, digital signal processor and memory. For scalability and compactness, the ADC was designed such that only two comparators were required regardless of the number of color/wavelength to be identified. The complete system design has been implemented in hardware (bread board) and fully characterized. The ADC achieved less than 0.1 LSB for both INL and DNL. The experimental results also demonstrate

that the color sensor system is working as intended at 20 kHz while maintaining greater than 2.5 ENOB by the ADC. This work proved the design concept and the system will be realized with integrated circuit technology in future to improve its operating frequency.

INTRODUCTION

Color sensor systems are increasingly being used in automated applications to detect automation errors and monitor quality at the speed of production line. They are used in assembly lines to identify and classify products by color. The objectives of their usage include to check the quality of products [START_REF] Zhang | Colorimetric sensor array for soft drink analysis[END_REF][START_REF] Oram | Color measurement of a solid active pharmaceutical ingredient as an aid to identifying key process parameters[END_REF][START_REF] Frank | High-speed industrial color and position sensors[END_REF], to facilitate sorting and packaging [START_REF] Pacquit | Development of a smart packaging for the monitoring of fish spoilage[END_REF][START_REF] Cadieux | System and method for visually inspecting a cigarette packaging process[END_REF][START_REF] Lee | High-speed automated color-sorting vision system[END_REF], to assess the equality of products in storage [START_REF] Popov-Raljić | Investigations of bread production with postponed staling applying instrumental measurements of bread crumb color[END_REF][START_REF] Popov-Raljić | Sensory properties and color measurements of dietary chocolates with different compositions during storage for up to 360 days[END_REF], and to monitor waste products [START_REF] Bogue | Optical chemical sensors for industrial applications[END_REF]. Consequently, there is abundant of color sensors and the choice is often application-driven [START_REF] Escid | 0.35 mm CMOS optical sensor for an integrated transimpedance circuit[END_REF][START_REF] Ogawa | optical probe current sensor module using the Kerr effect of exchange-coupled magnetic film and its application to IGBT switching current measurements[END_REF]. Low cost and simple color sensors are preferred over sophisticated solutions for less demanding applications where the top priority is cost and power consumption. This paper presents such a sensor that is based on an embedded analog-to-digital converter (ADC) as the end-user interface circuit. The proposed system is capable of differentiating up to eight different colors and thus, it is specifically targeted for automated applications where few colored products need to be detected.

The principle of detection embedded in our color sensor system is based on reflectance property of a colored surface, as illustrated in Figure 1. When a white light is shined on a surface, the surface will reflect a specific spectrum while absorbing all the other spectra. For example, a white light focused onto a red surface is reflected as red. The reflected red light impinges on the light transducer producing a corresponding output voltage that is typical of the reflected red color. By interpreting this output voltage using an interface circuit, the color can be determined. The success of a color sensor by reflection depends on the detector, the illuminant (light source) and the target object. Black and white objects reflect respectively 0 and 100% of the incident light falling on them while other colors reflect selected parts in the visible spectra.

Rough, glossy or dirty surfaces make the detection rather complicated since their reflectance property is different, and the source of light affects the color saturation of the object being detected [START_REF] Baribeau | Color reflectance modeling using a polychromatic laser range sensor[END_REF]. For our system, the most appropriate source is a nearly pure white light (i.e.

D65 daylight).

The detector of the color sensor system also plays a crucial role for efficient color recognition.

A photodiode is used in the proposed color sensor system as the principal detector element.

Photodiodes generate electron and hole carriers upon exposure from visible light inducing photocurrent. The maximum photo-current can be given by (1.1) [START_REF] Zeghbroeck | p-n Junctions[END_REF][START_REF] Deen | Silicon Photodetectors[END_REF]:

a*d in ph P I= ( 1 -R ) * ( 1 -e) * q * h* v (1.1)
where R is the surface reflectivity of the photodiode; d is depth from the silicon surface; α is the absorption coefficient which is dependent on the material property (e.g. silicon or GaAs); q is electron charge; P in is the power of incident light; h is Planck's constant ; and v is the frequency of incident light. The following sections present the system design, the operating principle and the characterization of our color sensor system.

II. COLOR SENSOR SYSTEM DESIGN

The proposed color sensor system incorporates a detector and a dedicated interface circuit.

The interface circuit offers a lower cost and power consumption solution, compared with the conventional design. As depicted in Figure 2(a), conventional color sensor systems comprise (i) a light transducer, (ii) a pre-amplifying block to amplify the sensor signal and/or convert the signal from current to voltage domain, (iii) an ADC, (iv) a digital signal processor (DSP)

for color recognition which may include a memory, digital comparator arrays, arithmetic units and so on to produce the final color output. In our design, we minimize the component count by storing the color table (mapping between color and photodiode output voltage) with variable resistors acting as analog memory, and generate digital color code using an

b. Interface Circuit

The interface circuit is based on a pseudo flash ADC (shown in Fig 3(b)) that has been customized to meet the requirements of the targeted application. Indeed, the selection of a specific ADC architecture is always driven by design requirements. For high-speed, lowresolution applications, the flash architecture is a promising approach [START_REF] Torfs | Low-power 4-bit flash analogue to digital converter for ranging applications[END_REF]; for applications such as sensor networks that do not require high speed and can tolerate data latency but have ultra-low power requirements, successive approximation (SAR) ADCs are usually used [START_REF] Lee | A 21 fJ/conversion-step 100 kS/s 10-bit ADC with a low-noise timedomain comparator for low-power sensor interface[END_REF][START_REF] Scott | An ultra-low power ADC for distributed sensor networks[END_REF]. Often designers combine features of one or more architectures to achieve the desired performance. The ADC designed in this work offers a balance between power consumption and speed by combining features of a flash and a digital ramp ADC. The interface circuit needs two comparators only, regardless of the number of colors, N color , to be identified. This minimizes the power as well as the on-chip area, especially when N color is large.

The proposed design uses a set of tunable resistors, which form part of the ADC to store the color table. This is easily achieved as the photodiode displays a monotonous response V phd to different wavelength/color. If the full scale of the ADC is 2 V, we could thus map different voltage intervals for different colors as shown in Table 1. These intervals can be easily The timer block serves the function of adjusting the duty cycle of the LED blinking. In the case of fast color change, the timer holds the output for longer time so that the output is visually distinguished by a user. Otherwise for constant outputs, the timer limits the duty cycle so the LEDs does not draw current continuously there by lowering the power dissipation. The design also incorporates a sampler after the photodetector to ensure dynamic (time varying) color detection with minimum error.

III. OPERATING PRINCIPLE OF THE INTERFACE CIRCUIT

The operating principle of the proposed design is depicted in the conceptual diagram At this point, the counter state is registered and outputs the corresponding digital code. This code is kept in the display until a new color is detected. The multiplexers are controlled by an up-down counter, which in turn is controlled by the comparison result (D/U). Compared with using one-sided regular counter, the proposed search scheme provides a faster conversion speed with a small hardware overhead.

1 1 1 A M U X 1 A M U X 2 Vref Vphd V 1 V 0 V 2 V 3 V 4 D DFF x x x D DFF D DFF S 0 S 1 S 2 b 0 b 1 b 2 = xxx Up-down Counter S 0 S 1 S 2 T CLK D/U 1 1 1 A M U X 1 A M U X 2 Vref Vphd V 1 V 0 V 2 V 3
As mentioned, the key advantage of the proposed system is the minimization of components count in the interface circuit which is the number of comparators being fixed to two, regardless of the number of detectable colors, as opposed to the 2^N-1 comparators in a conventional flash ADC, albeit with some trade-off in conversion speed. For the present 3-bit implementation, the average sampling speed of the interface circuit τs, without the timer effect, is estimated to be 4 clock cycles; in the worst case condition where the AMUXs have to switch through all reference levels to reach the desired interval, τ s is 8 clock cycles; in the best case where the desired interval is found on its first search, τ s is one clock cycle. The average sampling rate can then be estimated as half the maximum rate. One clock cycle (τ clk ) can be measured based on the propagation delay of the constituent ICs, in this case 1/τ clk = 2.8

MHz. This gives 1/τ s , a sampling rate of 700 kHz for the interface circuit,

τ clk ≥ δ pd = δ COUNTER + δ MUX + δ COMP + δ AND + δ DFF (1.2)
τ clk ≤ τ S ≤ 8*τ clk (1.3) (τ S ) avg. = 0.5*(τ clk ) MAX = 4τ clk (1.4)
where, δ pd is the total propagation delay and δ counter , δ MUX , δ AND , δ DFF are the propagation delay of counter, AMUX, comparator, AND gate and D flip flop (DFF) respectively. As mentioned previously, the stored voltages using the variable resistors represent color voltages, which are calibrated to the sensor system before measurement begins.

IV. EXPERIMENT RESULTS

The proposed color sensor system has been implemented using discrete components for a quick proof of design concept. Validation was carried out by characterizing the embedded ADC then the complete color sensor system. Experimental setup for a quick proof of concept implementation on a project board is shown in Figure 5. The principal element of the interface circuit, the pseudo Flash ADC, was realized for a fullscale voltage of 2 V. The typical static and dynamic performance of the ADC is plotted in Figure 6. The plots show that the static characteristic of the ADC is good, achieving 0.1 LSB for both INL and DNL. In addition, regarding the dynamic characteristics, it achieved more than 2.5 ENOB at 20 kHz input frequency (input color change) on a project board. V.

DISCUSSION

In our previous work [START_REF] Assaad | Two-Stage Interface Circuit Design for a 32-Color Resolution Optical Sensor[END_REF][START_REF] Assaad | Design and characterization of multi-color sensor circuit[END_REF], we have proposed color sensor based on similar color detection mechanism. This work includes significant improvements over the previous such as (i) it uses two-sided counter (up/down) instead on one sided which contributed to improved efficiency and speed of conversion (ii) it enables dynamic (online) detection by incorporating a sampler after the light transducer unit (iii) it implements output control by regulating duty cycle using timer, which attributes to saving power. ADC characterization result of the interface circuit is also included. The core design concept about the proposed color sensor system is low component-count and scalability. While the design has been implemented for 3-bit ( 8different colors), it can easily be extended to detect more than eight different colors. Apart from being low component count and low power consumption, the advantage of the proposed system is its ability to generate a digital output/code representing directly the detected color.

This ensures a straightforward computation and eliminates the need of further data processing. This is desirable for easy and fast integration with subsequent units in the production line. The proposed system can be applied for assembly lines where products need to be sorted by color or colored mark. Experimental results show that the system is working as intended. For a successful detection, careful manual calibration of the voltage intervals is required before use.

Future work includes integrating a dedicated CMOS photodiodes that suitable for color sensing as in [START_REF] Fang | Colorimetric porous photonic bandgap sensors with integrated CMOS color detectors[END_REF][START_REF] Longoni | The transverse field detector (TFD): A novel color-sensitive CMOS device[END_REF][START_REF] Catrysse | An integrated color pixel in 0.18µm CMOS technology[END_REF] along with the proposed interface circuit on a single chip and introducing auto calibration mechanism.

VI. CONCLUSION

A new, automated color sensor system based on an embedded 3-bit pseudo flash ADC has been realized and successful experimental results of the sensor system and the interface circuit is presented. Admittedly, the operating frequency (successful color detection rate) of the complete system is rather low, i.e. goes to 20 kHz for > 2.5 effective number of bits, which is mainly attributed to its current implementation as discrete components; however it can be significantly improved by using integrated circuit technology (i.e. much lower gate propagation delay). The proposed color sensor system design is low-cost, has low component count and simple yet scalable for higher resolution. We envisage it to be applied in automated color detection applications such as color sorting and matching applications.

Figure 1 .

 1 photodiode

Figure 2 .

 2 Figure 2. Block diagram of (a) conventional color detection scheme (b) color detection using the proposed color sensor system.

  adjusted based on calibration result from the photodiode. The proposed design uses eight indicator blinking LEDs as a simple yet clear means to indicate the final output for user through a 3-to-8 decoder where each LED represents one color/voltage interval.

Figure 3 .

 3 Photodiode (Vphd) to S/H

Figure 4 .

 4 The two analog multiplexers switch through the reference voltages creating a closed interval dynamic voltage reference. The comparators compare the photodiode response Vphd with the moving reference (signals AMUX1 and AMUX2) until the correct interval is found (V3 and V4 in Fig4(b)). Then the comparators will fire simultaneously as can be seen in Figure4(b).

Figure 4 .

 4 Figure 4. Conceptual diagram illustrating operation of the embedded ADC. (a) The AMUX's switch through the ladder voltage until both comparators fire, during this time the output is not updated from previous detection. (b) Both comparators fire indicating conversion process is completed.

Figure 5 .

 5 Figure 5. Experimental setup to test the proposed color sensor

Figure 6 .

 6 Figure 6. Embedded ADC characteristics in proposed interface circuit. (a) Differential and integral nonlinearity errors. (b) Effective number of bits against input frequency (in kHz). The interface circuit is running at 1/τ s = 700 kHz.

  B5 = 1, color yellow detected. (d) B7 = 1, color red detected.

Figure 7 .

 7 Figure 7. Experimental result from the proposed sensor system. The output bits and their corresponding color is shown. (Only four bits are shown at a time from a 4channel oscilloscope).

Table 1 :

 1 Reference voltage intervals and their corresponding color values

	Color	Designation	Voltage intervals
	Violet	B0	0.00 -0.25
	Indigo	B1	0.25 -0.50
	Blue	B2	0.50 -0.75
	Green	B3	0.75 -1.00
	Yellow-Green	B4	1.00 -1.25
	Yellow	B5	1.25 -1.50
	Orange	B6	1.50 -1.75
	Red	B7	1.75 -2.00