177 citations · 621 across the 42 of their papers we have counts for
5 papers · 2 filters
On the non-efficient PAC learnability of conjunctive queries
Balder ten Cate, Maurice Funk, Jean Christoph Jung +1
This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct…
Extremal Fitting Problems for Conjunctive Queries
Balder ten Cate, Victor Dalmau, Maurice Funk +1
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not un…
Ontology-Mediated Querying on Databases of Bounded Cliquewidth
Carsten Lutz, Leif Sabellek, Lukas Schulze
We study the evaluation of ontology-mediated queries (OMQs) on databases of bounded cliquewidth from the viewpoint of parameterized complexity theory. As the ontology language, we…
Efficiently Enumerating Answers to Ontology-Mediated Queries
Carsten Lutz, Marcin Przybyłko
We study the enumeration of answers to ontology-mediated queries (OMQs) where the ontology is a set of guarded TGDs or formulated in the description logic ELI and the query is a co…
Conservative Extensions for Existential Rules
Jean Christoph Jung, Carsten Lutz, Jerzy Marcinkowski
We study the problem to decide, given sets T1,T2 of tuple-generating dependencies (TGDs), also called existential rules, whether T2 is a conservative extension of T1. We consider t…