19 citations · 43 across the 11 of their papers we have counts for
4 papers · 1 filter
Entropy bounds for conjunctive queries with functional dependencies
Tomasz Gogacz, Szymon Toruńczyk
We study the problem of finding the worst-case bound for the size of the result of a fixed conjunctive query applied to a database satisfying giv…
Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable
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 th…
Non-dominating sequences of vectors using only resets and increments
Wojciech Czerwinski, Tomasz Gogacz, Eryk Kopczynski
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 sequenc…
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 undecida…