2 citations · 3 across the 9 of their papers we have counts for
10 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…
Monotone Rewritability and the Analysis of Queries, Views, and Rules
Michael Benedikt, Stanislav Kikot, Johannes Marti +1
We study the interaction of views, queries, and background knowledge in the form of existential rules. The motivating questions concern monotonic determinacy of a query using views…
Determinacy of Real Conjunctive Queries. The Boolean Case
Jarosław Kwiecień, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
In their classical 1993 paper [CV93] Chaudhuri and Vardi notice that some fundamental database theory results and techniques fail to survive when we try to see query answers as bag…
A Journey to the Frontiers of Query Rewritability
Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral +1
This paper is about (first order) query rewritability in the context of theory-mediated query answering. The starting point of our journey is the FUS/FES conjecture, saying that if…
On monotonic determinacy and rewritability for recursive queries and views
Michael Benedikt, Stanislav Kikot, Piotr Ostropolski-Nalewaja +1
A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, mono…
The First Order Truth behind Undecidability of Regular Path Queries Determinacy
Grzegorz Głuch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
In our paper [Głuch, Marcinkowski, Ostropolski-Nalewaja, LICS ACM, 2018] we have solved an old problem stated in [Calvanese, De Giacomo, Lenzerini, Vardi, SPDS ACM, 2000] showing t…
Can One Escape Red Chains? Regular Path Queries Determinacy is Undecidable
Grzegorz Głuch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
For a given set of queries (which are expressions in some query language) , and for another query we say that determines…