Databases Reference
In-Depth Information
New answers for the query can be computed on-the-fly as new sources arrive. We
now formally define the key notion of query-relevant documents in the context
of LTBQE, and give an indication as to how these documents are derived.
29
Definition 12 (Query Relevant Sources & Answers).
First let
uris
(
μ
):=
{
denote the set of URIs in a solution mapping μ.
Given a query Q and an intermediate dataset Γ,wedefinethefunction
qrel
,
which extracts from Γ a set of URIs that can (potentially) be dereferenced to
find further sources deemed relevant for Q:
qrel
(
Q,Γ
):=
tp
u
∈
U
|∃
v
s
.
t
.
(
v,u
)
∈
μ
}
uris
(
μ
)
∈
Q
μ∈
[[
{tp}
]]
Γ
To begin the recursive process of finding query-relevant sources, LTBQE takes
URIs in the query—denoted with U
Q
:=
terms
(
Q
)
∩
U
—as “seeds”, and builds an
initial dataset by dereferencing these URIs: Γ
0
:=
derefs
(
U
Q
)
. Thereafter, for
i
, define:
30
∈
N
Γ
i
+1
:=
derefs
qrel
(
Q,Γ
i
)
∪
Γ
i
The set of
LTBQE query relevant sources
for Q is given as the least n such
that Γ
n
=
Γ
n
+1
,denotedsimplyΓ
Q
.Thesetof
LTBQE query answers
for Q
is given as
[[
Q
]]
Γ
Q
, or simply denoted
Q
.
Example 11
We illustrate this core concept of LTBQE query-relevant sources with a
simple example based on Fig. 2. Let us consider our example Query 3.
First, the process extracts all raw query URIs:
U
Q
=
{
nyt:4958--
,
nytimes:latest use
,
owl:sameAs
,
dbo:revenueUSD
}
and the engine dereferences these URIs. Second, LTBQE looks to extract
additional query relevant URIs by seeing if any query patterns are matched
in the current dataset. LTBQE repeats the above process until no new
sources are found. When no other query-relevant URIs are found, a fix-
point is reached and the process terminates with the results given over the
retrieved “query-relevant documents”.
♦
6.2
(In)Completeness of LTBQE
An open question is the
decidability
of collecting query-relevant sources: does
it always terminate? This is dependent on whether one considers the Web of
29
This is similar in principle to the generic notion of reachability introduced previ-
ously [34,32], but relies here on concrete HTTP specific operations.
30
In practice, URIs need only be dereferenced once;
i.e.
,onlyURIsinqrel(
Q,Γ
i
)
\
(qrel(
Q,Γ
i−
1
)
∪ U
Q
) need be dereferenced at each stage.
