7 papers
Complexity of Clique-Guarded First-Order Logic with Counting
Steffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt
We introduce clique-guarded first-order logic with counting (cgFOC), a fragment of the first-order logic with counting FOC [Kuske and Schweikardt, LICS 2017], and we study the comp…
First-Order Query Evaluation with Cardinality Conditions
Martin Grohe, Nicole Schweikardt
We study an extension of first-order logic that allows to express cardinality conditions in a similar way as SQL's COUNT operator. The corresponding logic FOC(P) was introduced by…
A Rank-Preserving Gaifman Normal Form
Martin Grohe, Nicole Schweikardt
We introduce a rank measure for first-order logic and prove a "rank-preserving'" version of Gaifman's theorem. Compared to earlier "rank-preserving locality theorems'" (in particul…
Color Refinement for Relational Structures
Benjamin Scheidt, Nicole Schweikardt
Color Refinement, also known as Naive Vertex Classification, is a classical method to distinguish graphs by iteratively computing a coloring of their vertices. While it is mainly u…
Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs of Binary Schemas
Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt
We present an index structure, called the color-index, to boost the evaluation of acyclic conjunctive queries (ACQs) over binary schemas. The color-index is based on the color refi…
Structural Indexing of Relational Databases for the Evaluation of Free-Connex Acyclic Conjunctive Queries
Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt
We present an index structure to boost the evaluation of free-connex acyclic conjunctive queries (fc-ACQs) over relational databases. The main ingredient of the index associated wi…