6 citations · 9 across the 6 of their papers we have counts for
7 papers
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
Christoph Berkholz, Nicole Schweikardt
Marx (STOC~2010, J.~ACM 2013) introduced the notion of submodular width of a conjunctive query (CQ) and showed that for any class of Boolean CQs of bounded submodular width, th…
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
Nofar Carmeli, Shai Zeevi, Christoph Berkholz +2
As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tr…
Answering UCQs under updates and in the presence of integrity constraints
Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
We investigate the query evaluation problem for fixed queries over fully dynamic databases where tuples can be inserted or deleted. The task is to design a dynamic data structure t…
Answering FO+MOD queries under updates on bounded degree databases
Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
We investigate the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that…
Answering Conjunctive Queries under Updates
Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
We consider the task of enumerating and counting answers to -ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit…
Limitations of Algebraic Approaches to Graph Isomorphism Testing
Christoph Berkholz, Martin Grohe
We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Gröbner basis computation. The idea of these algorithms is to encode two graph…