Skyline Queries in SPARQL: An Overview

• Marlene Goncalves Da Silva Universidad Simón Bolívar, Caracas, Venezuela. https://orcid.org/0000-0003-4843-0774
• Ana Isabel Aguilera Faraco Universidad de Valparaíso, Valparaíso, Chile. https://orcid.org/0000-0003-0726-1759

DOI: https://doi.org/10.22209/rt.v45n2a06

Keywords: databases, data formats, data processing, programming languages, skyline query, SPARQL

Abstract

The growth of RDF (Resource Description Framework) datasets and the expansion of their use in conjunction with the definition of SPARQL, a declarative query language, have made RDF data management an active area of research and development. In this regard, mechanisms have been proposed to help users find their desired answers in less time, including ranking methods and preference-based queries. Skyline queries constitute one of the most practical and predominant types of preference-based queries. The aim of this work was to provide a guide to specifying SPARQL skyline queries using syntax proposed in state-of-the-art works, and SPARQL versions 1.0 and 1.1. The results show the possibility of rewriting skyline queries in SPARQL to express preferences. We plan to develop a tool to translate SPARQL skyline queries applying the different grammars proposed, into SPARQL 1.0 and 1.1 with the aim of providing an automatic mechanism of translation.

References

Abidi, A., Elmi, S., Tobji, M. A. B., HadjAli, A., Yaghlane, B. B. (2018). Skyline queries over possibilistic RDF data. International Journal of Approximate Reasoning, 93, 277-289.

Abidi, A., Tobji, M. A. B., Hadjali, A., Yaghlane, B. B. (2017). Skyline modeling and computing over trust RDF data. Proceedings of the 19th international conference on enterprise information systems (ICEIS 2017). Setúbal: Science and Technology Publications, 634-643.

Alvarado, A., Baldizán, O., Vidal, M., Goncalves, M. (2013). FOPA: a final object pruning algorithm to efficiently produce skyline points. Database and Expert Systems Applications. DEXA 2013. Berlin: Springer, 334-348.

Bader, M. (2012). Space-filling curves: an introduction with applications in scientific computing. Suisse: Springer Publishing Company, Inc.

Balke W., Guntzer, U. (2004). Multi-objective query processing for database systems. Proceedings of the 30th international conference on very large data bases. New York: ACM Digital Library, 936-947.

Balke, W. T., Guntzer, U., Zheng, J. X. (2004). Efficient distributed skylining for Web information systems. Advances in Database Technology - EDBT 2004. Berlin: Springer, 256-273.

Bartolini, I., Ciaccia, P., Patella, M. (2008). Efficient sort-based skyline evaluation. ACM Transactions on Database Systems, 33, 1-49.

Bentley, J., Kung, H., Schkolnick, M., Thompson, C. (1978). On the average number of maxima in a set of vectors and applications. Journal of the ACM, 25, 536-543.

Bitbucket. (2021). SPREFQL dataengineering/sprefql – Bitbucket [online] available in: https://bitbucket.org/dataengineering/sprefql/src/master/ [accessed: 1 March 2021].

Borzsonyi, S., Kossmann, D., Stocker, K. (2001). The skyline operator. Proceedings of the 17th international conference on data engineering. Heidelberg: IEEE Computer Society, 421-430.

Chen, L., Gao, S., Anyanwu, K. (2011). Efficiently evaluating skyline queries on RDF databases. The Semanic Web: Research and Applications. ESWC 2011. Berlin: Springer, 123-138.

Chomicki, J. (2002). Querying with intrinsic preferences. In: Advances in Database Technology — EDBT 2002. Eds. Jensen, C. S., Šaltenis, S., Jeffery, K. G., Pokorny, J., Bertino, E., Böhn, K., Jarke, M. Berlin: Springer, 34-51.

Chomicki, J., Godfrey, P., Gryz, J., Liang, D. (2003). Skyline with presorting. Proceedings of the 19th international conference on data engineering (ICDE 2003). Bangalore: IEEE Computer Society, 717-719.

Elzein, N. M., Majid, M. A., Hashem, I. A. T., Yaqoob, I., Alaba, F. A., Imran, M. (2018). Managing big RDF data in clouds: challenges, opportunities, and solutions. Sustainable Cities and Society, 39, 375-386.

Endres, M., Glaser, E. (2019). Indexing for skyline computation. In: Flexible Query Answering Systems. Eds. Cuzzocrea, A., Greco, S., Larsen, H. L., Saccà, D., Andreasen, T., Christiansen, H. Suisse: Springer International Publishing, 31-42.

Feigenbaum, L. (2009). SPARQL by example [online] available in: https://www.w3.org/2009/Talks/0615-qbe/ [accessed: 12 October 2020].

Feyznia, A., Kahani, M., Zarrinkalam, F. (2014). COLINA: a method for ranking SPARQL query results through content and link analysis. Proceedings of the 13th international semantic Web conference (ISWC 2014). New York: ACM Digital Library, 273-276.

Godfrey, P., Shipley, R., Gryz, J. (2005). Maximal vector computation in large data sets. Proceedings of the 31st international conference on very large data bases. New York: ACM Digital Library, 229-240.

Gueroussova, M. Polleres, A., McIlraith, S. (2013). SPARQL with qualitative and quantitative preferences. Proceedings of the 2nd international conference on ordering and reasoning. New York: ACM Digital Library, 2-8.

Gueroussova, M., Polleres, A., McIlraith, S. (2013b). SPARQL with qualitative and quantitative preferences (extended report). Tech. Rep. CSRG-619. Toronto: University of Toronto.

Gulzar, Y., Alwan, A. A., Abdullah, R. M., Xin, Q., Swidan, M. B. (2019). SCSA: evaluating skyline queries in incomplete data. Applied Intelligence, 49, 1636-1657.

Harris, S., Seaborne, A. (2013). SPARQL 1.1 query language. W3C Recommendation [online] available in: http://www.w3.org/TR/2013/REC-sparql11-query20130321/ [accessed: 1 March 2021].

Keles, I., Hose, K. (2019). Skyline queries over knowledge graphs. Proceedings of the 18th international semantic Web conference. Berlin: Springer, 293-310.

Keles, I., Hose, K. (2019). Skyline queries over knowledge graphs. In: The Semantic Web – ISWC 2019. Eds. Ghidini, C., Hartig, O., Maleshkova, M., Svátek, V., Cruz, I., Hogan, A., Song, J., Lefrançois, M., Gandon, F. Berlin: Springer International Publishing, 293-310.

Kossmann, D., Ramsak, F., Rost, S. (2002). Shooting stars in the sky: an online algorithm for skyline queries. Proceedings of the 28th international conference on very large data bases. New York: ACM Digital Library, 275-286.

Kostylev, E. V., Reutter, J. L., Ugarte, M. (2015). Expressiveness of construct queries in SPARQL. 18th international conference on database theory (ICDT’15). Eds. Arenas, M., Ugarte, M. Brussels: Dagstuhl Publishing, 1-25.

Křemen, P. (2018). SPARQL query language for RDF [online] available in: https://cw.fel.cvut.cz/b181/_media/courses/osw/lecture-03sparql-s.pdf [accessed: 1 March 2021].

Lee, K., Lee, W. C., Zheng, B., Li, H., Tian, Y. (2010). Z-sky: an efficient skyline query processing framework based on z-order. The VLDB Journal, 19, 333-362.

MIB. (2016). My information bubble project [online] available in: http://mib.projects.iit.cnr.it/ [accessed: 1 March 2021].

Ontotext. (2020). What is RDF and why to use it? Ontotext Fundamentals Series [online] available in: https://www.ontotext.com/knowledgehub/fundamentals/what-is-rdf/ [accessed: 8 December 2020].

Papadias, D., Tao, Y., Fu, G., Seeger, B. (2005). Progressive skyline computation in database systems. ACM Transactions on Database Systems (TODS) - Special Issue: SIGMOD/PODS, 30, 41-82.

Patel-Schneider, P. F., Martin, D. (2016). EXISTStential aspects of SPARQL. Proceedings of 15th international semantic Web conference. Kobe: Computer Science Bibliography, 1-4.

Patel-Schneider, P. F., Polleres, A., Martin, D. (2018). Comparative preferences in SPARQL. In: Knowledge Engineering and Knowledge Management. Eds. Zucker, C. F., Ghidini, C., Napoli, A., Toussaint, Y. Berlin: Springer International Publishing, 289-305.

Prud’hommeaux, E., Seaborne, A. (2008). SPARQL query language for RDF. W3C Recommendation [online] available in: https://www.w3.org/TR/rdf-sparql-query/ [accessed: 2 December 2020].

RDF. (2021). RDF - semantic Web standards [online] available in: https://www.w3.org/ [accessed: 1 March 2021].

Selke, J., Balke, W. T. (2011). Skymap: a trie-based index structure for high-performance skyline query processing. Database and Expert Systems Applications. DEXA 2011. Berlin: Springer, 350-365.

Sessoms, M., Anyanwu, K. (2014). Enabling a package query paradigm on the semantic Web: model and algorithms, Transactions on Large-Scale Data -and Knowledge- Centered Systems XIII. Berlin: Springer, 1-32.

Siberski, W., Pan, J. Z., Thaden, U. (2006). Querying the semantic web with preferences. In: The Semantic Web - ISWC 2006. Eds. Cruz, I., Decker, S., Allemang, D., Preist, C., Schwabe, D., Mika, P., Uschold, M., Aroyo, L. M. Berlin: Springer, 612-624.

Tan, K., Eng, P., Ooi, B. (2001). Efficient progressive skyline computation. Proceedings of the 27th international conference on very large data bases. San Francisco: Morgan Kaufmann Publishers Inc., 301-310.

The Apache Software Foundation (2019). Arq – A SPARQL processor for jena [online] available in: http://jena.apache.org/documentation/ query/index.html [accessed: 8 November 2019].

Troumpoukis, A., Konstantopoulos, S., Charalambidis, A. (2017). An extension of SPARQL for expressing qualitative preferences. In: The Semantic Web – ISWC 2017. Eds. d’Amato, C., Fernandez, M., Tamma, V., Lecue, F., Cudré-Mauroux, P., Sequeda, J., Lange, C., Heflin, J. Berlin: Springer International Publishing, 711-727.

Zou, L., Özsu, M. T. (2017). Graph-based RDF data management. Data Science Engineering, 2, 56-70.