Fitting Horn DL Ontologies to ABox and Query Examples
A research study investigates the adaptation of description logic (DL) ontologies to both positive and negative examples presented as ABoxes along with Boolean queries. It emphasizes Horn DLs, specifically EL and ELI, including their extensions that incorporate the bottom concept. The types of query languages analyzed include atomic queries (AQs), conjunctive queries (rooted CQs), and unions of rooted CQs (UCQs). The study identifies the conditions for the existence of fitting ontologies through simulations, formulates decision-making procedures, and assesses computational complexity. For AQs, the complexity is in PTime for both EL and ELI, while rooted CQs and UCQs are Sigma_P^2-complete for EL and ExpTime-complete for ELI. The addition of the bottom concept does not affect these complexities. Transitioning from expressive DLs ALC and ALCI to Horn DLs presents further technical difficulties.
Key facts
- Study focuses on Horn DLs EL and ELI.
- Extensions with the bottom concept are considered.
- Query languages: AQs, rooted CQs, and rooted UCQs.
- Existence of fitting ontology characterized via simulations.
- Decision procedures developed.
- For AQs, problem in PTime for both EL and ELI.
- For rooted CQs and UCQs, Sigma_P^2-complete for EL.
- For rooted CQs and UCQs, ExpTime-complete for ELI.
- Adding bottom concept does not change complexities.
- Technical challenges arise from moving from ALC/ALCI to EL/ELI.
Entities
—