TLDR: This research paper investigates the problem of automatically generating or refining ontologies based on positive and negative examples of ABox (database) and Boolean query pairs. It determines the computational complexity of this ‘ontology fitting’ problem for various description logics (ALC, ALCI) and query languages (AQs, CQs, UCQs, Full CQs). The study finds that fitting for Atomic and Full Conjunctive Queries is CONP-complete, while for general Conjunctive Queries and Unions of Conjunctive Queries, it is significantly harder, being 2EXPTIME-complete. The findings offer insights into automating parts of ontology construction and engineering.
Researchers Maurice Funk, Marvin Grosser, and Carsten Lutz from Leipzig University and ScaDS.AI Center Dresden/Leipzig have tackled a fundamental problem in artificial intelligence and computer science: fitting formal objects to given examples. Their new research, titled “Fitting Description Logic Ontologies to ABox and Query Examples,” explores how to automatically generate or refine ontologies based on a set of positive and negative data examples and queries.
In many fields, from inductive program synthesis to machine learning and database research, the goal is often to find a model or program that aligns with observed behaviors or data. This paper applies a similar principle to ontologies, which are formal representations of knowledge within a specific domain. Ontologies are crucial in areas like ontology-mediated querying, where they enrich data with domain knowledge to provide more complete answers and bridge different data representations.
The core problem studied by the researchers is this: given a collection of examples, each consisting of an ABox (essentially a database) and a Boolean query, can we find an ontology that satisfies the query for all positive examples and does not satisfy it for all negative examples? This means the ontology should make the positive cases true and the negative cases false when combined with the database.
The team focused on two expressive yet foundational description logics (DLs) for their ontology languages: ALC and ALCI. These logics provide the formal framework for defining concepts and relationships within an ontology. For the queries, they considered several types: atomic queries (AQs), conjunctive queries (CQs), full CQs (CQs without existential variables), and unions of conjunctive queries (UCQs).
Understanding the Complexity of Ontology Fitting
A significant part of the research involved determining the computational complexity of deciding whether such a fitting ontology exists for various combinations of ontology and query languages. The results show a clear spectrum of difficulty:
- For consistency-based fitting (where examples are just ABoxes, and the goal is consistency or inconsistency with the ontology) and for atomic queries (AQs), the problem is CONP-complete. This means it’s computationally challenging but falls within a class of problems that are considered relatively tractable compared to some other complex problems in logic.
- Full conjunctive queries (Full CQs) also fall into the CONP-complete category, indicating a similar level of complexity to AQs.
- However, when it comes to general conjunctive queries (CQs) and unions of conjunctive queries (UCQs), the complexity significantly increases. These problems are 2EXPTIME-complete. This higher complexity arises because CQs and UCQs can contain existentially quantified variables, which, when combined with positive examples, act like existential rules. This can lead to the need for potentially infinite interpretations (models) to satisfy the conditions, making the problem much harder to solve. Interestingly, for ALCI, this complexity matches that of query entailment, but for ALC, the fitting problem is even harder than its associated entailment problems.
Also Read:
- Bridging the Gap: Validating Data with SHACL and OWL Ontologies
- A New Approach to Learning Logical Rules with Minimum Message Length
Implications and Future Directions
The algorithms developed by the researchers to prove their upper bounds are capable of producing explicit fitting ontologies, which is a practical outcome. This work has direct applications in assisting with ontology construction and engineering. Instead of building an entire ontology from scratch, this approach could help construct smaller, specific portions of an ontology from examples, supporting a more incremental development process by human engineers.
The paper also discusses related work, distinguishing their approach from others that fit DL concepts or use interpretations as examples. They highlight that their focus on ABox and query examples is particularly motivated by ontology-mediated querying applications where an ontology might be designed to support specific queries rather than provide a comprehensive domain representation.
Looking ahead, the researchers suggest that their results could be adapted to cover many common extensions of ALC and ALCI. They also propose exploring other ontology languages, such as Horn DLs or existential rules, and variations in the framework, like providing a signature for the fitting ontology or defining stronger semantics for negative examples. This research provides a robust foundation for understanding and automating the process of fitting ontologies to real-world data and query patterns. You can read the full paper at arXiv.org.
