TLDR: This research paper investigates the problem of ‘fitting’ logical rules (ontologies and constraints) to positive and negative data examples, which are represented as finite relational structures. It analyzes the computational complexity, designs algorithms, and examines the size of these fitting rules for various logical languages, including Description Logics (EL, ELI) and different classes of Tuple-Generating Dependencies (TGDs). Key findings include the existence and complexity of ‘finite bases’ for EL, ELI, and guarded TGDs, while demonstrating that such bases often do not exist for more expressive TGDs. The paper provides detailed complexity bounds and size analyses for fitting problems across these diverse logical formalisms, highlighting both solved challenges and remaining open questions in the field.
In the realm of artificial intelligence and data management, a fundamental challenge involves teaching systems to understand and apply logical rules based on observed data. This is precisely the focus of a recent research paper titled “Fitting Ontologies and Constraints to Relational Structures” by Simon Hosemann, Jean Christoph Jung, Carsten Lutz, and Sebastian Rudolph. The paper delves into the intricate problem of automatically generating logical formulas – specifically ontologies and constraints – that accurately describe a given set of positive and negative data examples, presented as finite relational structures.
Understanding the Core Problem: Fitting Logic to Data
Imagine you have a collection of database instances or knowledge graphs, some of which represent ‘correct’ scenarios (positive examples) and others ‘incorrect’ ones (negative examples). The goal of a ‘fitting problem’ is to derive a logical formula that holds true for all positive examples but is violated by all negative ones. This concept is crucial across several applications. For instance, in data management, it underpins ‘query reverse engineering,’ where the system learns a database query from example instances. In description logics, it’s about learning a concept from labeled data, and in entity comparison, it involves deriving SPARQL queries from knowledge graphs.
The researchers specifically investigate fitting problems for two main types of logical artifacts: ontologies, formulated using description logics or existential rules, and database constraints, expressed as tuple-generating dependencies (TGDs). TGDs, also known as existential rules, come in various forms, including unrestricted, full, guarded, frontier-guarded, frontier-one, and inclusion dependencies. For description logics, the paper focuses on EL and ELI, where ontologies are sets of concept inclusions that can be translated into equivalent TGDs.
Key Findings and Their Implications
The study meticulously pinpoints the exact computational complexity of these fitting problems, designs algorithms for their resolution, and analyzes the size of the resulting fitting ontologies and TGDs. A significant aspect of their work connects the fitting problem to ‘finite basis construction,’ a concept from description logic. A finite basis for a set of positive examples acts as a canonical candidate for a fitting ontology, meaning if any ontology fits the examples, this basis will too. This connection often leads to clear decidability and tight complexity bounds.
Insights on EL and ELI Description Logics
For the description logics EL and ELI (including their extensions with the ‘bottom’ concept), the paper re-establishes the existence of finite bases for EL (a known result) and, for the first time, proves their existence for ELI. While these constructed bases can be of double exponential size, they can be represented much more compactly (single exponential size) using ‘structure sharing.’ The research demonstrates that these size bounds are tight. Consequently, the problem of determining if a fitting EL(I)-ontology exists is decidable in EXPTIME (exponential time), and such ontologies can be constructed in double exponential time (or exponential time with succinct representation).
Insights on Tuple-Generating Dependencies (TGDs)
The findings for TGDs present a more varied picture:
-
Guarded TGDs (GTGDs): Finite bases always exist for GTGDs, and they can be constructed in single exponential time. Fitting GTGD existence and ontology existence are CONEXPTIME-complete, with tight single exponential bounds on the size of fitting GTGDs and ontologies.
-
Inclusion Dependencies (INDs): Finite bases trivially exist. The fitting existence problem for INDs and IND-ontologies is NP-complete, and fitting IND-ontologies can be of polynomial size.
-
Frontier-Guarded, Frontier-One, and Full TGDs: A crucial finding is that finite bases generally do not exist for these more expressive classes of TGDs. Despite this, the researchers provide semantic characterizations that enable algorithms for fitting existence. For frontier-guarded and frontier-one TGDs, fitting ontology and TGD existence are CONEXPTIME-complete. For full TGDs, fitting TGD existence is CONEXPTIME-complete, while fitting ontology existence is in Σp2. The size of fitting TGDs and ontologies for these classes is tightly bounded by single exponential size, except for full TGD ontologies which can be polynomial.
-
Unrestricted TGDs: The existence of finite bases remains an open question. However, the paper establishes complexity upper bounds for fitting ontology existence (CO2NE XPTIME) and fitting TGD existence (CO3NE XPTIME), along with exponential size bounds for fittings.
The paper also discusses related work in areas like schema mapping, inductive logic programming, and concept learning, highlighting how their approach differs by not assuming fixed schemas or additional biases often found in other studies.
Also Read:
- Making Knowledge Graph Rules Understandable with AI
- Refining Knowledge Graph Searches with User-Defined Preferences
Looking Ahead: Open Questions and Future Directions
The research concludes by identifying several intriguing open questions. The exact complexity of fitting TGD and ontology existence for unrestricted TGDs remains to be precisely determined. Furthermore, whether finite bases always exist for unrestricted TGDs is still an open problem, with the authors conjecturing they do not. Characterizing the specific sets of instances that do have finite bases for frontier-guarded, frontier-one, and full TGDs is another area for future exploration. For more in-depth technical details, you can access the full paper here.
