Difference between revisions of "Open Problems:18"
(Created page with "{{DISPLAYTITLE:Problem 18: Finite Cursor Machines}} {{Infobox |label1 = Proposed by |data1 = Nicole Schweikardt |label2 = Source |data2 = Kanpur 2006...") |
m (updating header) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur06 | |
| − | | | + | |who=Nicole Schweikardt |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
The Finite Cursor Machine (FCM) model is an abstract model for database query processing | The Finite Cursor Machine (FCM) model is an abstract model for database query processing | ||
Latest revision as of 01:42, 7 March 2013
| 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:
- 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)$)
- 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.
