Federated SPARQL Queries Processing with Replicated Fragments

详细信息    查看全文

• 关键词：Linked data ; Federated query processing ; Source selection ; Fragment replication
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9366
• 期：1
• 页码：36-51
• 全文大小：860 KB
• 参考文献：1.Acosta, M., Vidal, M., Lampo, T., Castillo, J., Ruckhaus, E.: ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints. In: Aroyo et al. [5], pp. 18–34
  2.Aluç, G., Hartig, O., Özsu, M.T., Daudjee, K.: Diversified Stress Testing of RDF Data Management Systems. In: Mika et al. [15], pp. 197–212
  3.Aluç, G., Ozsu, M.T., Daudjee, K., Hartig, O.: chameleon-db: a Workload-Aware Robust RDF Data Management System. University of Waterloo, Tech. Rep. CS-2013-10 (2013)
  4. Buil-Aranda, C., Hogan, A., Umbrich, J., Vandenbussche, P.-Y.: SPARQL web-querying infrastructure: ready for action? In: Alani, H., et al. (eds.) ISWC 2013, Part II. LNCS, vol. 8219, pp. 277–293. Springer, Heidelberg (2013) CrossRef
  5. Aroyo, L., Welty, C., Alani, H., Taylor, J., Bernstein, A., Kagal, L., Noy, N., Blomqvist, E. (eds.): ISWC 2011, Part I. LNCS, vol. 7031. Springer, Heidelberg (2011)
  6.Basca, C., Bernstein, A.: Avalanche: putting the spirit of the web back into semantic web querying. In: Polleres, A., Chen, H. (eds.) ISWC Posters&Demos. CEUR Workshop Proceedings, vol. 658. CEUR-WS.org. (2010)
  7.Bizer, C., Heath, T., Berners-Lee, T.: Linked Data - The Story So Far. Int. J. Semantic Web Inf. Syst. 5(3), 1–22 (2009)CrossRef
  8.Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-Wise Independent Permutations. J. Comput. Syst. Sci. 60(3), 630–659 (2000)MathSciNet CrossRef MATH
  9.Görlitz, O., Staab, S.: SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions. In: Hartig, O., Harth, A., Sequeda, J. (eds.) COLD (2011)
  10.Gutierrez, C., Hurtado, C.A., Mendelzon, A.O., Pérez, J.: Foundations of Semantic Web databases. J. Comput. Syst. Sci. 77(3), 520–541 (2011)CrossRef MATH
  11.Halevy, A.Y.: Answering queries using views: A survey. VLDB J. 10(4), 270–294 (2001)CrossRef MATH
  12.Hose, K., Schenkel, R.: Towards benefit-based RDF source selection for SPARQL queries. In: Virgilio, R.D., Giunchiglia, F., Tanca, L. (eds.) SWIM, p. 2. ACM (2012)
  13.Ibáñez, L.D., Skaf-Molli, H., Molli, P., Corby, O.: Col-Graph: towards writable and scalable linked open data. In: Mika et al. [15], pp. 325–340
  14.Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Aho, A.V., et al. (eds.) ACM Symposium on Theory of Computing, pp. 38–49. ACM (1973)
  15. Mika, P. (ed.): ISWC 2014, Part I. LNCS, vol. 8796. Springer, Heidelberg (2014)
  16.Montoya, G., Skaf-Molli, H., Molli, P., Vidal, M.E.: Fedra: Query Processing for SPARQL Federations with Divergence. Tech. rep., Université de Nantes (May 2014)
  17.Özsu, M.T., Valduriez, P.: Principles of distributed database systems. Springer (2011)
  18. Quilitz, B., Leser, U.: Querying distributed rdF data sources with SPARQL. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) ESWC 2008. LNCS, vol. 5021, pp. 524–538. Springer, Heidelberg (2008) CrossRef
  19. Saleem, M., Ngonga Ngomo, A.-C.: HiBISCuS: hypergraph-based source selection for SPARQL endpoint federation. In: Presutti, V., d’Amato, C., Gandon, F., d’Aquin, M., Staab, S., Tordai, A. (eds.) ESWC 2014. LNCS, vol. 8465, pp. 176–191. Springer, Heidelberg (2014) CrossRef
  20. Saleem, M., Ngonga Ngomo, A.-C., Xavier Parreira, J., Deus, H.F., Hauswirth, M.: DAW: duplicate-AWare federated query processing over the web of data. In: Alani, H., et al. (eds.) ISWC 2013, Part I. LNCS, vol. 8218, pp. 574–590. Springer, Heidelberg (2013) CrossRef
  21.Schwarte, A., Haase, P., Hose, K., Schenkel, R., Schmidt, M.: FedX: Optimization Techniques for Federated Query Processing on Linked Data. In: Aroyo et al. [5], pp. 601–616
  22.Verborgh, R., Hartig, O., Meester, B.D., Haesendonck, G., Vocht, L.D., Sande, M.V., Cyganiak, R., Colpaert, P., Mannens, E., de Walle, R.V.: Querying Datasets on the Web with High Availability. In: Mika et al. [15], pp. 180–196
  23.Verborgh, R., Sande, M.V., Colpaert, P., Coppens, S., Mannens, E., de Walle, R.V.: Web-Scale querying through linked data fragments. In: Bizer, C., et al. (eds.) WWW Workshop on LDOW 2014. CEUR Workshop Proceedings, vol. 1184. CEUR-WS.org (2014)
  24.Wilcoxon, F.: Individual comparisons by ranking methods. In: Breakthroughs in Statistics, pp. 196–202. Springer (1992)
  
• 作者单位：Gabriela Montoya (25) (26)
  Hala Skaf-Molli (25)
  Pascal Molli (25)
  Maria-Esther Vidal (27)
  
  25. LINA – Nantes University, Nantes, France
  26. Unit UMR6241 CNRS, Nantes, France
  27. Universidad Simón Bolívar, Caracas, Venezuela
  
• 丛书名：The Semantic Web - ISWC 2015
• ISBN：978-3-319-25007-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Federated query engines provide a unified query interface to federations of SPARQL endpoints. Replicating data fragments from different Linked Data sources facilitates data re-organization to better fit federated query processing needs of data consumers. However, existing federated query engines are not designed to support replication and replicated data can negatively impact their performance. In this paper, we formulate the source selection problem with fragment replication (SSP-FR). For a given set of endpoints with replicated fragments and a SPARQL query, the problem is to select the endpoints that minimize the number of tuples to be transferred. We devise the Fedra source selection algorithm that approximates SSP-FR. We implement Fedra in the state-of-the-art federated query engines FedX and ANAPSID, and empirically evaluate their performance. Experimental results suggest that Fedra efficiently solves SSP-FR, reducing the number of selected SPARQL endpoints as well as the size of query intermediate results.