An Overview on Execution Strategies for Linked Data Queries

I wrote an article titled "An Overview on Execution Strategies for Linked Data Queries" for the German database journal Datenbank-Spektrum. This article provides a general overview on approaches for an online execution of Linked Data queries, i.e., queries that range over data that is made available using the Linked Data publishing principles. In particular, the article first reviews important characteristics of the Web and their consequences for Linked Data query execution. Thereafter, the article focuses on the following three orthogonal dimensions along which Linked Data query execution approaches can be classified:

• Data source selection
• Data source ranking
• Integration of data retrieval and result construction

In the context of these dimensions, the article discusses different strategies that possible Linked Data query execution approaches may apply. Furthermore, the article outlines how the discussed strategies are implemented in the Linked Data query execution approaches that have been proposed in the literature so far. In summary, these proposed approaches can be classified along the three dimensions as follows:

Publication	Source Selection	Source Ranking	Integrated Execution
Harth et al. 2010, Umbrich et al. 2011	index-based	yes	no
Hartig et al. 2009, Hartig 2011, Hartig and Freytag 2012	live exploration	no	yes
Ladwig and Tran 2010 ("bottom up")	live exploration	yes	yes
Ladwig and Tran 2010 ("top down")	index-based	yes	yes
Ladwig and Tran 2010 ("mixed")	hybrid	yes	yes
Ladwig and Tran 2011	live exploration	no	yes
Miranker et al. 2012	live exploration	no	yes
Paret et al. 2011	index-based	no	no
Schmedding 2011	live exploration	no	yes
Tian et al. 2011	index-based	no	n/a
Wagner et al. 2012	index-based	yes	yes

Here is a pre-print of the article.

B.t.w., I'm also going to talk about this topic during the upcoming Linked Data Query Processing Tutorial at WWW2013.

Olaf