8 papers
Property Testing for Recursive Query Languages
Isolde Adler, Carsten Lutz, Quentin Manière +2
In the context of database querying, property testing provides a framework for testing query answers with high confidence while inspecting only a sublinear part of the database, th…
A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL
David Carral, Calixte Gruson, Quentin Manière
The emergence of the ISO standard GQL introduces a powerful query language extending first-order logic with controlled recursion, raising the question of its applicability to evalu…
Will My Favorite Chases Terminate if Evaluating Conjunctive Queries Does? One Does Not Simply Decide This
Lucas Larroque, Quentin Manière
Existential rules are a prominent formalism to enrich a database with knowledge from the domain of interest, but make even basic reasoning tasks on the resulting knowledge base und…
Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics
Meghyn Bienvenu, Quentin Manière
In this paper, we study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell,…
Minimal Model Reasoning in Description Logics: Don't Try This at Home!
Federica Di Stefano, Quentin Manière, Magdalena Ortiz +1
Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description…
Spectra of Cardinality Queries over Description Logic Knowledge Bases
Quentin Manière, Marcin Przybyłko
Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or…
Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
Carsten Lutz, Quentin Manière
We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO, its extension C with counting q…
Querying Circumscribed Description Logic Knowledge Bases
Carsten Lutz, Quentin Manière, Robin Nolte
Circumscription is one of the main approaches for defining non-monotonic description logics (DLs). While the decidability and complexity of traditional reasoning tasks such as sati…