5 papers
Someone slept in my bed! On the entailment problem for conjunctive queries with safe negation over DL-Lite knowledge bases
Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
We solve a long standing open problem, showing that the query answering for conjunctive queries with safe negation, over DL-Lite knowledge bases, is undecidable.
On the entailment problem for DL-Lite ontologies and conjunctive queries with negation
Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
We show that the entailment problem, for a given entailment problem for DL-Lite ontology, and given conjunctive query with inequalities, is undecidable. We also show that…
About the Multi-Head Linear Restricted Chase Termination
Lukas Gerlach, Lucas Larroque, Jerzy Marcinkowski +1
The chase is a ubiquitous algorithm in database theory. However, for existential rules (aka tuple-generating dependencies), its termination is not guaranteed, and even undecidable…
Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories
Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
Query Containment Problem (QCP) is a fundamental decision problem in query processing and optimization. While QCP has for a long time been completely understood for the case of set…
Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability
Jerzy Marcinkowski, Mateusz Orda
Query Containment Problem (QCP) is one of the most fundamental decision problems in database query processing and optimization. Complexity of QCP for conjunctive queries (QCP-CQ) h…