Standard

Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries. / Bozzon, Alessandro; Valle, Emanuele Della; Magliacane, Sara.

Search Computing: Broadening Web Search. Vol. 7538 Berlin : Springer, 2012. p. 143-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7538).

Research output: Chapter in Book/Conference proceedings/Edited volumeChapterScientificpeer-review

Harvard

Bozzon, A, Valle, ED & Magliacane, S 2012, Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries. in Search Computing: Broadening Web Search. vol. 7538, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7538, Springer, Berlin, pp. 143-156. https://doi.org/10.1007/978-3-642-34213-4_10

APA

Bozzon, A., Valle, E. D., & Magliacane, S. (2012). Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries. In Search Computing: Broadening Web Search (Vol. 7538, pp. 143-156). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7538). Berlin: Springer. https://doi.org/10.1007/978-3-642-34213-4_10

Vancouver

Bozzon A, Valle ED, Magliacane S. Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries. In Search Computing: Broadening Web Search. Vol. 7538. Berlin: Springer. 2012. p. 143-156. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-34213-4_10

Author

Bozzon, Alessandro ; Valle, Emanuele Della ; Magliacane, Sara. / Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries. Search Computing: Broadening Web Search. Vol. 7538 Berlin : Springer, 2012. pp. 143-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inbook{94aa26b7ac4c45d5abac6ec5e9e4604f,
title = "Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries",
abstract = "With the widespread adoption of Linked Data, the efficient processing of SPARQL queries gains importance. A crucial category of queries that is prone to optimization is {"}top-k{"} queries, i.e. queries returning the top k results ordered by a specified ranking function. Top-k queries can be expressed in SPARQL by appending to a SELECT query the ORDER BY and LIMIT clauses, which impose a sorting order on the result set, and limit the number of results. However, the ORDER BY and LIMIT clauses in SPARQL algebra are result modifiers, i.e. their evaluation is performed only after the evaluation of the other query clauses. The evaluation of ORDER BY and LIMIT clauses in SPARQL engines typically requires the process of all the matching solutions (possibly thousands), followed by a monolithically computation of the ranking function for each solution, even if only a limited number (e.g. K = 10) of them were requested, thus leading to poor performance. In this paper, we present SPARQL-RANK, an extension of the SPARQL algebra and execution model that supports ranking as a firstclass SPAR-QL construct. The new algebra and execution model allow for splitting the ranking function and interleaving it with other operations. We also provide a prototypal open source implementation of SPARQL-RANK based on ARQ, and we carry out a series of preliminary experiments.",
keywords = "Ranking Function, Rank Operator, Graph Pattern, Execution Model, Query Optimization",
author = "Alessandro Bozzon and Valle, {Emanuele Della} and Sara Magliacane",
year = "2012",
doi = "10.1007/978-3-642-34213-4_10",
language = "English",
isbn = "9783642342127",
volume = "7538",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "143--156",
booktitle = "Search Computing: Broadening Web Search",

}

RIS

TY - CHAP

T1 - Extending SPARQL algebra to support efficient evaluation of top-k SPARQL queries

AU - Bozzon, Alessandro

AU - Valle, Emanuele Della

AU - Magliacane, Sara

PY - 2012

Y1 - 2012

N2 - With the widespread adoption of Linked Data, the efficient processing of SPARQL queries gains importance. A crucial category of queries that is prone to optimization is "top-k" queries, i.e. queries returning the top k results ordered by a specified ranking function. Top-k queries can be expressed in SPARQL by appending to a SELECT query the ORDER BY and LIMIT clauses, which impose a sorting order on the result set, and limit the number of results. However, the ORDER BY and LIMIT clauses in SPARQL algebra are result modifiers, i.e. their evaluation is performed only after the evaluation of the other query clauses. The evaluation of ORDER BY and LIMIT clauses in SPARQL engines typically requires the process of all the matching solutions (possibly thousands), followed by a monolithically computation of the ranking function for each solution, even if only a limited number (e.g. K = 10) of them were requested, thus leading to poor performance. In this paper, we present SPARQL-RANK, an extension of the SPARQL algebra and execution model that supports ranking as a firstclass SPAR-QL construct. The new algebra and execution model allow for splitting the ranking function and interleaving it with other operations. We also provide a prototypal open source implementation of SPARQL-RANK based on ARQ, and we carry out a series of preliminary experiments.

AB - With the widespread adoption of Linked Data, the efficient processing of SPARQL queries gains importance. A crucial category of queries that is prone to optimization is "top-k" queries, i.e. queries returning the top k results ordered by a specified ranking function. Top-k queries can be expressed in SPARQL by appending to a SELECT query the ORDER BY and LIMIT clauses, which impose a sorting order on the result set, and limit the number of results. However, the ORDER BY and LIMIT clauses in SPARQL algebra are result modifiers, i.e. their evaluation is performed only after the evaluation of the other query clauses. The evaluation of ORDER BY and LIMIT clauses in SPARQL engines typically requires the process of all the matching solutions (possibly thousands), followed by a monolithically computation of the ranking function for each solution, even if only a limited number (e.g. K = 10) of them were requested, thus leading to poor performance. In this paper, we present SPARQL-RANK, an extension of the SPARQL algebra and execution model that supports ranking as a firstclass SPAR-QL construct. The new algebra and execution model allow for splitting the ranking function and interleaving it with other operations. We also provide a prototypal open source implementation of SPARQL-RANK based on ARQ, and we carry out a series of preliminary experiments.

KW - Ranking Function

KW - Rank Operator

KW - Graph Pattern

KW - Execution Model

KW - Query Optimization

UR - http://www.scopus.com/inward/record.url?scp=84893660810&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-34213-4_10

DO - 10.1007/978-3-642-34213-4_10

M3 - Chapter

SN - 9783642342127

VL - 7538

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 143

EP - 156

BT - Search Computing: Broadening Web Search

PB - Springer

CY - Berlin

ER -

ID: 36754716