Query processing is an important way of accessing data on the Semantic Web. Today, the Semantic Web is characterized as a web of interlinked datasets, and thus querying the web can be seen as dataset integration on the web. Also, this dataset integration must be transparent from the data consumer as if she is querying the whole web. To decide which datasets should be selected and integrated for a query, one requires a metadata of the web of data. In this paper, to enable this transparency, we introduce a federated query engine called WoDQA (Web of Data Query Analyzer) which discovers datasets relevant with a query in an automated manner using VOID documents as metadata. WoDQA focuses on powerful dataset elimination by analyzing query structure with respect to the metadata of datasets. Dataset and linkset descriptions in VOID documents are analyzed for a SPARQL query and a federated query is constructed. By means of linkset concept of VOID, links between datasets are incorporated into selection of federated data sources. Current version of WoDQA is available as a SPARQL endpoint.
While the web is evolving through a structured data space,
many applications are publishing and linking their data, and
the cloud of this linked and open data will be gigantic as
times go. In this interlinked and structured data space,
query execution becomes one of the most important research
problems and di erent query execution approaches and tools
have been proposed in the literature [
In this paper, we present a federated query engine called WoDQA (Web of Data Query Analyzer) which is developed to execute a query on distributed datasets without missing answers using VOID metadata of datasets in linked open data cloud. WoDQA focuses on e ective dataset selection for a query and analyzes query structure to eliminate irrelevant datasets. Relevant datasets are selected by analyzing VOID documents and considering which dataset includes a resource related with the query and which links between datasets allow to nd a result to the query. VOID metadata provides dataset descriptions representing content of a dataset and linkset descriptions representing relationships between datasets which are used by WoDQA for e ective dataset selection.
There are two main approaches which enable automated
query processing on the web of data and prevent data
consumers from searching for relevant datasets. The rst
approach called follow-your-nose (link traversal) [
Follow-your-nose approach conceptualizes the web as a
graph of documents which contains dereferenceable URIs.
This approach is based on executing queries on relevant
documents which are retrieved by following links between
resources in di erent documents. But, this method raises
completeness and performance issues. Although some
heuristic query planning methods can be used to answer di erent
kinds of queries [
In the light of these ideas, WoDQA executes queries by analyzing VOID documents which constitute a projection of the web of data and incorporates follow-your-nose approach into query federation by considering links between datasets in metadata. WoDQA does not change the evaluation order of a query because the main focus of this initial version of WoDQA is only eliminating much more irrelevant datasets in dataset selection without query optimization. Current RDF federation implementations select relevant datasets by considering only predicate and type indexes. Since vocabularies in the Semantic Web should be common, there can be a lot of datasets which use a speci c property or class. Therefore, using such indexes causes selection of redundant datasets. The main contribution of WoDQA is incorporating both links between data through linkset concept and relationships between triple patterns of a query into dataset selection to eliminate irrelevant datasets e ectively. We serve WoDQA as a SPARQL endpoint and a simple web form2 to execute raw queries by analyzing datasets in the VOID stores.
Remaining sections are organized as follows. In Section 2, related work is discussed. Section 3 introduces general architecture of WoDQA and details dataset selection approach. In Section 4, usage of WoDQA is shown with a working example. Finally, Section 5 concludes the paper.
The Semantic Web querying approaches can be classi ed
as centralized and distributed. Centralized querying is based
on collecting linked data into a single central data store, and
querying the data from this store. This approach includes
data warehousing which collects pre-selected data sources
and search engines which crawl the Web by following RDF
links and index discovered data [
On the other hand, distributed querying depends on
processing query parts directly on original data and managing
results retrieved from distributed data. Query federation
[
Although aforementioned query federation implementations aim to query linked datasets, they do not consider links between data for dataset selection. For this reason, there are some shortcomings of these implementations from querying web of data perspective. The rst one is that deciding datasets via only predicate indexes causes inability to select datasets e ectively for triple patterns which have unbounded predicates or have so general predicates such as owl:sameAs and foaf:page that are extensively used in datasets6. The second shortcoming is that so many datasets may be selected for triple patterns, and executing ASK queries in such a case increases the cost notably. One need to take the structure of the query into account to eliminate right irrelevant datasets in the web of data context.
The second distributed querying approach is
follow-yournose [
WoDQA aims to query the web of interlinked datasets using VOID dataset and linkset descriptions to decide relevant datasets for a query. At rst, it assumes that all datasets are relevant with a query, then irrelevant datasets are eliminated by analyzing query structure in the light of metadata of datasets. Its novelty is considering query structure and links between datasets to select relevant datasets before query execution, and thus it incorporates follow-yournose approach into the query federation. To the best of our knowledge, WoDQA is the rst query engine which uses datasets and linksets together that are critical elements of VOID to describe dataset metadata.
In this section, query processing architecture of WoDQA is explained in detail. Since it is impractical to perform a query on all published datasets on the web, WoDQA aims to transform a query into a federated query which is evaluated only on relevant datasets. In this direction, to process a query on the linked data cloud, WoDQA contains three main modules as seen in Figure 3.1: DatasetAnalyzer, QueryReorganizer and Jena ARQ 7.
Dataset publishers construct the VOID documents of their datasets and the Semantic Web programmers can access these documents through services called VOID store such as voiD Browser8, CKAN9 and voiDStore10. A VOID store generates a projection of Linked Open Data, and thus this structure obliges dataset publishers to create well-de ned VOID document which re ects actual content of the dataset to enable including the dataset in relevant queries. DatasetAnalyzer is the module which is responsible for discovering relevant datasets and eliminating irrelevant ones using VOID documents of datasets in the VOID stores. We assume that dataset publishers update the description documents in the VOID stores to make VOID stores up-todate for dataset selection when datasets are changed. In the current version of WoDQA, DatasetAnalyzer discovers the VOID documents from the CKAN net, and analyzes dataset and linkset descriptions for each triple pattern in the query. This analysis eliminates irrelevant datasets which de nitely do not contain any result contributing to the result of the query by assuming that accurate and complete VOID documents of datasets are available. Dataset analysis is achieved by a rule-based approach. We explain the rules which discovers relevant datasets Subsection 3.1.
The second module is QueryReorganizer which rewrites queries depending on results of DatasetAnalyzer. This rewriting process constructs federated SPARQL queries including 7http://jena.sourceforge.net/ARQ/ 8http://kwijibo.talis.com/voiD/ 9http://ckan.net/ 10http://void.rkbexplorer.com/ SERVICE expressions11. Details of QueryReorganizer are given in Subsection 3.2.
The last module is query executor which directly uses Jena ARQ to execute SPARQL queries including the SERVICE expressions inserted by the QueryReorganizer. The federated query constructed by QueryReorganizer is passed to ARQ to be executed. Results of query execution are returned to the querior. In the following subsections, the rst two modules which implement WoDQA analysis and reorganization phases are explained. 3.1
This section introduces the details of the DatasetAnalyzer module which is the core and the innovative part of the current version of WoDQA. Unlike other query federation approaches, WoDQA considers triple pattern relations and links between datasets while selecting datasets. Thanks to dataset analysis of WoDQA, relevant datasets are specied while plenty of irrelevant ones are excluded. Output of dataset analysis is a subset of all published datasets on the web of data, and thus the query is performed only on this subset including related ones. For the purpose of explaining how this subset is constructed, we give a formalization in this section.
We rstly give a de nition of the web of data to formalize
our dataset selection approach. In summary, the web of data
is an RDF graph which is constructed by typed links between
data from di erent sources. Basically an RDF graph (G) is
formally represented as a set of triples in the form of hs; p; oi:
G = fhs; p; oi j hs; p; oi2 (I [ B) I (I [ B [ L)g where I
is the set of IRIs[
From another perspective, the web of data means web
of interlinked datasets [
De nition 1. A dataset is a sub-graph of web of data, x Gwod, and the resources which are included by x are speci ed as follows: 8r; i (r 2 subj ( x) ! Owner ( x; r)).
VOID describes a dataset with well-de ned properties12, and we formalize a VOID dataset description as a tuple hLspace; Ivoci 2 L I. The rst dataset property Lspace corresponding to void:uriSpace set which contains string literals that all entity IRIs in a dataset start with. The other one is Ivoc corresponding to void:vocabulary which denotes the set of vocabularies used by the dataset13.
The triples whose object is a resource in another dataset make the web of data a graph of interlinked datasets. We call such triples link triples, and de ne the set of link triples as LT = f(s; p; o) jowner (s) 6= owner (o)g where s; o 2 I. This de nition leads us to de ne link predicate (plink) concept which corresponds to void:linkPredicate used to de ne a linkset which is an important contribution of VOID effort. Set of link predicates Plink includes all the predicates which are used in a link triple: Plink = fplinkj9 s; plink; o 2 LT g. A linkset represents link triples which connect resources in di erent datasets using the same link predicate. We formalize the linkset, , as a tuple D from; to; plinkE 2
Plink where is the set of all datasets on the web. In this de nition, from is the referrer dataset which is the owner of subject of link triples in the linkset, to is the referenced dataset which is the owner of object of link triples in the linkset, and plink is the link predicate of all link triples in the linkset.
DatasetAnalyzer uses both dataset and linkset descriptions of VOID metadata to select the relevant datasets, in other words sub-graphs, which may contain the results of the query. By this means, the query is transformed into a federated query and executed on the relevant datasets on the web. Accordingly, we exclude the datasets which do not contain any result for the query while querying the global graph, Gwod. Beside analyzing relationships between VOID descriptions (datasets, linksets) and triple pattern, relationships between triple patterns in a query are considered. For this reason, we need to give a formal de nition of SPARQL queries.
We consider a subset of SPARQL queries which
corresponds to a basic graph pattern for formalization [
To perform a query on the web of data, in the worst case, each triple pattern has to be queried on all published 12DatasetAnalyzer of the current version of WoDQA considers only these properties for the sake of simplicity. We plan to integrate other properties such as statistics in the future to make optimized queries. 13Note that schemas of the Semantic Web languages such as RDFS and OWL are not speci ed in Ivoc. 14We exclude blank nodes in query. datasets. Since this is impractical, our purpose is eliminating irrelevant datasets for each triple pattern. By elimination of irrelevant datasets, we construct a federated query which distributes sub-queries to only relevant ones. In order to eliminate irrelevant datasets, we introduce a set of rules which discover the relevant datasets in dataset analysis, called relevant dataset discovery rules. A relevant dataset for a triple pattern is formalized as an assertion ( x; tpi) which denotes that the dataset x may contain a result for the triple pattern tpi. We need to discuss how relevant dataset assertions ( ) inferred by discovery rules used for eliminating irrelevant datasets. To explain the method of eliminating irrelevant datasets, assume that Qtpi is the set of datasets selected to be queried for tpi which we call selected set, and this set initially contains all datasets on the web, Qitnpiit (all datasets in a VOID store in our case). Each rule analyzes datasets in Qtpi of each triple pattern. After applying a rule, elements of Qtpi which the rule does not infer relevant dataset assertion about are removed from Qtpi . But, if the rule does not imply any relevant dataset assertion, Qtpi remains the same. Irrelevant dataset elimination method is formalized as Qtnpeiw below to denote such an update of selected set subsequent to executing a rule. Qtnpeiw = 9 a ( ( a; tpi)) ; 90 a ( ( a; tpi)) ; f xj ( x 2 Qtpi ) ^ (tpi; x)g
Qtpi
In the following subsection we give relevant dataset discovery rules in detail and we use some queries to exemplify application of rules. Figure 3.2 shows VOID models of a set of datasets which are used in these examples. This model contains simpli ed VOID descriptions of ve datasets and the linksets connecting these datasets by link predicates. Link predicates are showed by arrows between dataset descriptions which are represented with squares. Also we create a sample dataset called Facebook which keeps the data about Facebook users in our local store. This data is about that movie resources located in LinkedMDB dataset are liked by which users. Although there can be a lot of linksets, in Figure 3.2, only a few linksets are taken into account to explain our rules are depicted. 3.1.1
This subsection presents a set of rules each of which represents an analysis method of the DatasetAnalyzer module to discover relevant datasets e ectively. Each relevant dataset discovery rule aims to analyze datasets from di erent perspectives and combinations of them to infer relevant dataset ( ) assertions for triple patterns. These perspectives can be classi ed into three groups. The rst one is analyzing IRIs in the triple patterns. We call this perspective IRIbased Analysis where namespaces of IRIs and vocabularies in the VOID documents are considered to determine relevant datasets. The second one is considering linked resources. We call this perspective Linking Analysis which considers whether a triple links two resources in the same dataset (internal) or in di erent datasets (external) to eliminate irrelevant datasets. The last perspective is Shared Variable Analysis. Since triple patterns share some variables, each triple pattern a ects relevant datasets of other triple patterns that include same variables. Relevant dataset discovery rules of all perspectives are introduced in this section.
The rst two rules are under the IRI-based analysis perspective each of which considers vocabularies Ivoc of VOID metadata. The rst discovery rule checks whether IRIs in triple patterns are RDFS (or OWL) classes or properties in the vocabulary set (Ivoc) of VOID documents. To give the rule, we de ne has Ivxoc; r function which represents that a resource r 2 I (a property or a class IRI) is included by one of the vocabularies in Ivxoc. Using has expression, relevance of a dataset x to an IRI r is represented with V ocM atch as shown in De nition 2.
De nition 2. 8 x(has(Ivxoc; r) ! V ocM atch( x; r)) where r 2 I
For a triple pattern such as ?s dbpprop:name15 \Nikola Tesla", dbpprop:name RDFS property in the predicate position obliges that matching triple patterns can only be in datasets which uses dbpprop vocabulary. Therefore, we can eliminate datasets which do not use dbpprop vocabulary. This situation is handled by Rule 1 which is similar to predicate indexes.
Rule 1. If there is a dataset in which one of its vocabularies includes the predicate of a triple pattern, then it is relevant for the triple pattern. 8tpi; x (V ocM atch ( x; ptpi ) ! ( x; tpi))
According to Figure 3.2, DBpedia uses dbpprop vocabulary, and the rule decides that it is relevant for such a triple pattern. In web of data, lots of datasets which uses dbpprop vocabulary can be found, and they can be eliminated using outputs of other discovery rules.
To introduce Rule 2, consider another triple pattern, ?producer rdf:type linkedMDB:producer, which contains a type de nition for the variable ?producer. In such cases, the object of the triple pattern is a class de nition, it makes sense to eliminate the datasets which do not use the vocabulary of this class. Rule 2 resembling type indexes is used to specify relevant datasets for such triple patterns. The example triple pattern is queried from the datasets that use linkedMDB vocabulary, i.e. LinkedMDB dataset for our example model. Other datasets do not include a resource which is an instance of linkedMDB:producer class, and therefore they are eliminated by output of this rule.
Rule 2. If there is a dataset in which one of its vocabularies includes the object of a triple pattern when the predicate of the triple pattern is rdf:type, then the dataset is relevant for the triple pattern. 8tpi; x(V ocM atch( x; otpi ) ^ (ptpi = rdf:type) ! ( x; tpi)) 15All pre xes used in the paper are de ned in Table 1.
Another perspective to discover relevant datasets is Linking Analysis. Since a triple links two resources in the same dataset or in di erent datasets, this perspective is separated into two kinds of analyses, each of which considers di erent kind of triples. The rst one is Internal Linking Analysis which considers triples linking resources in the same dataset. A relevant dataset found by this analysis is called internal relevant dataset, and is represented with int ( x; tpi). On the other hand, External Linking Analysis considers link triples which connect resources in di erent datasets. In this case, linkset descriptions of VOID documents are taken into account to discover relevant datasets, and a dataset found by this analysis is called external relevant dataset which is represented as ext ( x; tpi). Internal and External Linking analyses are both executed for a triple pattern in whole Linking Analysis process, and then produced internal and external relevant datasets for a triple pattern are uni ed as relevant datasets for the triple pattern as shown in Rule 3.
Rule 3. Union of external and internal datasets for a triple pattern constitutes relevant datasets for the triple pattern. 8 x; tpi int ( x; tpi) _ ext ( x; tpi) ! ( x; tpi)
Irrelevant dataset elimination method considers relevant datasets which are speci ed by Rule 3 to eliminate irrelevant datasets from selected set of a triple pattern (Qtpi ). Internal and external datasets are intermediate results to infer relevant datasets in a Linking Analysis.
The rst two rules under Linking Analysis perspective are linking-to-IRI discovery rules. Consider the example triple pattern, ? lm owl:sameAs dbpedia:A Fistful of Dollars, which can be matched with a triple that links a resource to dbpedia:A Fistful of Dollars resource. Triple patterns whose object is an IRI are analyzed by these rules. Since owners of the linked IRI must be known in these rules, we give a de nition that depicts the owners of any resource on the basis of IRI Analysis. We formalize inclusion of a resource (r 2 I) by a dataset ( x) in De nition 3 by using the urispaces (Lspsapcaec)e property of the VOID description and startsW ith r; L x function which represents that r space. starts with one of the urispaces in L x
De nition 3. 8 x(startsW ith(r; Lsxpace) ! Owner( x; r)) Rule 4 is linking-to-IRI internal discovery rule from the internal linking point of view. According to the example query ? lm should be in the same dataset with dbpedia:A Fistful of Dollars, i.e. owner of the dbpedia:A Fistful of Dollars resource. Therefore appropriate triple patterns can be found in DBpedia dataset.
Rule 4. If there is a triple pattern whose object is an IRI, then owner datasets of the IRI are internal relevant for the triple pattern. 8tpi; x ( x 2 Qtpi ) ^ Owner ( x; otpi ) ! where otpi 2 I; stpi 2 V int ( x; tpi)
On the other hand, from the external linking point of view, appropriate triples can be found in datasets which are linked to the owner datasets of object IRI. For our example triple pattern, ? lm should be in datasets which contain link triples whose object resource is de ned in DBpedia. For this analysis, linkset descriptions of VOID documents are used. To discover relevant datasets for a triple pattern by using linking-to-IRI external discovery rule, the triple pattern should have a bound predicate. We de ne Compatible expression in De nition 4 to represent that which linkset description is appropriate to use for determining relevant datasets for a triple pattern.
De nition 4. If selected set of a triple pattern has the referrer dataset of a linkset description and link predicate of the linkset description is same with the triple pattern's predicate, then the linkset description is compatible with the triple pattern. 8 m; tpi(( fmrom 2 Qtpi ) ^ (plimnk = ptpi ) ! Compatible( m; tpi))
Considering ? lm owl:sameAs dbpedia:A Fistful of Dollars triple pattern, and remembering the linkset description of our example model in Figure 3.2, there are linksets from LinkedMDB and YAGO datasets to DBpedia dataset whose link predicates are owl:sameAs. Rule 5 which is under the Linking Analysis perspective gives these two datasets as external relevant datasets for this triple pattern. If a dataset is not linked to DBpedia by owl:sameAs predicate then one can conclude that this dataset is irrelevant with the triple pattern.
Rule 5. If there is a linkset description that is compatible with the triple pattern and whose referenced dataset is an owner dataset of the triple pattern's object, then the referrer dataset of the linkset description is external relevant for the triple pattern. 8tpi; m; x(Compatible( m; tpi) ^ Owner( x; otpi ) ^ ( x = tom ) ! ext( fmrom; tpi)) where otpi 2 I; stpi 2 V Recall that internal and external relevant datasets are unied by Rule 3 after applying rules in Rule 4 and Rule 5. Thus, the nal relevant datasets which are selected by the linking-to-IRI rules are DBpedia, LinkedMDB and YAGO.
Another couple of rules under the Linking Analysis perspective are IRI-links-to rules. These rules are applied to triple patterns whose subject is an IRI and object is a variable to determine relevant datasets from internal and external linking point of view. Rule 6 is IRI-links-to internal discovery rule and it nds the triples that link resources in the same dataset. One can conclude that if the subject of a triple pattern is an IRI, then triples matching with this triple pattern are in the owner dataset of this IRI.
Rule 6. If a dataset is an owner of the subject of a triple pattern, then this dataset is internal relevant dataset for the triple pattern. 8tpi; x ( x 2 Qtpi ) ^ Owner( x; stpi ) ! otpi 2 V; stpi 2 I int( x; tpi) where
Consider the triple pattern dbpedia:Ennio Morricone owl: sameAs ?person. Subject of this triple pattern is an IRI whose namespace is dbpedia, and therefore an internal relevant dataset is DBpedia whose VOID metadata contains dbpedia as value of urispace property.
Rule 7 is IRI-links-to external discovery rule and it nds the triples that connect resources in di erent datasets. According to this rule an owner dataset of the subject IRI of the triple pattern is external relevant only when there is a linkset de nition that includes owner dataset as referrer dataset compatible with the triple pattern.
Rule 7. If there is a linkset description that is compatible with the triple pattern and whose referrer dataset is an owner dataset of the triple pattern's subject, then the referrer dataset of the linkset description is external relevant for the triple pattern. 8tpi; m; x(Compatible( m; tpi) ^ Owner( x; stpi ) ^ ( x = fmrom) ! ext( x; tpi)) where otpi 2 V; stpi 2 I
According to the example, DBpedia is the owner dataset of dbpedia:Ennio Morricone and also there is a linkset description whose referrer dataset is DBpedia and whose link predicate is owl:sameAs.
Other discovery rules in Linking Analysis are combined with Shared Variable Analysis. The rst discovery rule which conforms to this combined analysis is Chaining Triple Patterns Analysis. This rule considers two triple patterns together to discover relevant datasets. This is a characteristic of Shared Variables Analysis, since it depends on analyzing more than one triple pattern that have same variable. Triple patterns below are example of chaining triple patterns: ?s owl:sameAs ? lm. ? lm linkedMDB:producer name \Sergio Leone"
Notice that the second triple pattern is used for querying lms whose producer name is \Sergio Leone". Thus, the second triple pattern a ects the relevant datasets of the rst triple pattern. From internal linking point of view, the rst triple pattern can be found in datasets which satisfy the second triple pattern because ?s and ? lm should be in the same dataset. In this direction, Internal Chaining Triple Pattern Analysis formalized in Rule 8 is used to discover internal relevant datasets for triple patterns.
Rule 8. If there is a triple pattern whose object is same with the subject of another triple pattern, then datasets included by selected sets of both triple patterns are internal relevant. 8 x; tpi; tpj ((otpi = stpj ) ^ ( x 2 Qtpi ) ^ ( x 2 Qtpj ) ! int( x; tpi) ^ int( x; tpj )) where otpi ; stpi 2 V
To execute Chaining Triple Pattern Analysis, execution order of rules becomes important. To exemplify this situation according to Chaining Triple Patterns query, assume that IRI-based analysis is applied before, and LinkedMDB is the relevant dataset for the second triple pattern since LinkedMDB VOID includes linkedMDB as the value of vocabulary. Then, this rule can specify that the internal relevant dataset for the rst triple pattern is LinkedMDB. It is clearly seen from this example, Shared Variable Analysis should be performed after the execution of IRI-based Analysis rules to eliminate more datasets. Hence, in the Subsection 3.1.2, we give an overview of analysis process which speci es an execution order for these rules.
After the IRI-based analysis, if we apply Rule 8 for the example triple patterns, relevant datasets of the second triple pattern is shown as Qtp2 = f LinkedMDB g, and of the rst one is shown as Qtp1 . For this case, this rule asserts that int( LinkedMDB ; tp1) and int ( LinkedMDB; tp2).
On the other hand, External Chaining Triple Patterns analysis uses linkset descriptions while considering two triple patterns. While internal one can be used for all triple patterns without considering the predicate, external rule is applied for a triple pattern which has a link predicate. Rule 9 introduces this rule.
Rule 9. If there is a triple pattern (tpi) whose object is same with the subject of another one (tpj ), and there is a linkset description which is compatible with (tpi) and its referenced dataset is included by the selected set of tpj , then referrer dataset is external relevant for tpi and referenced dataset is external relevant for tpj . 8 m; tpi; tpj ((otpi = stpj ) ^ Compatible( m; tpi) ^ ( tom 2 Qtpj ) ! ext( fmrom; tpi) ^ ext( tom ; tpj )) where otpi 2 V
With respect to the example of chaining triple patterns, assume that selected set for the rst triple pattern is Qtp1 , and for the second one is Qtp2 = f LinkedMDBg. Rule 9 determines that DBpedia is external relevant for tp1 since resources ? lm can be found in LinkedMDB and there is a linkset between these two datasets with owl:sameAs predicate. It is clear that no other dataset can contain an appropriate triple if it is not linked to LinkedMDB by owl:sameAs. At the end of Chaining Triple Pattern Analysis, internal and external relevant datasets speci ed by Rule 8 and 9 are unied according to Rule 3.
Another analysis which uses both Linking Analysis and Shared Variable Analysis is Object Sharing Triple Patterns Analysis. For triple patterns which have the same object variable, only the datasets can include triples which satisfy the object variable of both triple patterns. To simplify the explanation, we use the following example for Object Sharing Triple Pattern Analysis below: ?person facebook:likes ?movie. ? lm owl:sameAs ?movie.
From internal linking point of view, ?person and ? lm should be in the same dataset with ?movie. Rule 10 species the internal relevant datasets for triple patterns which have the same object. Assume that Qtp1 = f F acebookg due to value of vocabulary property of Facebook VOID and Qtp2 . This rule determines that only F acebook can contain internal triples that satisfy triple patterns together.
Rule 10. If there is a triple pattern whose object is same with the object of another one, then the datasets included by selected sets of both triple patterns are internal relevant. 8 x; tpi; tpj ((otpi = otpj ) ^ ( x 2 Qtpi ) ^ ( x 2 Qtpj ) ! int( x; tpi) ^ int( x; tpj )) where otpi 2 V
To execute Object Sharing Analysis from external point of view, we bene t from the linkset descriptions. To nd appropriate link triples, ?person and ? lm should be in di erent datasets. Rule 11 determines external relevant dataset for triple patterns which have the same object. This rule considers two linkset descriptions together for two triple patterns.
Rule 11. If two triple patterns have the same object, and there are two linkset descriptions which have the same referenced dataset each of which is compatible with one of the triple patterns, then referrer datasets of the linkset descriptions are external relevant for the triple patterns. patible( n; tpj )^( tom = ton ) ! tpj )) where otpi 2 V 8 m; n; tpi; tpj ((otpi = otpj )^Compatible( m; tpi)^Com ext( from; tpi)^ ext( from; m n
For the example of Object Sharing Triple Pattern Analysis, assume that no rule is applied before this analysis and selected sets are Qtp1 and Qtp2 . In Figure 5, DBpedia, Y AGO, and LinkedMDB have link triples with predicate owl:sameAs. But, only F acebook has a linkset to LinkedMDB with predicate facebook:likes, and therefore Qtnpe1w = f F acebookg. In this case, tp2 can only be queried on the datasets which is linked to LinkedMDB with predicate owl:sameAs, and thus Qtnpe2w = f DBpediag. Other triples whose subject corresponding to ? lm in other datasets according to tp2 cannot include objects that satisfy object of tp1. As done in other Linking Analysis methods, internal and external relevant datasets which are inferred by Rule 10 and Rule 11 are uni ed according to Rule 3.
The last analysis from the Shared Variable Analysis perspective considers the triple patterns which have the same subject called Subject Sharing Triple Patterns Analysis. This rule does not use Linking Analysis perspective, and thus it does not contain Internal and External Linking Analysis. Consider the following example triple patterns for Subject Sharing Triple Pattern Analysis: ?city dbpprop:name \Izmir" . ?city dc:terms ?subject.
According to our dataset de nition, triples which have the same subject are included by the same dataset. Based on this, Rule 12 infers datasets which are relevant for triple patterns by taking the intersection of selected sets into account.
Assume that selected sets for triple patterns are Qtp1 = f DBpediag and Qtp2 . According to the rule, the nal datasets according to this rule are Qtnpe1w Qtnpe2w = f DBpediag.
Rule 12. If there is a triple pattern whose subject is same with the subject of another triple pattern, then the datasets included by selected sets of both triple patterns are relevant. 8 x; tpi; tpj ((stpi = stpj )^( x 2 (Qtpi \Qtpj )) ! ( x; tpj )) where stpi 2 V ( x; tpi)^
Up to this point, we have given the relevant dataset discovery rules which are used to determine relevant datasets from di erent perspectives. These rules are executed together for a query to make a complete analysis. Next section introduces the analysis process which speci es the execution order for rules. 3.1.2
The rules introduced above should be executed together to provide e ective dataset selection. In this section, execution of rules are explained in the process of DatasetAnalyzer which is shown Figure 3.3. In the gure, QBGP = fQtpi jtpi 2 BGP g is the set of selected sets of all triple patinit terns in a query. We use QBGP to represent the initial state where selected set of each triple pattern contains the whole web of data, 8Qtpi 2 QiBnGitP (Qtpi ). This set is the input of the single step analysis, and selected sets in this set are constrained by execution of the rules includes the IRI-based analyses. Single step analysis includes vocabulary match, linking-to-IRI and IRI-links-to rules which are executed only once. The reason is that the rules based on IRI-based analysis produce the same result for every execution because they do not depend on current Qtpi . Although the rules in single step analysis do not have a speci c order, using output of each rule in dataset elimination method reduces current datasets set of the triple patterns. Then, QcBoGnPstrained is given to the repetitive analysis phase.
On the other hand, rules based on Shared Variable Analysis take more than one triple pattern into consideration. Since di erent combinations of triple patterns a ect the selected sets of each other, these rules depend on current selected sets of triple patterns to discover the datasets relevant to the triple patterns. For this reason, they are executed repetitively until no dataset is eliminated from any new Qtpi . The repetitive analysis phase produces QBGP by executing Shared Variable Analysis rules. After the phase is new completed once, if an elimination has been done, QBGP is constrained, and the phase is given to repetitive analysis as QBGP repeated. On the other hand, when the rules do not change any selected set, i.e. QnBeGwP QcBoGnPstrained, the analysis is nished and the result is produced as QfBiGnPal. 3.2
The QueryReorganizer module is responsible for rewriting a query using nal selected set of each triple pattern
QfBiGnPal decided by the DatasetAnalyzer. While rewriting a federated query, Query Reorganizer conforms to SPARQL 1.1 federation extension16.
While the initial query is a set of triple patterns, QueryReorganizer divides the query into sub-queries and makes it a set of service graph patterns each of which is represented with a tuple sgp = hSrv ; SubT p i. A service graph pattern consists of a Srv set which includes datasets17 to send the sub-query, and a SubT p set which is the subset of the triple patterns of the initial query, i.e. a sub-query. Performing a service graph pattern is unifying the results of the sub-query in each dataset in Srv .
Triple patterns which have the same selected set (Qtpi ) are added to the same service graph pattern to decrease networking cost. But, only consecutive triple patterns can be in the same sub-query because WoDQA does not change the evaluation order of the query. In this direction, elements of SubT p sets of service graph patterns are found by Algorithm 1.
Datasets of a sub-query is formalized as Srv = f xj x 2 Qtpi ; tpi 2 SubT p g, and service endpoint URLs are procured from VOID documents of the datasets. The output of the Query Reorganizer is shown as ReorganizedBGP = hsgp1; : : : ; sgpmi where 1 m n and n is the number of triple patterns of the initial query. ReorganizedBGP repre16http://www.w3.org/TR/sparql11-federated-query/ 17In the implementation, SPARQL endpoints of datasets are used in SERVICE expressions.
Algorithm 1 This algorithm divides query into sub-triples FUNCTION DivideT riples() INPUT bgp = ftp1; : : : ; tpng including n triple patterns; LET i := 1; := 1; LET SubT riples := ftpig; WHILE i < n DO
ELSE IF Qtpi+1 = Qtpi THEN
LET SubT riples := SubT riples [ ftpi+1g; LET SubT riples +1 := ftpi+1g;
LET := + 1;
LET i := i + 1; sents the federated form of the initial query which contains ordered service graph patterns. WoDQA executes the reorganized query using Jena ARQ query engine.
Besides grouping triple patterns, although WoDQA does
not include query optimization phase of query federation
approach, only moving up FILTER expression[
There are two ways for users to bene t from WoDQA. The rst one is the SPARQL endpoint of WoDQA18 which can be used to redirect raw queries. One can construct a SPARQL query with a SERVICE block including the raw query, and use WoDQA SPARQL endpoint as the remote service. When this query is executed, the WoDQA endpoint is invoked, and this endpoint transforms the query into a federated form by means WoDQA and executes this federated query on the relevant dataset transparently to the user.
The other way is using the web form of the WoDQA19. In this section, a sample query execution on the web form of WoDQA is explained. Reorganized form of the query, results of select and construct queries and execution time can be observed in this form.
The example query seen in the WoDQA web form in Figure 4.1 searches for an answer to \Which facebook users like movies which are produced by a German producer?". This query is represented as BGP = htp1; : : : ; tp5i where tp1 = h?faceUser,facebook:likes,?moviei, tp2 = h?movie,linkedMDB:producer,?produceri, tp3 = h?dbProducer,owl:sameAs,?produceri , tp4 = h?anyMovie, dbpo:producer, ?dbProduceri, tp5 = h?dbProducer, dbpo:birthPlace, dbpedia:Germanyi.
We explain how relevant datasets are found according to the WoDQA Analysis process introduced in Figure 3.3. Initially, single step analysis phase is performed for this query. Selected sets of tp1 and tp2 are eliminated via output of predicate vocabulary match, and in the consequence of single step analysis they are Qtp1 = f F acebookg and Qtp2 = f LinkedMDBg. No relevant dataset is found for tp3 in the single step analysis, because owl:sameAs is a generic 18Up-to-date WoDQA SPARQL endpoint address can be found on http://seagent.ege.edu.tr/etmen/wodqa.html page. 19http://seagent.ege.edu.tr/etmen/wodqa.html property and owl is not de ned as vocabulary property in VOIDs. Thus, Qtp3 still includes all datasets ( ). Predicate vocabulary match discovers relevant datasets for tp4 and tp5, and their selected sets are Qtp4 = Qtp5 = f DBpediag.
After the single step analysis is applied to all triple patterns, the repetitive analysis phase is performed, and selected set of tp3 is eliminated in this phase. Subject Sharing Triple Patterns Analysis discovers relevant datasets for tp3 since tp3 and tp5 have the same subject variable, and thus its selected set becomes Qtp3 = f DBpediag.
The reorganized query shown in Figure 4.1 is rendered with these analysis results by QueryReorganizer and formalized as ReorganizedBGP = hsgp1; sgp2; sgp3i where sgp1 = hf F acebookg ; ftp1gi, sgp2 = hf LinkedMDBg ; ftp2gi, sgp3 = hf DBpediag ; ftp3; tp4; tp5gi.
After the reorganizing process, the triple patterns in the service graph patterns are executed on related endpoints by means of Jena ARQ, and query results are incrementally collected. In conclusion, results related with the query are listed at the bottom of the web form page as seen in Figure 4.1.
In this paper, we have introduced a query federation engine called WoDQA that discovers related datasets in a VOID store for a query and distributes the query over these datasets. The novelty of our approach is exhaustive dataset selection mechanism which includes analysis of triple pattern relations and links between datasets besides analyzing datasets for each triple pattern. WoDQA focuses on discovering relevant datasets and eliminating irrelevant ones using a rule-based approach introduced in this paper. Our approach requires VOID descriptions which include a SPARQL endpoint to query the dataset, re ect actual content of the dataset completely and accurately, and include linksets between datasets to select datasets e ectively. WoDQA allows users to construct raw queries without the need to know how query will divide into sub-queries and where sub-queries are executed. Query results are complete under the assumption of available, accurate and complete VOID descriptions of datasets.
The initial version of WoDQA which is introduced in this paper has some disadvantages arising from query federation approach which WoDQA builds upon. As mentioned previously, follow-your-nose has some problems such as missing results and large document retrieval. Similar problems may occur for query federation. Firstly, to nd complete results to queries, it is required that metadata of all datasets must be well-de ned and accurate. But, to provide such an accurate dataset metadata an automated mechanism which continuously updates the metadata is required. However, even there would be a tool which implements this requirement, providing accurate dataset metadata via such a tool is the responsibility of dataset publishers.
Another problems of query federation are high latency and low selectivity of datasets which are similar to retrieval of large documents in follow-your-nose. Query optimization can be a solution for these problems of query federation. Grouping triple patterns to lter more triples on an endpoint can prevent high latency (required processing time) and changing query evaluation order according to dataset selectivity statistics can prevent retrieving large result sets. To make WoDQA functioning in the wild, optimization step of query federation is required to be implemented. We plan to incorporate triple pattern selectivity into query reorganization using VOID properties about statistics.
On the other hand, we could not make an evaluation of our approach in this paper, since VOID documents in current VOID stores are not well-de ned. Since SPARQL endpoint de nitions, linkset descriptions or vocabularies are missing in most of VOID documents, we could not nd a chance to execute comprehensive scenarios. Developing a tool which extracts well-de ned VOID descriptions of datasets, and by this means evaluating our approach is a required future work to con rm applicability of WoDQA on linked open data. Also, evaluating the analysis cost of WoDQA for a large VOID store will be possible when well-de ned VOIDs are constructed. 6.