Re: ISSUE-3: REPORTED: Lack of anonymous individuals

Hello,

The OWL 1.1 Member Submission does not contain anonymous individuals for the reasons I explain below. These reasons are related to
ISSUE-46: Unnamed Individual Restrictions (http://www.w3.org/2007/OWL/tracker/issues/46). It might make sense to discuss both issues
together.

In short, we did not include the anonymous individuals into the Member Submission because they significantly affect computational
aspects of the logic (explained under item 1 below). Furthermore, anonymous individuals are usually used in practice with a weaker
semantics (explained under item 2 below). Therefore, we did not introduce anonymous individuals in the Member Submission and wanted
to discuss this in the working group.



1. Why can nontree-like "true" anonymous individuals be dangerous?

Nontree-like "true" anonymous individuals in the ABox cause undecidability of ontology entailment, which is the basic inference
problem for OWL. An ABox containing anonymous individuals can actually be understood as a conjunctive query. It is well known that
answering conjunctive queries over SHOIQ TBoxes is undecidable if you allow the query to contain inequalities. Details can be found
in the following paper, but I can give further explanation if needed.

    Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini:
    Conjunctive query containment and answering under description logics constraints,
    ACM Trans. on Computational Logic, 2007. To appear.

Finally, DifferentIndividuals ABox assertions are actually inequalities. To summarize, if you allow nontree-like anonymous
individuals in DifferentIndividuals ABox assertions, you easily get undecidability of the basic reasoning problem.


Even if you were to forbid arbitrary anonymous individuals in the DifferentIndividuals assertions, ontology entailment would still
require answering conjunctive queries over DL TBoxes. Currently, we only know that this problem is decidable for SHIQ; however, it
is not clear whether this is the case for SHOIQ as well.


The bottom line is that nontree-like "true" anonymous individuals are computationally hard, so it might be prudent to avoid them.



2. We could interpret anonymous individuals as Skolem constants

In practice, the semantics of anonymous individuals as true existentially quantified variables is rarely needed. Usually, anonymous
individuals are used just as a convenience, saving the ontology modeler from the trouble of inventing a name for the individual. I
am not aware of any practical system (OWL or RDF) that implements the semantics of anonymous individuals as true existentially
quantified variables.

Therefore, rather than introducing "true" anonymous individuals, we might simply interpret them as Skolem constants. In this case,
we do not need the restriction to tree-like connections, and we could indeed process a larger fragment of RDF data.

Here is a concrete proposal how to reflect this in the specification documents:

- The structural specification would be changed to imbue the Individual class with an "anonymous" flag. This might be useful for the
presentation of an ontology.

- The semantics document would make no special provisions for the anonymous individuals. Thus, individuals with the "anonymous" flag
set would be interpreted as all other individuals.

- The mappings to the XML and RDF syntaxes would be extended to update the "anonymous" flag correctly during parsing.

- The semantics of ontology entailment would not change.

 

Regards,

	Boris

Received on Wednesday, 7 November 2007 19:47:30 UTC