Probabilistic OWL (PR-OWL) improves the Web Ontology Language (OWL) with the ability to treat uncertainty using Multi-Entity Bayesian Networks (MEBN). PR-OWL 2 presents a better integration with OWL and its underlying logic, allowing the creation of ontologies with probabilistic and deterministic parts. However, there are scalability problems since PR-OWL 2 is built upon OWL 2 DL which is a version of OWL based on description logic SROIQ(D) and with high complexity. To address this issue, this paper proposes PR-OWL 2 RL, a scalable version of PR-OWL based on OWL 2 RL pro le and triplestores (databases based on RDF triples). OWL 2 RL allows reasoning in polynomial time for the main reasoning tasks. This paper also presents First-Order expressions accepted by this new language and analyzes its expressive power. A comparison with the previous language presents which kinds of problems are more suitable for each version of PR-OWL.
Web Ontology Language (OWL) is the main language in the Semantic Web for
creating ontologies. It lacks the capacity for treating uncertainty, limiting its
application in several kinds of domains. Various approaches have been proposed
to solve this issue using di erent formalisms, such as Bayesian networks, fuzzy
logic, and Dempster-Sha er theory. One of these approaches, Probabilistic OWL
(PR-OWL) [
OWL DL reasoner for modeling and reasoning with the deterministic part of the ontology.
PR-OWL 2 implementation, however, has some scalability problems due to
the time complexity of OWL 2 DL reasoners to solve complex expressions. This
hinders the ability to work with domains that have large assertive databases. One
example is the public procurement fraud detection domain developed in Brazil,
for which a probabilistic ontology was created using PR-OWL 2 [
The solution proposed for overcoming this limitation is to use triplestores
together with the OWL 2 RL pro le to create a new version of PR-OWL 2,
named PR-OWL 2 RL. The OWL 2 RL [
The proposal of this new language requires: 1) to review the PR-OWL language according the OWL 2 RL syntax restrictions; 2) a new algorithm to evaluate the MEBN rst-order formulas using triplestores; and 3) to design a scalable algorithm for generating Situation Speci c Bayesian Networks (SSBN). This paper discusses the rst two issues.
This paper is organized as follows. Section 2 describes some relevant concepts for the understanding of this work: MEBN, OWL and PR-OWL. Section 3 presents PR-OWL 2 bottlenecks that motivated this work. Section 4 introduces the language proposed and shows how the rst-order formulas can be evaluated using the SPARQL language. Finally, Section 5 presents some conclusions and possible future work. 2
This section presents some concepts necessary for the understanding of this paper. Section 2.1 presents Multi-Entity Bayesian Networks, the formalism used by PR-OWL to deal with uncertainty in the OWL language. Section 2.2 presents the OWL language and its versions, including the OWL 2 RL pro le, and triplestores. Section 2.3 presents PR-OWL, its extension, PR-OWL 2, and its implementation in the UnBBayes Framework. 2.1
Multi-Entity Bayesian Networks
Multi-Entity Bayesian Networks (MEBN) is a formalism for representing
rstorder probabilistic knowledge bases [
MEBN models the domain using a MEBN Theory (MTheory), which is composed of random variables that together have a unique joint probability distribution. The knowledge is divided into MEBN Fragments (MFrags). Each MFrag is composed by resident nodes, input nodes, and context nodes. Resident nodes are random variables for which the Local Probability Distribution (LPD) is de ned in the MFrag where they are. Input nodes are references to resident nodes de ned in a di erent MFrag. Context nodes contain restrictions that need to be satis ed in order to correctly instantiate the corresponding MFrag. The nodes represent entity attributes and relationships between entities. Each node is parameterized with ordinary variables (OV), placeholders lled with entity instances available in the knowledge base during the instantiation of the model.
Figure 1 shows the MFrag Front Of Enterprise of the Procurement Fraud
ontology [
The direct model-theoretic semantics of OWL 2 is called Direct Semantics,
which is strongly related to the semantics of description logics [
OWL 2 has three di erent pro les (syntactic subsets): OWL 2 EL, OWL 2
QL, and OWL 2 RL. All of them are more restrictive than OWL 2 DL and trades
o OWL 2's expressive power for computational or implementation bene ts. In
these pro les, most types of reasoning can be made in polynomial time. OWL 2
EL is suitable for ontologies with a very large but simple TBox. OWL 2 QL is
suitable to work with conjunctive queries, permitting the use of ontological
reasoning in systems like relational databases through a query rewriting approach.
OWL 2 RL, based on Datalog and in R-entailment [
W3C proposes a set of rules called OWL 2 RL/RDF that implements the
OWL 2 RL pro le. This set of rules is based on RDF Semantic, where the
knowledge is organized in graphs, composed by RDF triples. Each RDF triple is
composed by a subject linked to an object by a property. The reasoning is made
through rules, where given a set of speci c triples and a rule, we can get another
expression that follows logically from the rule. The Theorem PR1 [
SubAnnotationPropertyOf, AnnotationPropertyDomain,
AnnotationPropertyRange; and { each axiom in O2 is an assertion of the form as speci ed below, for a1, a2, . . . , an a named individual:
ClassAssertion( C a ) where C is a class, ObjectPropertyAssertion( OP a1 a2 ) where OP is an object property, DataPropertyAssertion( DP a v ) where DP is a data property, or
The OWL 2 RL pro le is implemented by some triplestores. Triplestores are databases that organize the knowledge in graphs composed by RDF triples. They are becoming very useful and there are a lot of commercial (e.g., GraphDB, Oracle Spatial and Graph, and AllegroGraph) and free implementations (e.g., Sesame). They normally implement the RDF/RDFS entailment rules, using materialization for expanding the rules when new declarations are added to the base. SPARQL is the main language used for querying RDF databases. It is very similar to SQL, acting over generalized RDF graphs. Most triplestores accept, in addiction to RDFS, inference with some constructions of OWL. Implementations of the OWL 2 RL pro le are common. 2.3
PR-OWL
Probabilistic OWL (PR-OWL) is an extension of the OWL language that
permits the creation of probabilistic ontologies [
UnBBayes has an implementation of PR-OWL and MEBN [
PR-OWL 2 [
definesUncertaintyOf that links a random variable to an OWL property. The additional properties isObjectIn and isSubObjectIn allow the mapping of both domain and range of the OWL property to its corresponding concept in MEBN. PR-OWL 2 also has other improvements, like the support to polymorphism and the use of OWL datatypes. A plug-in for PR-OWL 2 was developed in UnBBayes, using Protege for modeling the deterministic parts of the ontology. Protege is a popular open source framework for editing ontologies. Moreover, HermiT is used for evaluating the context nodes and for getting information about ndings. 3
PR-OWL 2 and its implementation in UnBBayes have some scalability and
expressibility problems. OWL 2 DL, which is used in PR-OWL 2 de
nition/implementation, is based on description logic SROIQ(D) that has complexity
N2EXPTIME-complete [
We also have scalability problems because of the use of Protege's GUI and
API in UnBBayes' PR-OWL 2 implementation. We made tests using LUBM
ontologies to verify the performance of this implementation. LUBM (Lehigh
University Benchmark) [
This scalability problems limit the use of PR-OWL in domains with large
assertive bases. In the domain of procurement fraud detection [
Since PR-OWL 2 is written in OWL 2 DL, one possibility is to use an OWL 2 DL reasoner for solving the FOL formulas during MEBN reasoning. PR-OWL 2 current implementation in UnBBayes does that.
Evaluating MEBN FOL formulas using an OWL DL reasoner requires some workarounds. The Table 1 presents the formulas that are allowed in the current implementation of UnBBayes, where ov are ordinary variables, CONST are constants, and booleanRV are Boolean random variables. Expressions with connectives and quanti ers are not allowed in this version. ov1 = ov2 booleanRV( ov1 [ , ov2 , . . . ] ) ov0 = nonBooleanRV( ov1 ) ov0 = nonBooleanRV( ov1 [ , ov2, . . . ] ) CONST = nonBooleanRV( ov1 [ , ov2 , . . . ] ) nonBooleanRV( ov1 [ , ov2 , . . . ] ) = CONST nonBooleanRV( ov1 ) = ov0 nonBooleanRV( ov1 [ , ov2 , . . . ] ) = ov0 Negation NOT ( ov1 = ov2 ) NOT booleanRV( ov1 [ , ov2, . . . ] ) NOT ( ov0 = nonBooleanRV( ov1 )) NOT ( nonBooleanRV ( ov 1 ) = ov0) 4
In order to overcome the limitations presented, we propose PR-OWL 2 RL, a more scalable version of PR-OWL based in the OWL 2 RL pro le. The purpose is to use an RDF triplestore database for both the storage and reasoning with very large ontologies represented as RDF triples. This is possible because OWL 2 RL allows reasoning in polynomial time for the main reasoning tasks. SPARQL is the common query language used with RDF triples.
Since PR-OWL 2 is written in OWL 2 DL, some adjustments are necessary to adapt it for OWL 2 RL. This is due to the fact that OWL 2 RL imposes several syntactic restrictions on the OWL expressions. Running a validator developed by the Manchester University 6 we found the following unsupported features: 1. Use of non-superclass expression where superclass expression is required; 2. Use of non-subclass expression where subclass expression is required; 3. Use of non-equivalent-class expression where equivalent-class expression is required; and 4. Use of unsupported data range.
Figure 3 shows examples for each kind of unsupported feature. The rst case occurs for several reasons, such as the use of existential quanti er and disjunction on the right side of a subClass expression or in range/domain expressions, the use of owl:Thing as superclass or in range/domain expressions, and the use of the quali ed restriction exactly. The second occurs in the class owl:Thing, that is setted as a subclass of the restriction 'hasUID only String'. The property hasUID is used to guarantee that every instance in PR-OWL has a unique identi er (a requisite necessary to work with MEBN, where each possible state has to be unique). The third occurs in all equivalent expressions of PR-OWL 2, which includes conjunctions, min/max/exactly cardinality expressions, and universal/existential quanti ers. OWL 2 RL is very restrictive in relation to equivalent expressions, allowing only Class, intersection, and hasValue expressions. Finally, the fourth occurs in the isRepresentedAs range expression, where all possible formats to represent the probabilistic distributions are listed.
Since the syntax of OWL 2 RL/RDF is based on RDF, it permits generalized RDF graphs, not having the several restrictions of OWL 2 DL. The pure OWL 2 RL pro le, however, has restrictions to allow reasoning also with the Direct Semantics. We choose to adapt PR-OWL 2 RL with the OWL 2 RL restrictions for keeping the compatibility with both semantics. In order to make this adaptation it is necessary to x the unsupported features listed above.
To solve the unsupported features, we analyzed three alternatives. The rst consists in rewriting all expressions of PR-OWL 2 from OWL 2 DL to OWL 2 RL. However, this is not possible due the less expressive power of OWL 2 RL language. Expressions subClass, for instance, with existential quanti er on the right side cannot be expressed in this pro le. The second alternative consists in rewriting to OWL 2 RL the expressions that can be rewritten, removing the others, and passing the responsibility of validating them forward to the PR-OWL reasoner. The problem with this alternative is that the resulting ontology is hard to understand due to the rewriting of the expressions to less intuitive axioms and because the restrictions are only partially explicit. The last alternative consists in turning PR-OWL into a lightweight ontology, containing only the class hierarchy and the object and data properties (with its domain and range restrictions). The full validation of the probabilistic model consistency is left to the PR-OWL reasoner. This was the chosen alternative because it results in a simpler ontology, su cient for expressing the MEBN elements in OWL language.
The FOL formulas in PR-OWL 2 RL are evaluated in a di erent way than
they are in the previous versions of PR-OWL. Using materialization, all
implications of an added expression is calculated in load time. In the triplestores
implementations, we do not have posterior reasoning: the queries are solved with
searches on the database, using the SPARQL language, in a similar way to the
SQL language in relational databases. This means that in the knowledge base
we already have for example the hierarchy of an instance explicitly. For
example, if an instance a is of the class A, and A is subclass of B, then, we will also
have both ClassAssertion(A,a) and ClassAssertion(B,a) information on the
base, where the second one was derived from the rule showed below (extracted
from [
IF T(?c1, rdfs:subClassOf, ?c2) AND T(?x, rdf:type, ?c1) THEN T(?x, rdf:type, ?c2)
If we ask if a is instance of class B, the result will be TRUE because we will get the information ClassAssertion(B,a). The advantage of this approach is that queries are very fast. The disadvantage is that complex reasoning cannot be handled, justifying the OWL 2 RL language restrictions.
The BNF grammar below shows the restrictions on the types of context nodes formulas accepted in PR-OWL 2 RL. The evaluation of these context nodes will be handled using the SPARQL language.
Listing 1.1. BNF Grammar for FOL Expressions in PR-OWL 2 RL <atom> : : = ov1 == ov2 j booleanRV ( ov1 , [ , ov2 . . . ] ) j nonBooleanRV ( ov1 , [ , ov2 . . . ] ) = ov0 j ov0 = nonBooleanRV ( ov1 , [ , ov2 . . . ] ) j nonBooleanRV ( ov1 , [ , ov2 . . . ] ) = CONST j
CONST = nonBooleanRV ( ov1 , [ , ov2 . . . ] ) <n e g a t i o n > : : = NOT <atom> <c o n j u n c t i o n >::= <atom> [AND <atom>]+ <d i s j u n c t i o n >::= <atom> [OR <atom>]+ <formula> : : = <atom> j <n e g a t i o n > j
<c o n j u n c t i o n > j <d i s j u n c t i o n >
Table 2 shows how to evaluate these formulas using SPARQL. To solve the EQUAL TO operator between two ordinary variables, we can use the SPARQL FILTER construction, limiting the result of a query where the terms are equal. The evaluation of AND and OR connectives is possible using period and UNION constructions. The negation can be implemented by the PR-OWL 2 reasoner in one of three ways depending on each case: for a not equal expression a FILTER can be used with the operator != (di erent); for a boolean RV it is su cient to ask if it is equal FALSE; and nally, for a not boolean RV, we can use the operator NOT EXISTS inside a FILTER.
To evaluate expressions where we do not know the value of some ordinary variable, we use the SPARQL SELECT construction. If we already know all values, a command ASK is used. This command evaluates the expression and returns TRUE or FALSE. The evaluation of the context nodes is made one by one and the implementation is responsible for keeping the consistency between the ordinary variable values of each node. The following code shows a SELECT to get which procurements ENTERPRISE 1 won (node 5 in Figure 1).
Finally, for the new language to be useful, it is also necessary to propose a new
algorithm for generating a SSBN. The previous SSBN algorithm implemented in
PR-OWL 2 starts from the queries set as well as the ndings set. Since we can
have a large assertive base in PR-OWL 2 RL, making the ndings set very large,
the previous SSBN construction algorithm might be hindered. We plan to extend
the algorithm previously proposed in [
Using the new language proposed, together with a triplestore and the materialization approach, it is possible to solve the scalability problems presented. The BNF grammar proposed is su cient to evaluate all context node formulas used in the Procurement Fraud probabilistic ontology.
The Theorem PR1 [
It is important to note that Costa, the author of PR-OWL, already visualized
the possibility of creating more restrictive versions of the language to guarantee
tractability [
Using a less expressive version of OWL for reasoning in polynomial time, PROWL 2 RL is developed to work with ontologies containing millions of triples. When used together with RDF triplestores, it can solve the scalability problem of the previous PR-OWL versions. Using a commercial database it is possible to work with billions of triples, making it suitable even for working with Big Data. The restrictions on the expressiveness of OWL 2 RL do not allow it to express some complex statements, but it is su cient for a lot of domains, such as the Procurement Fraud, and Linked Open Data projects. This paper presented limitations on the rst-order expressions used in context node formulas, restricting the use of MEBN logic, but allowing at the same time the same constructs which are implemented and allowed in UnBBayes' PR-OWL 2 plug-in.
A future work that is already under way is the implementation of a plug-in
for PR-OWL 2 RL in UnBBayes. In this plug-in we plan to use the triplestore
GraphDB Lite, a free version of GraphDB [