Information Technology Reference
In-Depth Information
By matching property tuple patterns on property link graphs, the relevant
datasets and the sets of property tuples for each triple pattern are decided. Then,
for each selection plan
p
G
∈
P
G
, if two triple patterns are joined and their matched
property tuples are not joined, then the edge linking them is deleted from
p
G
.
Finally, if
p
G
become a unconnected graph, then it is excluded from
P
G
.
For a selection plan, triple patterns relevant to the same dataset are sent
together(as a conjunctive query) to the relevant dataset, thus executing them in
a single subquery at the respective endpoint. The result set of a selection plan
is produced by joining all subqueries.
We implement distributed join operations using an optimizing version of nest-
loop join. Subqueries are ordered according to a heuristics-based cost estimation.
We use the variable counting technique proposed in [11]. Our algorithm uses a
variation of the technique proposed in [10] and is depicted in Algorithm 1. Firstly,
It selects the subquery with minimum cardinality(line 3) and append it to the
result list(line 4). Then, it selects the subquery from the remaining subqueries
which has minimum join cardinality with the last subquery in the result list (line
7-8) and append it to the end of the result list(line 9).
Algorithm 1.
Executing A Selection Plan
1:
order(
sqs
:
list of n joint subqueries
)
2:
result ₐ
∅
3:
mincard ₐ min
(
card
(
sqs
[1
− n
]))
4:
result ₐ result
+
{sqs
[
j
]
}
//j is the index of subquery with minimum cardinality
5:
sqs ₐ sqs\sqs
[
j
]
6:
while
sq
=
∅
do
7:
q ₐ result
[
result.len −
1]
8:
mincost ₐ card
(
q
sqs
[
i
])//i is the index of subquery which has the minimum join cardi-
nality with q
9:
result ₐ result
+
{sqs
[
i
]
}
10:
sqs ₐ sqs\sqs
[
i
]
11:
end while
12:
return
result
6 Experimental Study
In this section we present an experimental evaluation of the LAW approach.
6.1 As an Extension of Other Query Engines
The presented source selection approach(called LAWS) can combine with other
query engines. We implemented our source selection approach on top of three
different federated query engines: DARQ [8], SPLENDID [5], and FedX [10] and
compare our extensions with the original approaches.
Search WWH ::
Custom Search