LAW: Link-AWare Source Selection for Virtually Integrating Linked Data - Technologies and Applications of Artificial Intelligence - page 240

of the Sesame RDF repository. Users are required to determine which SPARQL
endpoint the sub-queries should be sent to by the GRAPH graph pattern. The
association between graph names and respective SPARQL endpoints at which
they reside is explicitly described in a configuration file. The W3C SPARQL
working group has defined a federation extension for SPARQL 1.1 [4]. However,
remote SPARQL queries require the explicit notion of endpoint URIs. The re-
quirement of additional information imposes further burden on the user. On
the other hand, the proposed approach hardly imposes any restrictions on user
queries.
The link-aware source selection approach is firstly proposed by Stuckenschmidt
[12]. They use predicate path index hierarchies of datasets for source selection.
This approach requires predicates of triple patterns must be bounded, and then
limits the variety of user queries.

3 Preliminary

The Resource Description Framework (RDF) is a language for representing in-
formation about resources in the World Wide Web [ ? ]. By using IRIs to identify
things, it provides a simple way to make statements about Web resources. An
RDF statement has three parts: subject, predicate(also called property) and
object. Formally, RDF triples are defined as:

Definition 1. Assume that I(IRIs), B(Blank nodes) and L(RDF literals) are
pairwise disjoint infinite sets. An RDF statement can be represented as a tuple:
( s,p,o ) L ) . In this tuple, s is the subject, p is the predicate

and o is the object. The tuple representing an RDF statement is called a RDF
triple, simply called triple.

∈ ( I ∪ B ) × I × ( I ∪ B ∪

A set of triples can be represented as a RDF graph, where the nodes are its
subjects and objects and predicates are represented as directed arcs(edges) which
point from subjects to objects. A RDF graph shows the entity-property-values
and relations between entities. However, it does not explicitly reveals relations
between triples. From the view of link relations, we define a set of triples as a
RDF triple link graph , where nodes are triples; A triple link graph is a directed
graph in which if two triples share at least one resource, then a typed edge
linking them is built. For example, two triples (exm:person1 foaf:name “lixj”)
and (exm:person1 foaf:age 34) are linked by an edge labeled by SS, i.e. they
share the same subject.
In SPARQL, the basic graph pattern(BGP) is the fundamental block to build
other complex graph patterns, and consists of a set of triple patterns. In dis-
tributed SPARQL queries, a triple pattern tp is relevant to a set S of datasets,
written as tp S . We define a BGP associated with relevant datasets to be a triple
pattern link graph , as following:

Definition 2. A triple pattern link graph G is an ordered pair ( V,E ) ,whereV
is a set of distinct triple patterns(associated with relevant datasets) and E is a set