Project Details
Projekt
Fitting Ontologies and Queries to Labeled Data Examples
Subject Area
Theoretical Computer Science
Term
since 2025
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 555349010
This project aims to deepen our understanding of the following fundamental problem: given a set of labeled data examples, find a logical expression that fits them. Here, an expression phi(x) fits a positive example (D,a,+), which consists of a database D and a distinguished tuple a of indivuduals from D, if phi(a) is satisfied in D, and a negative example (D,a,-) if phi(a) is not satified in D. Such fitting problems have a long history in several subareas of computer science. For example, in databases, they are at the core of the classical query-by-example paradigm; in machine learning the fitting existence problem goes under the name consistency problem; and in knowledge representation and reasoning, fitting logical expressions are used as referring expressions (expressions uniquely defining some individual) or as user support in writing concepts and ontologies. In the proposed project, we will advance the knowledge about fitting problems and algorithms, focusing mainly on queries and ontologies as logical expressions. More precisely, our main objectives are as follows. (A) We will study practically relevant settings that have received little attention so far such as (a core of) the recently standardized graph query languages SQL/PGQ and GQL, as well as ontologies formulated in description logics and existential rules. (B) We will give transparent model-theoretic characterizations for the existence of a query or ontology that fits a given set of examples, and based on that determine the computational complexity of the existence problem and develop algorithms for constructing a fitting. (C) We will go beyond the pure fitting existence problem and study variations thereof such as size-bounded and smallest fittings (where we additionally restrict the size of the sought expression), extremal fittings (where we additionally require that it is a/the logically strongest or weakest fitting), and Angluin style exact learning (where we allow additional questions to an oracle to facilitate construction of the fitting).
DFG Programme
Research Grants
