Jerzy Marcinkowski

University of Wrocław

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Tomasz Gogacz

University of Warsaw

Jan Chomicki

University at Buffalo, State University of New York

Piotr Ostropolski-Nalewaja

University of Wrocław

Andréas Pieris

University of Cyprus

Sławek Staworko

Université de Lille

Jakub Michaliszyn

University of Wrocław

Grzegorz Głuch

École Polytechnique Fédérale de Lausanne

Leszek Pacholski

Poznań University of Technology

Daniel Kirsten

UC Irvine Health

Cristian Molinaro

University of Calabria

Cooperative Institutions

University of Wrocław

Institute of Computer Science

Czech Academy of Sciences, Institute of Computer Science

Polish Academy of Sciences

TU Dresden

Centre National de la Recherche Scientifique

Institute of Mathematics

Institut national de recherche en informatique et en automatique

University of Warsaw

Laboratoire Bordelais de Recherche en Informatique

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

On the BDD/FC Conjecture

arXiv (Cornell University) (2014)

Tomasz Gogacz Jerzy Marcinkowski

Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog +/- programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.

10.48550/arxiv.1408.2081

Cite

Citations (0)

On the Computational Complexity of Minimal-Change Integrity Maintenance in Relational Databases

Lecture notes in computer science (2005)

Jan Chomicki Jerzy Marcinkowski

Data integrity

10.1007/978-3-540-30597-2_5

Cite

Citations (60)

Can One Escape Red Chains? Regular Path Queries Determinacy is Undecidable

arXiv (Cornell University) (2018)

Grzegorz Głuch Jerzy Marcinkowski Piotr Ostropolski-Nalewaja

For a given set of queries (which are expressions in some query language) $\mathcal{Q}=\{Q_1$, $Q_2, \ldots Q_k\}$ and for another query $Q_0$ we say that $\mathcal{Q}$ determines $Q_0$ if -- informally speaking -- for every database $\mathbb D$, the information contained in the views $\mathcal{Q}({\mathbb D})$ is sufficient to compute $Q_0({\mathbb D})$. Query Determinacy Problem is the problem of deciding, for given $\mathcal{Q}$ and $Q_0$, whether $\mathcal{Q}$ determines $Q_0$. Many versions of this problem, for different query languages, were studied in database theory. In this paper we solve a problem stated in [CGLV02] and show that Query Determinacy Problem is undecidable for the Regular Path Queries -- the paradigmatic query language of graph databases.

Determinacy

Undecidable problem

10.48550/arxiv.1802.01554

Cite

Citations (1)

Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable

arXiv (Cornell University) (2015)

Tomasz Gogacz Jerzy Marcinkowski

We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of our Red Spider method which we developed in our paper [GM15] to show undecidability of the same problem in the unrestricted case -- when database instances are allowed to be infinite. We also show a specific instance $Q_0$, ${\cal Q}= \{Q_1, Q_2, \ldots Q_k\}$ such that the set $\cal Q$ of CQs does not determine CQ $Q_0$ but finitely determines it. Finally, we claim that while $Q_0$ is finitely determined by $\cal Q$, there is no FO-rewriting of $Q_0$, with respect to $\cal Q$, and we outline a proof of this claim

Undecidable problem

Determinacy

Conjunctive query

Finite set

Source

Cite

Citations (0)

Disjunctive Databases for Representing Repairs

arXiv (Cornell University) (2008)

Cristian Molinaro Jan Chomicki Jerzy Marcinkowski

This paper addresses the problem of representing the set of repairs of a possibly inconsistent database by means of a disjunctive database. Specifically, the class of denial constraints is considered. We show that, given a database and a set of denial constraints, there exists a (unique) disjunctive database, called canonical, which represents the repairs of the database w.r.t. the constraints and is contained in any other disjunctive database with the same set of minimal models. We propose an algorithm for computing the canonical disjunctive database. Finally, we study the size of the canonical disjunctive database in the presence of functional dependencies for both repairs and cardinality-based repairs.

Cardinality (data modeling)

10.48550/arxiv.0811.2117

Cite

Citations (0)

Modulo Constraints and the Complexity of Typechecking XML Views

Theory of Computing Systems (2008)

Jerzy Marcinkowski Piotr Wieczorek

Conjunctive query

Negation

Natural number

10.1007/s00224-008-9132-z

Cite

Citations (0)

Optimal Complexity Bounds for Positive LTL Games

Lecture notes in computer science (2002)

Jerzy Marcinkowski Tomasz Truderung

EXPTIME

10.1007/3-540-45793-3_18

Cite

Citations (10)

The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable

Tomasz Gogacz Jerzy Marcinkowski

We solve a well known, long-standing open problem in relational databases theory, showing that the conjunctive query determinacy problem (in its "unrestricted" version) is undecidable.

Undecidable problem

Conjunctive query

Determinacy

Boolean conjunctive query

10.1109/lics.2015.35

Cite

Citations (21)

Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.

Proceedings of the ACM on Management of Data (2024)

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 has been fully understood since 1970s. But, as Chaudhuri and Vardi noticed in their classical 1993 paper this understanding is based on the assumption that query answers are sets of tuples, and it does not transfer to the situation when multi-set (bag) semantics is considered. Now, 30 years later, decidability of QCP for bag semantics remains an open question, one of the most intriguing open questions in database theory. In this paper we show a series of undecidability results for some generalizations of this problem. We show, for example, that the problem whether, for given two boolean conjunctive queries φ s and φ b , and a linear function F, the inequality F(φ s (D)) =< φ b (D) holds for each database instance D, is undecidable.

Conjunctive query

Containment (computer programming)

Boolean conjunctive query

10.1145/3651604

Cite

Citations (0)

On a Semantic Subsumption Test

Lecture notes in computer science (2005)

Jerzy Marcinkowski Jan Otop Grzegorz Stelmaszek

Gas meter prover

Automated reasoning

10.1007/978-3-540-32275-7_10

Cite

Citations (1)