Functional and Efficient Query Interpreters: Principle, Application and Performances’ Comparison

Authors: Laurent Thiry, Michel Hassenforder

Abstract:

This paper presents a general approach to implement efficient queries’ interpreters in a functional programming language. Indeed, most of the standard tools actually available use an imperative and/or object-oriented language for the implementation (e.g. Java for Jena-Fuseki) but other paradigms are possible with, maybe, better performances. To proceed, the paper first explains how to model data structures and queries in a functional point of view. Then, it proposes a general methodology to get performances (i.e. number of computation steps to answer a query) then it explains how to integrate some optimization techniques (short-cut fusion and, more important, data transformations). It then compares the functional server proposed to a standard tool (Fuseki) demonstrating that the first one can be twice to ten times faster to answer queries.

Keywords: Data transformation, functional programming, information server, optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.2571944

References:

[1] A. V. Aho, J. E. Hopcroft, and J. Ullman, Data Structures and Algorithms, 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1983.
[2] J. Hughes, “Research topics in functional programming,” D. A. Turner, Ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1990, ch. Why Functional Programming Matters, pp. 17–42.
[3] C. Okasaki, Purely Functional Data Structures. New York, NY, USA: Cambridge University Press, 1998.
[4] B. O’Sullivan, J. Goerzen, and D. Stewart, Real World Haskell, 1st ed. O’Reilly Media, Inc., 2008.
[5] P. Hitzler, M. Krtzsch, and S. Rudolph, Foundations of Semantic Web Technologies, 1st ed. Chapman & Hall/CRC, 2009.
[6] O. Cur and G. Blin, RDF Database Systems: Triples Storage and SPARQL Query Processing, 1st ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2014.
[7] M. Martin, J. Unbehauen, and S. Auer, “Improving the Performance of Semantic Web Applications with SPARQL Query Caching,” in Proceedings of 7th Extended Semantic Web Conference (ESWC 2010), 30 May – 3 June 2010, Heraklion, Crete, Greece, ser. Lecture Notes in Computer Science, L. Aroyo, G. Antoniou, E. Hyv¨onen, A. ten Teije, H. Stuckenschmidt, L. Cabral, and T. Tudorache, Eds., vol. 6089. Berlin / Heidelberg: Springer, 2010, pp. 304–318.
[8] R. Verborgh, O. Hartig, B. De Meester, G. Haesendonck, L. De Vocht, M. Vander Sande, R. Cyganiak, P. Colpaert, E. Mannens, and R. Van de Walle, “Querying datasets on the Web with high availability,” in Proceedings of the 13th International Semantic Web Conference, ser. Lecture Notes in Computer Science, P. Mika, T. Tudorache, A. Bernstein, C. Welty, C. Knoblock, D. Vrandei, P. Groth, N. Noy, K. Janowicz, and C. Goble, Eds., vol. 8796. Springer, 2014, pp. 180–196.
[9] A. Hogan, A. Harth, J. Umrich, S. Kinsella, A. Polleres, and S. Decker, “Searching and browsing linked data with swse: the semantic web search engine,” Web Semantics: Science, Services and Agents on the World Wide Web, vol. 9, no. 4, 2011.
[10] L. Thiry, M. Mahfoudh, and M. Hassenforder, “A functional inference system for the web,” IJWA, vol. 6, no. 1, pp. 1–13, 2014.
[11] L. Thiry, H. Zhao, and M. Hassenforder, “Categories for (big) data models and optimization,” Journal of Big Data, vol. 5, no. 1, p. 21, Jul 2018.
[12] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, The Description Logic Handbook: Theory, Implementation and Applications, 2nd ed. New York, NY, USA: Cambridge University Press, 2010.
[13] A. Takano and E. Meijer, “Shortcut deforestation in calculational form,” in Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture, ser. FPCA ’95. New York, NY, USA: ACM, 1995, pp. 306–313.