19 citations · 43 across the 11 of their papers we have counts for
Showing 2015 · cs.DBShow all
3 papers · 2 filters
cs.DB2015★ 4 cited
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…
cs.DB2015★ 1 cited
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…
cs.DB2015★ 19 cited
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…