Open Problems:18 - Revision history

Krzysztof Onak: updating header

2013-03-07T01:42:07Z

updating header

Krzysztof Onak at 05:12, 16 November 2012

2012-11-16T05:12:06Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 18: Finite Cursor Machines}} {{Infobox |label1 = Proposed by |data1 = Nicole Schweikardt |label2 = Source |data2 = Kanpur 2006..."

2012-10-16T15:09:46Z

Created page with "{{DISPLAYTITLE:Problem 18: Finite Cursor Machines}} {{Infobox |label1 = Proposed by |data1 = Nicole Schweikardt |label2 = Source |data2 = Kanpur 2006..."

New page

{{DISPLAYTITLE:Problem 18: Finite Cursor Machines}}
{{Infobox
|label1 = Proposed by
|data1 = Nicole Schweikardt
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/18
}}
The Finite Cursor Machine (FCM) model is an abstract model for database query processing
based on abstract state machines {{cite|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.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Nicole Schweikardt

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 18: Finite Cursor Machines}}
+{{Header
-{{Infobox
+|title=Finite Cursor Machines
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Nicole Schweikardt
+|who=Nicole Schweikardt
 }}
 The Finite Cursor Machine (FCM) model is an abstract model for database query processing

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)