Source author record

Jerzy Marcinkowski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Databases Logic in Computer Science Artificial Intelligence

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Conservative Extensions for Existential Rules

We study the problem to decide, given sets T1,T2 of tuple-generating dependencies (TGDs), also called existential rules, whether T2 is a conservative extension of T1. We consider two natural notions of conservative extension, one pertaining to answers to conjunctive queries over databases and one to homomorphisms between chased databases. Our main results are that these problems are undecidable for linear TGDs, undecidable for guarded TGDs even when T1 is empty, and decidable for frontier-one TGDs.

preprint2015arXiv

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

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

preprint2015arXiv

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

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.

preprint2014arXiv

On the BDD/FC Conjecture

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.

preprint2014arXiv

Termination of oblivious chase is undecidable

We show that all--instances termination of chase is undecidable. More precisely, there is no algorithm deciding, for a given set $\cal T$ consisting of Tuple Generating Dependencies (a.k.a. Datalog $^\exists$ program), whether the $\cal T$ -chase on $D$ will terminate for every finite database instance $D$ . Our method applies to Oblivious Chase, Semi-Oblivious Chase and -- after a slight modification -- also for Standard Chase. This means that we give a (negative) solution to the all--instances termination problem for all version of chase that are usually considered. The arity we need for our undecidability proof is three. We also show that the problem is EXPSPACE-hard for binary signatures, but decidability for this case is left open. Both the proofs -- for ternary and binary signatures -- are easy. Once you know them.

preprint2011arXiv

Prioritized Repairing and Consistent Query Answering in Relational Databases

A consistent query answer in an inconsistent database is an answer obtained in every (minimal) repair. The repairs are obtained by resolving all conflicts in all possible ways. Often, however, the user is able to provide a preference on how conflicts should be resolved. We investigate here the framework of preferred consistent query answers, in which user preferences are used to narrow down the set of repairs to a set of preferred repairs. We axiomatize desirable properties of preferred repairs. We present three different families of preferred repairs and study their mutual relationships. Finally, we investigate the complexity of preferred repairing and computing preferred consistent query answers.

preprint2010arXiv

The Last Paper on the Halpern-Shoham Interval Temporal Logic

The Halpern-Shoham logic is a modal logic of time intervals. Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability of its satisfiability problem. We contribute to this effort by showing - what we believe is quite an unexpected result - that the logic of subintervals, the fragment of the Halpern-Shoham where only the operator "during", or D, is allowed, is undecidable over discrete structures. This is surprising as this logic is decidable over dense orders and its reflexive variant is known to be decidable over discrete structures.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.