Showing cs.DBShow all
3 papers · 1 filter
cs.DB2025
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…
cs.DB2025
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…
cs.DB2025
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…