On the size of intermediate results in the federated processing of SPARQL BGPs

Author
Halvorsen, Jonas
Stolpe, Audun
Date Issued
2018
Keywords
Søketeori
Semantisk web
Permalink
http://hdl.handle.net/20.500.12242/853
https://ffi-publikasjoner.archive.knowledgearc.net/handle/20.500.12242/853
DOI
10.1016/j.websem.2018.06.001
Collection
Articles
Description
Halvorsen, Jonas; Stolpe, Audun. On the size of intermediate results in the federated processing of SPARQL BGPs. Journal of Web Semantics 2018
1598972.pdf
Size: 728k
Abstract
This paper is a foundational study in the semantics of federated query answering of SPARQL BGPs. Its specific concern is to explore how the size of intermediate results can be reduced without, from a logical point of view, altering the content of the final answer. The intended application is to reduce communication costs and local memory consumption in querying dynamic network topologies and highly distributed, share-nothing or shared architectures. We define row-reducing and column-reducing operations that, if a SPARQL resultset is viewed as a table, reduces the number of rows and columns respectively. These operations are deliberately designed so that they do not anticipate the unfolding of the evaluation process, which is to say that they do not presuppose knowledge about the structure or content of data sources, or equivalently, that they do not require data to be exchange in order to make intermediate results smaller. In other words, the operations that are studied are based solely on the shape of evaluations trees and the distribution of variables within them. The paper culminates with a study of different compositions of the aforementioned reduction operators. We establish mathematically that our row- and column operators can be combined to form a single reduction operator that can be applied repeatedly without altering the semantics of the final result of the query answering process.
View Meta Data