Open Problems:18

Suggested by	Nicole Schweikardt
Source	Kanpur 2006
Short link	https://sublinear.info/18

The Finite Cursor Machine (FCM) model is an abstract model for database query processing based on abstract state machines [GroheGLSTV-07]. This model has the following fixed structure:

1. A background structure ${\mathcal U}$ that consists of an infinite set $U$ of potential database entries, and some functions and predicates on $U$ (e.g., ${\mathcal U} = (\mathbb N, {\le}, +, \times)$)
2. A database schema $\sigma$ that consists of a finite number of relation symbols $R_1, \ldots, R_t$ of arities $r_1, \ldots, r_t$.

The input of a problem in this model is a database $D$ of schema $\sigma$ where $D$ is a collection of $t$ tables $R^D_1, \ldots, R^D_t$ and each table $R^D_i$ is a list of elements from $U^{r_i}$. On every input table, the FCM has a fixed number of cursors which can only move from top to bottom. Apart from this, the FCM also has an internal memory consisting of a constant number of “modes” (comparable to the states of a Turing machine) and a register for storing up to $o(n)$ many bits where $n$ is the total number of tuples in $D$.

Is there a Boolean query from Relational Algebra (or, equivalently, a sentence of first-order logic) that cannot be computed by any composition of FCMs and sorting operations? We conjecture that there is no such Boolean query.