Source author record

Tomasz Gogacz

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

ResearcherUnclaimed source record

Databases Artificial Intelligence Discrete Mathematics math.GR math.LO

Catalog footprint

Research overview

8works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On Finite Entailment of Non-Local Queries in Description Logics

We study the problem of finite entailment of ontology-mediated queries. Going beyond local queries, we allow transitive closure over roles. We focus on ontologies formulated in the description logics ALCOI and ALCOQ, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of unions of conjunctive queries with transitive closure. We also provide a matching lower bound by showing that finite entailment of conjunctive queries with transitive closure in ALC is 2EXPTIME-hard.

preprint2015arXiv

Entropy bounds for conjunctive queries with functional dependencies

We study the problem of finding the worst-case bound for the size of the result $Q(\mathbb{ D})$ of a fixed conjunctive query $Q$ applied to a database $\mathbb{ D}$ satisfying given functional dependencies. We provide a precise characterization of this bound in terms of entropy vectors, and in terms of finite groups. In particular, we show that an upper bound provided by Gottlob, Lee, Valiant and Valiant is tight, answering a question from their paper. Our result generalizes the bound due to Atserias, Grohe and Marx, who consider the case without functional dependencies. Our result shows that the problem of computing the worst-case size bound, in the general case, is closely related to difficult problems from information theory.

preprint2015arXiv

Non-dominating sequences of vectors using only resets and increments

We consider a variant of Dickson lemma, where each entry of a vector can be reseted or incremented by 1 in respect to the previous one. We give an example of non dominating sequence of length $2^{2^{θ(n)}}$ . It perfectly match the previously known upperbound.

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.

preprint2012arXiv

On regular groups and fields

Regular groups and fields are common generalizations of minimal and quasi-minimal groups and fields, so the conjectures that minimal or quasi-minimal fields are algebraically closed have their common generalization to the conjecture that each regular field is algebraically closed. Standard arguments show that a generically stable regular field is algebraically closed. Let $K$ be a regular field which is not generically stable and let $p$ be its global generic type. We observe that if $K$ has a finite extension $L$ of degree $n$ , then $p^{(n)}$ has unbounded orbit under the action of the multiplicative group of $L$ . Known to be true in the minimal context, it remains wide open whether regular, or even quasi-minimal, groups are abelian. We show that if it is not the case, then there is a counter-example with a unique non-trivial conjugacy class, and we notice that a classical group with one non-trivial conjugacy class is not quasi-minimal, because the centralizers of all elements are uncountable. Then we construct a group of cardinality $ω_1$ with only one non-trivial conjugacy class and such that the centralizers of all non-trivial elements are countable.

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.

Tomasz Gogacz

Research overview

Is this your work?

8 publications

On Finite Entailment of Non-Local Queries in Description Logics

Entropy bounds for conjunctive queries with functional dependencies

Non-dominating sequences of vectors using only resets and increments

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

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

On the BDD/FC Conjecture

Termination of oblivious chase is undecidable

On regular groups and fields

See the researcher in context

Building this map preview