Top

Published in:

2015 | OriginalPaper | Chapter

RDF-SQ: Mixing Parallel and Sequential Computation for Top-Down OWL RL Inference

Authors : Jacopo Urbani, Ceriel Jacobs

Published in: Graph Structures for Knowledge Representation and Reasoning

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The size and growth rate of the Semantic Web call for querying and reasoning methods that can be applied over very large amounts of data. In this paper, we discuss how we can enrich the results of queries by performing rule-based reasoning in a top-down fashion over large RDF knowledge bases.

This paper focuses on the technical challenges involved in the top-down evaluation of the reasoning rules. First, we discuss the application of well-known algorithms in the QSQ family, and analyze their advantages and drawbacks. Then, we present a new algorithm, called RDF-SQ, which re-uses different features of the QSQ algorithms and introduces some novelties that target the execution of the OWL-RL rules.

We implemented our algorithm inside the QueryPIE prototype and tested its performance against QSQ-R, which is the most popular QSQ algorithm, and a parallel variant of it, which is the current state-of-the-art in terms of scalability. We used a large LUBM dataset with ten billion triples, and our tests show that RDF-SQ is significantly faster and more efficient than the competitors in almost all cases.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Subjective Networks: Perspectives and Challenges

next chapter Bring User Interest to Related Entity Recommendation

https://github.com/jrbn/querypie.

Abiteboul, S., Abrams, Z., Haar, S., Milo, T.: Diagnosis of asynchronous discrete event systems: datalog to the rescue!. In: Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 358–367. ACM (2005)

Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases, vol. 8. Addison-Wesley, Reading (1995)MATH

Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D.: Magic sets and other strange ways to implement logic programs. In: Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 1–15. ACM (1985)

Ceri, S., Gottlob, G., Tanca, L.: What you always wanted to know about datalog (and never dared to ask). IEEE Trans. Knowl. Data Eng. 1(1), 146–166 (1989)CrossRef

DeWitt, D., Naughton, J., Burger, J.: Nested loops revisited. In: Proceedings of the Second International Conference on Parallel and Distributed Information Systems, pp. 230–242. IEEE Comput. Soc. Press (1993)

Erling, O., Mikhailov, I.: Virtuoso: RDF support in a native RDBMS. In: de Virgilio, R., Giunchiglia, F., Tanca, L. (eds.) Semantic Web Information Management, pp. 501–519. Springer, Heidelberg (2009)

Heino, N., Pan, J.Z.: RDFS reasoning on massively parallel hardware. In: Cudré-Mauroux, P., et al. (eds.) ISWC 2012, Part I. LNCS, vol. 7649, pp. 133–148. Springer, Heidelberg (2012)CrossRef

Klyne, G., Carroll, J.J.: Resource description framework (RDF): Concepts and abstract syntax. W3C recommendation (2006)

Lloyd, J.W.: Foundations of Logic Programming. Springer, New York (1984)CrossRefMATH

10.

Madalińska-Bugaj, E., Nguyen, L.A.: Generalizing the QSQR evaluation method for horn knowledge bases. In: Nguyen, N.T., Katarzyniak, R. (eds.) New Challenges in Applied Intelligence Technologies, pp. 145–154. Springer, Heidelberg (2008)CrossRef

11.

Madalińska-Bugaj, E., Nguyen, L.A.: A generalized QSQR evaluation method for horn knowledge bases. ACM Trans. Comput. Logic 13(4), 32:1–32:28 (2012)

12.

Motik, B., Nenov, Y., Piro, R., Horrocks, I., Olteanu, D.: Parallel materialisation of datalog programs in centralised, main-memory RDF systems. In: Proceedings of AAAI. AAAI Press (2014)

13.

Nejdl, W.: Recursive strategies for answering recursive queries - The RQA/FQI strategy. In: Proceedings of the 13th International Conference on Very Large Data Bases, pp. 43–50. Morgan Kaufmann Publishers Inc. (1987)

14.

Prud’Hommeaux, E., Seaborne, A.: SPARQL query language for RDF. W3C recommendation (2008)

15.

Pérez-Urbina, H., Rodriguez-Díaz, E., Grove, M., Konstantinidis, G., Sirin, E.: Evaluation of query rewriting approaches for OWL 2. In: Proceedings of SSWS+HPCSW (2012)

16.

Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs (2009)

17.

Salvadores, M., Correndo, G., Harris, S., Gibbins, N., Shadbolt, N.: The design and implementation of minimal RDFS backward reasoning in 4store. In: Antoniou, G., Grobelnik, M., Simperl, E., Parsia, B., Plexousakis, D., De Leenheer, P., Pan, J. (eds.) ESWC 2011, Part II. LNCS, vol. 6644, pp. 139–153. Springer, Heidelberg (2011)CrossRef

18.

Urbani, J., Kotoulas, S., Maassen, J., Van Harmelen, F., Bal, H.: WebPIE: A web-scale parallel inference engine using MapReduce. Web Semant. Sci. Serv. Agents World Wide Web 10, 59–75 (2012)CrossRef

19.

Urbani, J., Margara, A., Jacobs, C., van Harmelen, F., Bal, H.: DynamiTE: Parallel materialization of dynamic RDF data. In: Alani, H., et al. (eds.) ISWC 2013, Part I. LNCS, vol. 8218, pp. 657–672. Springer, Heidelberg (2013)CrossRef

20.

Urbani, J., Margara, A., Jacobs, C., Voulgaris, S., Bal, H.: AJIRA: A lightweight distributed middleware for MapReduce and stream processing. In: 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS), pp. 545–554, June 2014

21.

Urbani, J., Piro, R., van Harmelen, F., Bal, H.: Hybrid reasoning on OWL RL. Semant. Web 5(6), 423–447 (2014)

22.

Urbani, J., van Harmelen, F., Schlobach, S., Bal, H.: QueryPIE: Backward reasoning for OWL horst over very large knowledge bases. In: Aroyo, L., Welty, C., Alani, H., Taylor, J., Bernstein, A., Kagal, L., Noy, N., Blomqvist, E. (eds.) ISWC 2011, Part I. LNCS, vol. 7031, pp. 730–745. Springer, Heidelberg (2011)CrossRef

23.

Vieille, L.: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. In: Expert Database Conference, pp. 253–267 (1986)

24.

Vieille, L.: A database-complete proof procedure based on SLD-resolution. In: Logic Programming, Proceedings of the Fourth International Conference, pp. 74–103 (1987)

25.

Vieille, L.: From QSQ towards QoSaQ: global optimization of recursive queries. In: Expert Database Conference, pp. 743–778 (1988)

26.

Vieille, L.: Recursive query processing: the power of logic. Theoret. Comput. Sci. 69(1), 1–53 (1989)MathSciNetCrossRefMATH

27.

Weaver, J., Hendler, J.A.: Parallel materialization of the finite RDFS closure for hundreds of millions of triples. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 682–697. Springer, Heidelberg (2009)CrossRef

28.

Zhou, Y., Nenov, Y., Cuenca Grau, B., Horrocks, I.: Complete query answering over horn ontologies using a triple store. In: Alani, H., et al. (eds.) ISWC 2013, Part I. LNCS, vol. 8218, pp. 720–736. Springer, Heidelberg (2013)CrossRef

29.

Zhou, Y., Nenov, Y., Grau, B.C., Horrocks, I.: Pay-as-you-go OWL query answering using a triple store. In: Proceedings of AAAI, pp. 1142–1148. AAAI Press (2014)

Title: RDF-SQ: Mixing Parallel and Sequential Computation for Top-Down OWL RL Inference
Authors: Jacopo Urbani
Ceriel Jacobs
Publisher: Springer International Publishing
Book: Graph Structures for Knowledge Representation and Reasoning
Print ISBN: 978-3-319-28701-0

Electronic ISBN: 978-3-319-28702-7

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-28702-7_8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner