Databases Reference
In-Depth Information
Data to be infinite or finite. For an infinite Web of Data, this process is indeed
undecidable [32]. To illustrate this case, Hartig [32] uses the example of a Linked
Data server describing all natural numbers
31
,whereeach
n
∈
N
is given a deref-
erenceable URI, each
n
has a link to
n
+ 1 with the predicate
ex:next
,anda
query with the pattern “
?n ex:next ?np1 .
”isgiven.Inthiscase,thetraver-
sal of query-relevant sources will span the set of all natural numbers. However,
if the (potential) Web of Data is finite, then LTBQE is decidable; in theory, it
will terminate after processing all sources. The question of whether the Web (of
Data) is infinite or not comes down to whether the set of URIs is infinite or not:
though they may be infinite in theory [8] (individual URIs have no upper bound
for length), they are finite in practice (machines can only process URIs up to
some fixed length).
32
Of course, this is a somewhat academic distinction. In practice, the Web of
Data is suciently large that LTBQE may end up traversing an infeasibly large
number of documents before terminating. A simple worst case would be a query
with an “open pattern” consisting of three variables.
Example 12
The following query asks for data on the founders of
dbr:SAP AG
:
SELECT ?s ?p ?o WHERE {
dbr:SAP_AG dbo:foundedBy ?s .
?s ?p ?o .
}
The first query-relevant sources will be identified as the documents deref-
erenced from
dbr:SAP AG
and
dbo:foundedBy
. Thereafter, all triples in
these documents will match the open pattern, and thus all URIs in these
documents will be considered as potential query-relevant links. This will
continue recursively, crawling the entire Web of Data. Of course, this prob-
lem does not occur only for open patterns. One could also consider the
following query which asks for the friends of the founders of
dbr:SAP AG
:
SELECT ?o WHERE {
dbr:SAP_AG dbo:foundedBy ?s .
?s foaf:knows ?o .
}
This would end up crawling the connected Web of FOAF documents, as
are linked together by dereferenceable
foaf:knows
links.
♦
31
Such a server has been made available by Vrandecıc
et al.
[71], but unfortunately
stops just shy of a billion. See,
e.g.
,
32
It is not clear if URIs are (theoretically) finite strings. If so, they are countable [32].
