Article

Linked data query processing strategies

Authors:

Günter Ladwig,

Thanh TranAuthors Info & Claims

ISWC'10: Proceedings of the 9th international semantic web conference on The semantic web - Volume Part I

Pages 453 - 469

Published: 07 November 2010 Publication History

Abstract

Recently, processing of queries on linked data has gained attention. We identify and systematically discuss three main strategies: a bottom-up strategy that discovers new sources during query processing by following links between sources, a top-down strategy that relies on complete knowledge about the sources to select and process relevant sources, and a mixed strategy that assumes some incomplete knowledge and discovers new sources at run-time. To exploit knowledge discovered at run-time, we propose an additional step, explicitly scheduled during query processing, called correct source ranking. Additionally, we propose the adoption of stream-based query processing to deal with the unpredictable nature of data access in the distributed Linked Data environment. In experiments, we show that our implementation of the mixed strategy leads to early reporting of results and thus, more responsive query processing, while not requiring complete knowledge.

References

[1]

Avnur, R., Hellerstein, J.M.: Eddies: continuously adaptive query processing. SIGMOD Rec. 29(2), 261-272 (2000)

Digital Library

[2]

Bizer, C., Heath, T., Berners-Lee, T., Heath, T., Hepp, M., Bizer, C.: Linked data - the story so far. International Journal on Semantic Web and Information Systems (IJSWIS) (2009)

[3]

Deshpande, A., Hellerstein, J.M.: Lifting the burden of history from adaptive query processing. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, vol. 30, pp. 948-959 (2004)

Digital Library

[4]

Ge, W., Chen, J., Hu, W., Qu, Y.: Object link structure in the semantic web. In: The Semantic Web: Research and Applications, pp. 257-271 (2010)

Digital Library

[5]

Harth, A., Hose, K., Karnstedt, M., Polleres, A., Sattler, K., Umbrich, J.: Data summaries for on-demand queries over linked data. In: Proceedings of the 19th International Conference on World Wide Web (2010)

Digital Library

[6]

Hartig, O., Bizer, C., Freytag, J.: Executing SPARQL queries over the web of linked data. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 293-309. Springer, Heidelberg (2009)

Digital Library

[7]

Ives, Z.G., Halevy, A.Y., Weld, D.S.: Adapting to source properties in processing data integration queries. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France. ACM, New York (2004)

Digital Library

[8]

Ives, Z.G., Taylor, N.E.: Sideways information passing for Push-Style query processing. In: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, pp. 774-783. IEEE Computer Society, Los Alamitos (2008)

Digital Library

[9]

Kader, R.A., Boncz, P., Manegold, S., van Keulen, M.: ROX: run-time optimization of XQueries. In: Proceedings of the 35th SIGMOD International Conference on Management of Data, Providence, Rhode Island, USA, pp. 615-626. ACM, New York (2009)

Digital Library

[10]

Klyne, G., Carroll, J.J., McBride, B.: Resource description framework (RDF): concepts and abstract syntax (2004)

[11]

Ladwig, G., Tran, T.: Linked data query processing strategies - technical report. Technical report (2010), http://people.aifb.kit.edu/gla/tr/ldqp_report.pdf

[12]

Neumann, T., Weikum, G.: RDF-3X: a RISC-style engine for RDF. Proc. VLDB Endow. 1(1), 647-659 (2008)

Digital Library

[13]

Neumann, T., Weikum, G.: Scalable join processing on very large RDF graphs. In: Proceedings of the 35th SIGMOD International Conference on Management of Data, Providence, Rhode Island, USA, pp. 627-640. ACM, New York (2009)

Digital Library

[14]

Prud'hommeaux, E., Seaborne, A.: SPARQL Query Language for RDF. W3C Recommendation (2008)

[15]

Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C., Reynolds, D.: SPARQL basic graph pattern optimization using selectivity estimation. In: Proceeding of the 17th International Conference on World Wide Web, Beijing, China (2008)

Digital Library

[16]

Wilschut, A.N., Apers, P.M.G.: Dataflow query execution in a parallel mainmemory environment. Distributed and Parallel Databases 1(1), 103-128 (1993)

Digital Library

Cited By

Cheng SHartig O(2020)FedQPLProceedings of the 22nd International Conference on Information Integration and Web-based Applications & Services10.1145/3428757.3429120(436-445)Online publication date: 30-Nov-2020
https://dl.acm.org/doi/10.1145/3428757.3429120
Torre-Bastida ABermúdez JIllarramendi A(2018)A Rule-Based Transducer for Querying Incompletely Aligned DatasetsACM Transactions on the Web10.1145/322832812:4(1-40)Online publication date: 27-Sep-2018
https://dl.acm.org/doi/10.1145/3228328
Lynden SYui MMatono ANakamura AOgawa HKojima I(2016)Optimising Coverage, Freshness and Diversity in Live Exploration-based Linked Data QueriesProceedings of the 6th International Conference on Web Intelligence, Mining and Semantics10.1145/2912845.2912859(1-12)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2912845.2912859
Show More Cited By

Linked data query processing strategies
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Data Mining Using Classification Techniques in Query Processing Strategies
AICCSA '01: Proceedings of the ACS/IEEE International Conference on Computer Systems and Applications

Abstract: Given a query, there are many different query-processing strategies to fulfill user requirement. The selective of tuples are from 0% t o 100%. The found set of relation will determine the different of query processing strategies being ...
View-based query processing: On the relationship between rewriting, answering and losslessness

As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases ...
Query processing strategies in a distributed database

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISWC'10: Proceedings of the 9th international semantic web conference on The semantic web - Volume Part I

November 2010

829 pages

ISBN:364217745X

Editors:
Peter F. Patel-Schneider
Bell Labs Research, Murray Hill, NJ
,
Yue Pan
IBM Research Labs, Beijing, China
,
Pascal Hitzler
Wright State University, Dayton, OH
,
Peter Mika
Yahoo! Research, Barcelona, Spain
,
Lei Zhang
IBM Research Labs, Shanghai, China

Sponsors

Elsevier
Ontotext
Artificial Intelligence Journal
Yahoo!
Saltlux

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 November 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng SHartig O(2020)FedQPLProceedings of the 22nd International Conference on Information Integration and Web-based Applications & Services10.1145/3428757.3429120(436-445)Online publication date: 30-Nov-2020
https://dl.acm.org/doi/10.1145/3428757.3429120
Torre-Bastida ABermúdez JIllarramendi A(2018)A Rule-Based Transducer for Querying Incompletely Aligned DatasetsACM Transactions on the Web10.1145/322832812:4(1-40)Online publication date: 27-Sep-2018
https://dl.acm.org/doi/10.1145/3228328
Lynden SYui MMatono ANakamura AOgawa HKojima I(2016)Optimising Coverage, Freshness and Diversity in Live Exploration-based Linked Data QueriesProceedings of the 6th International Conference on Web Intelligence, Mining and Semantics10.1145/2912845.2912859(1-12)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2912845.2912859
Özsu M(2016)A survey of RDF data management systemsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-5554-y10:3(418-432)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s11704-016-5554-y
Sabri MGangemi ALeonardi SPanconesi A(2015)A Hybrid Framework for Online Execution of Linked Data QueriesProceedings of the 24th International Conference on World Wide Web10.1145/2740908.2741751(515-519)Online publication date: 18-May-2015
https://dl.acm.org/doi/10.1145/2740908.2741751
Hartig OÖzsu MChung CBroder AShim KSuel T(2014)Reachable subwebs for traversal-based query executionProceedings of the 23rd International Conference on World Wide Web10.1145/2567948.2576947(541-546)Online publication date: 7-Apr-2014
https://dl.acm.org/doi/10.1145/2567948.2576947
Gunaratna KLalithsena SSheth A(2014)Alignment and dataset identification of linked data in Semantic WebWiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery10.1002/widm.11214:2(139-151)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1002/widm.1121
Vasilyeva EThiele MBornhövd CLehner WBoncz PNeumann T(2013)Leveraging flexible data management with graph databasesFirst International Workshop on Graph Data Management Experiences and Systems10.1145/2484425.2484437(1-6)Online publication date: 23-Jun-2013
https://dl.acm.org/doi/10.1145/2484425.2484437
Arenas MGutierrez CMiranker DPérez JSequeda J(2013)Querying Semantic Data on the Web?ACM SIGMOD Record10.1145/2430456.243045841:4(6-17)Online publication date: 17-Jan-2013
https://dl.acm.org/doi/10.1145/2430456.2430458
Saleem MNgonga Ngomo AXavier Parreira JDeus HHauswirth M(2013)DAWProceedings of the 12th International Semantic Web Conference - Part I10.1007/978-3-642-41335-3_36(574-590)Online publication date: 21-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41335-3_36
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents