Computing complex class expressions that subsume a given atomic concept

[Daria Stepanova]

Dear developers and forum users,

Task definition:
Here is the task that I want to tackle by exploiting the ELK reasoner:
Given an EL ontology O and an atomic concept Q I want to get all (or some that satisfy a certain criteria) complex expressions that subsume Q.

For example, suppose we are given an EL ontology O with the following TBox:

1. (A and B) \sqsubseteq (C and \exists R.D)
2. (C and \exists R.D) \sqsubseteq E
3. E \sqsubseteq Q

Let Q be an atomic concept that we are interested in.
The result that should be returned is:
a) A and B;
b) C and \existsR.D;
c) E;
d) Q.

Ideal target solution:
Finding all complex expressions might not be possible in the general case (especially in presence of cycles).
Thus, weneed to introduce some restriction criteria. Ideally given O, Q and a criteria C, the reasoner should return the set of complex expressions that subsume Q and satisfy the criteria C and also a boolean flag that says whether the computed result is complete or not.
As a criteria one can use the size k of maximal complex expression that should be returned or time bound t, after which the computation should be stopped.

Solution found so far:
One of the possible solutions of the above problem can be probably found by exploring the task "Querying complex class expressions".
Namely, we might introduce atomic concepts for each complex expression that occurs in the TBox and add respective equivalence axioms.
In this case we have the size of the complex expression as a criteria and implicitly set the parameter k to the maximal size of complex expressions occurring in O. Then we can ask for all subconcepts of Q using

reasoner.getSubClasses("Q", false);

and get some result.

Questions:
The result that one obtains using the "Solution found so far" might be incomplete.
First it might be that there are some complex expressions that are or size bigger then k.
Second there might be some other complex expressions that are of size k but were not returned in the result.

1. Is there a way of checking the completeness of the result?
2. Are there other ways of solving the described task?

Sorry, if this topic is a repetition of some earlier discussion in this forum, I am new to the reasoner and might have missed the relevant answers when looking
for them.

Thanks a lot
Kind regards
Dasha

[Yevgeny Kazakov]

Hi Dasha,

I am afraid that the only solution is to enumerate all concepts that
you are interested in and test them one by one or at once. ELK will
not consider any concept unless you tell it explicitly (either in a
form of an axiom or using a query). Note that in the current version
of ELK you can query complex classes directly -- no need to introduce
new atomic classes.

You can try to reduce the number of tests by figuring out which
concepts should definitely *not* be returned as an answer and testing
for the remaining concepts only. E.g., if you have tested that (A and
B) is not subsumed by Q, there is no need to test A or B. You can take
a look if extracting a "top module" for Q can help you in filtering
out irrelevant concepts (google for "locality-based modules").

Maybe in your specific application, you can reduce the number of tests
based on an addition knowledge. What do you need it for?

Best regards,

Yevgeny

> --
> You received this message because you are subscribed to the Google Groups
> "elk-reasoner-discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to elk-reasoner-disc...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Daria Stepanova]

Dear Yevgeny,

Thanks a lot for your quick reply.

On Tuesday, April 1, 2014 5:17:53 PM UTC+2, Yevgeny Kazakov wrote:

Hi Dasha,

I am afraid that the only solution is to enumerate all concepts that
you are interested in and test them one by one or at once.

The concept subsumptions are needed in order to identify the forms of ABox assertions that are sufficient for the target concept to be derived.
In the above example, given (A and B) in the output, we know that for any constant t if A(t) and B(t) are present in the ABox, then Q(t) is ensured to be entailed, i.e. A and B "support" Q. If all possible complex expressions are returned in the result then we have all forms of "support sets" for Q at hand. Instance query answering in this case amounts to a simple check.

Now suppose that we know which concept and role names might occur in the ABox. They form our search space for "support sets".
If I understood it correctly, your suggestion when applied to the described scenario, amounts to construction of all possible complex expressions that can be formed from the elements of the search space. If no restriction on the form of complex expressions that we are interested in is applied, then the initial search space might be huge.
 

ELK will
not consider any concept unless you tell it explicitly (either in a
form of an axiom or using a query). Note that in the current version
of ELK you can query complex classes directly -- no need to introduce
new atomic classes.

You can try to reduce the number of tests by figuring out which
concepts should definitely *not* be returned as an answer and testing
for the remaining concepts only. E.g., if you have tested that (A and
B) is not subsumed by Q, there is no need to test A or B. You can take
a look if extracting a "top module" for Q can help you in filtering
out irrelevant concepts (google for "locality-based modules").

Exploiting the learning techniques as you suggest, might improve the situation. That you for the hint on "locality-based modules", I will look at it.
It would be certainly interesting to know whether we reach the point when the constructed set of "support sets" is complete, but as you wrote, it seems to be impossible given the current implementation.

Maybe in your specific application, you can reduce the number of tests
based on an addition knowledge. What do you need it for?

The application that I am working on is related to DL-program (Description Logic programs) which combine ontologies and rules via special DL-atoms, allowing for bidirectional information flow between rules and ontology. These atoms query ontology and send the result back to the rules, moreover prior to querying the ontology, the latter can be updated by information deduced from the rules. I am interested in computing the forms of ABox assertions that when present in the  update or ontology ABox, ensure the DL-atom to evaluate to true, i.e. guarantee its query to be entailed.
Without "support sets" ontology needs to be queried multiple times, which results in possible computation delays.
The complete set of mentioned "support sets" allows to completely avoid querying ontology.

Hence not much can be known about the forms of complex expressions that subsume the target query Q before their computation is started (just the candidate search space as mentioned above).

Kind regards
Dasha

 

> email to elk-reasoner-discussion+unsub...@googlegroups.com.