Tupla

Question

è sicuro tupla un linguaggio completo Turing?

Answer 1

Lasciamo perdere la sicurezza. di Codd teorema , calcolo relazionale è equivalente alla logica del primo ordine. FOL è molto limitata, non può esprimere il fatto che c'è un percorso da un punto A al punto B in qualche grafico (può esprimere il fatto che c'è un percorso da un punto A al punto B in lunghezza limitata, ad esempio ∃ x ∃y ∃z ∃t rotta (a, x) e rotta (x, y) e rotta (y, z) e rotta (z, t) e rotta (t, b) significa che c'è un percorso di lunghezza 4).

Vedere descrittivo complessità per una descrizione di ciò è la forza di logiche diverse.

Answer 2

di Codd Teorema , algebra relazionale e calcolo relazionale sono equivalenti. E 'ben noto che l'algebra relazionale non è Turing completa, così non è calcolo relazionale.

[Edit] Non si può, per esempio, fare operazioni di aggregazione (come sum, max) o fare query ricorsive in relazionale algebra / calcolo. Vedere qui (verso la fine) .