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

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.

Authors:

• Laurent Thiry
• Michel Hassenforder

Keywords:

• Data transformation
• functional programming
• information server
• optimization.

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.