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

of distinct triple pattern pairs. For each ordered pair ( v i ,v j ) ∈ E, v i ∈ V,v j ∈ V ,

v i and v j share at least one variable.

Familiar with triple link graphs, edges in triple pattern link graphs have types.

Definition 3. A selection plan p G for G is a triple pattern link graph, where a
triple pattern is relevant to one single dataset. The result set of p G are the inte-
gration of matched data of triple patterns over their respective relevant datasets.

Definition 4. The set P G is the selection plan space of G. A selection plan

p G ∈ P G is an element of this space. The size of P G is the total number of

selection plans for G.

tp S 1 ,tp S 2 , ..., tp S n } ×

|S n | ,where |S i | is the cardinality of S i . The optimization problem for B is to
prune P G and exclude any p G ∈ P G whose result set potentially being empty.

Given a BGP B =

{

,thesizeof P G is

| S 1 |×| S 2 |× ...

4 Statistical Model

To bridge the gap between triple link graphs and triple pattern link graphs, we
develop property link graphs . Firstly, the property set P of a dataset is collected.
Then, for each property p

P , we compute its domain D and range R; a property
tuple ( D,p,R ) is constructed. We define a set

∈

of property tuples to be a graph
U as a set of connected property link graphs. The elements u

U

are the
components of U . For each pair ( u i ,u j ) are disconnected. The property link
graph of one dataset may link to ones of other datasets. Consequently, links
between property link graphs reveal the links between real linked data.
Generally, linked data sources do not explicitly declare domains and ranges of
properties. The domain of a property p in one dataset S can be fetched in S by
the SPARQL query: SELECT ?d WHERE

∈U

. The object
of a triple may be a URI or a Literal. Hence, the class the object o of a triple
in one dataset S is computed as : (1) if o is a URI, the class of o is fetched in S
or from other dataset by dereferencing the URI; if the class of o is not explicitly
defined by rdf:type, then o is assigned a common class rdfs:Resource. (2) if o is
a typed literal, the class of o is the type of the literal; if o is a plane literal, o is
assigned a common class rdfs:Literal.

{ ?s p ?o. ?s rdf:type ?d. }

5 Source Selection and Execution of Selection Plans

To find relevant datasets according to property link graphs, triple patterns are
translated to property tuple patterns. For example, a triple pattern (?person
foaf:age 34 ∧∧ xsd:integer) is translated to the tuple pattern (?person foaf:age
{

). If the property tuple pattern of a triple pattern has matched
property tuples on the property link graph of a dataset, then we can state that
the triple pattern is relevant to this dataset.

xsd:integer }