Skip to main content

Tractable Probabilistic Description Logic Programs

Thomas Lukasiewicz

Abstract

We propose tractable probabilistic description logic programs (or probabilistic dl-programs) for the Semantic Web, which combine tractable description logics, normal programs under the answer set semantics, and probabilities. In particular, we introduce the total well-founded semantics for probabilistic dl-programs. Contrary to the previous answer set and well-founded semantics, it is defined for all probabilistic dl-programs and all probabilistic queries. Furthermore, tight (resp., tight literal) query processing under the total well-founded semantics coincides with tight (resp., tight literal) query processing under the previous well-founded (resp., answer set) semantics whenever the latter is defined. We then present an anytime algorithm for tight query processing in probabilistic dl-programs under the total well-founded semantics. We also show that tight literal query processing in probabilistic dl-programs under the total well-founded semantics can be done in polynomial time in the data complexity and is complete for EXP in the combined complexity. Finally, we describe an application of probabilistic dl-programs in probabilistic data integration for the Semantic Web.

Book Title
Proceedings of the 1st International Conference on Scalable Uncertainty Management‚ SUM 2007‚ Washington‚ DC‚ USA‚ October 10−12‚ 2007
Editor
Henri Prade and V. S. Subrahmanian
ISBN
978−3−540−75407−7
Pages
143−156
Publisher
Springer
Series
Lecture Notes in Computer Science
Volume
4772
Year
2007