257 citations · 486 across the 35 of their papers we have counts for
3 papers · 1 filter
Extremal Separation Problems for Temporal Instance Queries
Jean Christoph Jung, Vladislav Ryzhikov, Frank Wolter +1
The separation problem for a class Q of database queries is to find a query in Q that distinguishes between a given set of `positive' and `negative' data examples. Separation provi…
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +3
Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and bounded tre…
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +2
We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order…