Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-15T00:39:27.408Z Has data issue: false hasContentIssue false
  • English
  • Français

Probabilistic DL Reasoning with Pinpointing Formulas: A Prolog-based Approach

Published online by Cambridge University Press:  14 January 2019

RICCARDO ZESE Open the ORCID record for RICCARDO ZESE [Opens in a new window] ,
GIUSEPPE COTA ,
EVELINA LAMMA ,
ELENA BELLODI  and
FABRIZIO RIGUZZI Open the ORCID record for FABRIZIO RIGUZZI [Opens in a new window]
RICCARDO ZESE*
Affiliation:
Dipartimento di Ingegneria – Università di Ferrara, Via Saragat 1, 44122, Ferrara, Italy (e-mails: riccardo.zese@unife.it, giuseppe.cota@unife.it, evelina.lamma@unife.it)
GIUSEPPE COTA
Affiliation:
Dipartimento di Ingegneria – Università di Ferrara, Via Saragat 1, 44122, Ferrara, Italy (e-mails: riccardo.zese@unife.it, giuseppe.cota@unife.it, evelina.lamma@unife.it)
EVELINA LAMMA
Affiliation:
Dipartimento di Ingegneria – Università di Ferrara, Via Saragat 1, 44122, Ferrara, Italy (e-mails: riccardo.zese@unife.it, giuseppe.cota@unife.it, evelina.lamma@unife.it)
ELENA BELLODI
Affiliation:
Dipartimento di Matematica e Informatica – Università di Ferrara, Via Saragat 1, 44122, Ferrara, Italy (e-mails: elena.bellodi@unife.it, fabrizio.riguzzi@unife.it)
FABRIZIO RIGUZZI
Affiliation:
Dipartimento di Matematica e Informatica – Università di Ferrara, Via Saragat 1, 44122, Ferrara, Italy (e-mails: elena.bellodi@unife.it, fabrizio.riguzzi@unife.it)
Get access Rights & Permissions [Opens in a new window]

Abstract

When modeling real-world domains, we have to deal with information that is incomplete or that comes from sources with different trust levels. This motivates the need for managing uncertainty in the Semantic Web. To this purpose, we introduced a probabilistic semantics, named DISPONTE, in order to combine description logics (DLs) with probability theory. The probability of a query can be then computed from the set of its explanations by building a Binary Decision Diagram (BDD). The set of explanations can be found using the tableau algorithm, which has to handle non-determinism. Prolog, with its efficient handling of non-determinism, is suitable for implementing the tableau algorithm. TRILL and TRILLP are systems offering a Prolog implementation of the tableau algorithm. TRILLP builds a pinpointing formula that compactly represents the set of explanations and can be directly translated into a BDD. Both reasoners were shown to outperform state-of-the-art DL reasoners. In this paper, we present an improvement of TRILLP, named TORNADO, in which the BDD is directly built during the construction of the tableau, further speeding up the overall inference process. An experimental comparison shows the effectiveness of TORNADO. All systems can be tried online in the TRILL on SWISH web application at http://trill.ml.unife.it/.

Keywords

probabilistic description logicsSemantic WebBinary Decision DiagramtableauProlog
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 19 , Issue 3 , May 2019 , pp. 449 - 476
Copyright
Copyright © Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work was supported by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM).

References

Baader, F., Horrocks, I. and Sattler, U. 2008. Description Logics. Elsevier, Amsterdam, Chapter 3, 135–179.Google Scholar
Baader, F. and Peñaloza, R. 2010a. Automata-based axiom pinpointing. Journal of Automated Reasoning 45, 2, 91–129.CrossRefGoogle Scholar
Baader, F. and Peñaloza, R. 2010b. Axiom pinpointing in general tableaux. Journal of Logic and Computation 20, 1, 5–34.CrossRefGoogle Scholar
Baader, F. and Sattler, U. 2001. An overview of tableau algorithms for description logics. Studia Logica 69, 1, 5–40.CrossRefGoogle Scholar
Beckert, B. and Posegga, J. 1995. leanTAP: Lean tableau-based deduction. Journal of Automated Reasoning 15, 3, 339–358.CrossRefGoogle Scholar
Bellodi, E., Lamma, E., Riguzzi, F. and Albani, S. 2011. A distribution semantics for probabilistic ontologies. In Proc. of the 7th International Workshop on Uncertainty Reasoning for the Semantic Web, Bonn, Germany, 23 Oct. 2011, Bobillo, F., Carvalho, R., da Costa, P. C. G., d’Amato, C., Fanizzi, N., Laskey, K. B., Laskey, K. J., Lukasiewicz, T., Martin, T., Nickles, M., and Pool, M., Eds. CEUR-WS, vol. 778. Sun SITE Central Europe, Aachen, Germany, 75–86.Google Scholar
Bock, C., Fokoue, A., Hoekstra, R., Horrocks, I., Ruttenberg, A., Sattler, U. and Smith, M. 2012. OWL 2 web ontology language: Structural specification and functional-style syntax. W3C Recommendation. URL: https://www.w3.org/TR/owl2-syntax/.Google Scholar
Bryant, R. E. 1986. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35, 8 (Aug.), 677–691.CrossRefGoogle Scholar
Carvalho, R. N., Laskey, K. B. and Da Costa, P. C. G. 2013. PR-OWL 2.0 - bridging the gap to OWL semantics. In Uncertainty Reasoning for the Semantic Web II, International Workshops URSW 2008–2010 Held at ISWC and UniDL 2010 Held at FLoC, Revised Selected Papers, Bobillo, F., da Costa, P. C. G., d’Amato, C., Fanizzi, N., Laskey, K. B., Laskey, K. J., Lukasiewicz, T., Nickles, M., and Pool, M., Eds. LNCS, vol. 7123. Springer, 1–18.Google Scholar
Ceylan, İ. İ., Mendez, J. and Peñaloza, R. 2015. The Bayesian ontology reasoner is born! In Informal Proc. of the 4th International Workshop on OWL Reasoner Evaluation (ORE-2015) Co-located with the 28th International Workshop on Description Logics (DL 2015), Dumontier, M., Glimm, B., Gonçalves, R. S., Horridge, M., Jiménez-Ruiz, E., Matentzoglu, N., Parsia, B., Stamou, G. B., and Stoilos, G., Eds. CEUR-WS, vol. 1387. CEUR-WS.org, 8–14.Google Scholar
Ceylan, İ. İ. and Peñaloza, R. 2015. Probabilistic query answering in the bayesian description logic BEl. In SUM 2015, Beierle, C., and Dekhtyar, A., Eds. Lecture Notes in Computer Science (LNCS), vol. 9310. Springer, 21–35.Google Scholar
Ding, Z. and Peng, Y. 2004. A probabilistic extension to ontology language OWL. In 37th Hawaii International Conference on System Sciences (HICSS-37 2004), CD-ROM / Abstracts Proceedings, 5–8 Jan. 2004, Sprague, R. H. Jr., Ed. IEEE Computer Society, Big Island, HI, USA, 1–10.Google Scholar
Gavanelli, M., Lamma, E., Riguzzi, F., Bellodi, E., Zese, R. and Cota, G. 2015. An abductive framework for datalog± ontologies. In Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), Vos, M. D., Eiter, T., Lierler, Y., and Toni, F., Eds. CEUR-WS, vol. 1433. CEUR-WS.org.Google Scholar
Heinsohn, J. 1994. Probabilistic description logics. In 10th Conference on Uncertainty in Artificial Intelligence (UAI 1994), Seattle, Washington, 29–31 Jul. 1994, de Mántaras, R. L., and Poole, D., Eds. Morgan Kaufmann, 311–318.Google Scholar
Horrocks, I., Kutz, O. and Sattler, U. 2006. The even more irresistible SROIQ. In Proc. of the 10th International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, 2–5 Jun. 2006, Doherty, P., Mylopoulos, J., and Welty, C. A., Eds. AAAI Press, 57–67.Google Scholar
Horrocks, I. and Sattler, U. 2007. A tableau decision procedure for ${\cal S}{\cal H}{\cal O}{\cal I}{\cal Q}$. Journal of Automated Reasoning 39, 3, 249–276.CrossRefGoogle Scholar
Hustadt, U., Motik, B. and Sattler, U. 2008. Deciding expressive description logics in the framework of resolution. Information and Computation 206, 5, 579–601.CrossRefGoogle Scholar
Jaeger, M. 1994. Probabilistic reasoning in terminological logics. In 4th International Conference on Principles of Knowledge Representation and Reasoning, Doyle, J., Sandewall, E., and Torasso, P., Eds. Morgan Kaufmann, 305–316.CrossRefGoogle Scholar
Jung, J. C. and Lutz, C. 2012. Ontology-based access to probabilistic data with OWL QL. In The Semantic Web– ISWC 2012– 11th International Semantic Web Conference, Cudré-Mauroux, P., Heflin, J., Sirin, E., Tudorache, T., Euzenat, J., Hauswirth, M., Parreira, J. X., Hendler, J., Schreiber, G., Bernstein, A., and Blomqvist, E., Eds. LNCS, vol. 7649. Springer, Berlin, Heidelberg, 182–197.CrossRefGoogle Scholar
Kifer, M. and Subrahmanian, V. S. 1992. Theory of generalized annotated logic programming and its applications. The Journal of Logic Programming 12, 3&4, 335–367.CrossRefGoogle Scholar
Kimmig, A., Demoen, B., De Raedt, L., Costa, V. S., and Rocha, R. 2011. On the implementation of the probabilistic logic programming language ProbLog. Theory and Practice of Logic Programming 11, 2–3, 235–262.CrossRefGoogle Scholar
Klinov, P. 2008. Pronto: A non-monotonic probabilistic description logic reasoner. In Proc. of the Semantic Web: Research and Applications, 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, 1–5 Jun. 2008, Bechhofer, S., Hauswirth, M., Hoffmann, J., and Koubarakis, M., Eds. LNCS, vol. 5021. Springer, 822–826.CrossRefGoogle Scholar
Klinov, P. and Parsia, B. 2008. Optimization and evaluation of reasoning in probabilistic description logic: Towards a systematic approach. In Proc. of the Semantic Web - ISWC 2008, 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, 26–30 Oct. 2008, Sheth, A. P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T. W., and Thirunarayan, K., Eds. Lecture Notes in Computer Science, vol. 5318. Springer, 213–228.Google Scholar
Klinov, P. and Parsia, B. 2011. A hybrid method for probabilistic satisfiability. In CADE, Bjørner, N., and Sofronie-Stokkermans, V., Eds. LNCS, vol. 6803. 354–368.Google Scholar
Koller, D., Levy, A. Y. and Pfeffer, A. 1997. P-CLASSIC: A tractable probabilistic description logic. In Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, Providence, Rhode Island, 27-31 Jul. 1997, Kuipers, B., and Webber, B. L., Eds. AAAI Press/The MIT Press, 390–397.Google Scholar
Lakshmanan, L. V. S. and Sadri, F. 2001. On a theory of probabilistic deductive databases. Theory and Practice of Logic Programming 1, 1, 5–42.CrossRefGoogle Scholar
Lukácsy, G. and Szeredi, P. 2009. Efficient description logic reasoning in prolog: The dlog system. Theory and Practice of Logic Programming 9, 3, 343–414.CrossRefGoogle Scholar
Lukasiewicz, T. 2008. Expressive probabilistic description logics. Artificial Intelligence 172, 6–7, 852–883.CrossRefGoogle Scholar
Lutz, C. and Schröder, L. 2010. Probabilistic Description Logics for subjective uncertainty. In 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), Lin, F., Sattler, U., and Truszczynski, M., Eds. AAAI Press, Menlo Park, CA, USA, 393–403.Google Scholar
Nilsson, N. J. 1986. Probabilistic logic. Artificial Intelligence 28, 1, 71–87.CrossRefGoogle Scholar
Panda, S. and Somenzi, F. 1995. Who are the variables in your neighborhood. In Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1995, San Jose, California, USA, 5–9 Nov. 1995, Rudell, R. L., Ed. IEEE Computer Society/ACM, 74–77.Google Scholar
Patel-Schneider, P. F., Horrocks, I. and Bechhofer, S. 2003. Tutorial on OWL. In The Semantic Web - ISWC 2003, 2nd International Semantic Web Conference, Sanibel Island, FL, USA, 2023 Oct. 2013. URL: http://www.cs.man.ac.uk/~horrocks/ISWC2003/Tutorial/.Google Scholar
Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence 32, 1, 57–95.CrossRefGoogle Scholar
Ricca, F., Gallucci, L., Schindlauer, R., Dell’Armi, T., Grasso, G. and Leone, N. 2009. OntoDLV: An ASP-based system for enterprise ontologies. Journal of Logic and Computation 19, 4, 643–670.CrossRefGoogle Scholar
Riguzzi, F., Bellodi, E., Lamma, E. and Zese, R. 2013. Parameter learning for probabilistic ontologies. In RR 2013, Faber, W., and Lembo, D., Eds. LNCS, vol. 7994. Springer, Berlin, Heidelberg, 265–270.Google Scholar
Riguzzi, F., Bellodi, E., Lamma, E. and Zese, R. 2015. Probabilistic description logics under the distribution semantics. Semantic Web 6, 5, 447–501.CrossRefGoogle Scholar
Riguzzi, F. and Swift, T. 2010. Tabling and answer subsumption for reasoning on logic programs with annotated disjunctions. In Technical Communications of the 26th International Conference on Logic Programming, ICLP 2010, Edinburgh, Scotland, UK, 16–19 Jul. 2010, Hermenegildo, M. V., and Schaub, T., Eds. LIPIcs, vol. 7. Schloss Dagstuhl - Leibniz - Zentrum fuer Informatik, Dagstuhl, Germany, 162–171.Google Scholar
Riguzzi, F. and Swift, T. 2011. The PITA system: Tabling and answer subsumption for reasoning under uncertainty. Theory and Practice of Logic Programming 11, 4–5, 433–449.CrossRefGoogle Scholar
Sato, T. 1995. A statistical learning method for logic programs with distribution semantics. In Logic Programming, Proc. of the 12th International Conference on Logic Programming, Tokyo, Japan, 13–16 Jun. 1995, Sterling, L., Ed. MIT Press, 715–729.Google Scholar
Shearer, R., Motik, B. and Horrocks, I. 2008. HermiT: A highly-efficient OWL reasoner. In Proc. of the 5th OWLED Workshop on OWL: Experiences and Directions, Collocated with the 7th International Semantic Web Conference (ISWC-2008), Karlsruhe, Germany, 26–27 Oct. 2008, Dolbear, C., Ruttenberg, A., and Sattler, U., Eds. CEUR-WS, vol. 432. CEUR-WS.org.Google Scholar
Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., and Katz, Y. 2007. Pellet: A practical OWL-DL reasoner. Journal of Web Semantics 5, 2, 51–53.CrossRefGoogle Scholar
Steigmiller, A., Liebig, T. and Glimm, B. 2014. Konclude: System description. Journal of Web Semantics 27, 78–85.CrossRefGoogle Scholar
Tsarkov, D. and Horrocks, I. 2006. FaCT++ description logic reasoner: System description. In Proc. of the Automated Reasoning, 3rd International Joint Conference, IJCAR 2006, Seattle, WA, USA, 17–20 Aug. 2006, Furbach, U., and Shankar, N., Eds. LNCS, vol. 4130. Springer, 292–297.Google Scholar
Zese, R. 2017. Probabilistic Semantic Web: Reasoning and Learning. Studies on the Semantic Web, vol. 28. IOS Press, Amsterdam.Google Scholar
Zese, R., Bellodi, E., Riguzzi, F., Cota, G. and Lamma, E. 2018. Tableau reasoning for description logics and its extension to probabilities. Annals of Mathematics and Artificial Intelligence 82, 1–3, 101–130.CrossRefGoogle Scholar