Tuple calcul relationnel

Question

est-tuple sûr calcul relationnel un langage complet turation?

Answer 1

Oublions la sécurité. théorème de Codd , le calcul relationnel est équivalent à la logique de premier ordre. FOL est très limité, il ne peut pas exprimer le fait qu'il y a un itinéraire à partir d'un point A à un point B dans un graphe (il peut exprimer le fait qu'il y a un itinéraire à partir d'un point A à un point B d'une longueur limitée, par exemple ∃ x ∃y ∃z itinéraire ∃t (a, x) et de la voie (x, y) et la voie (y, z) et de la voie (z, t) et de la voie (t, b) signifie qu'il y a un itinéraire de longueur 4).

Voir complexité descriptive pour une description de ce qui est la force des logiques.

Answer 2

Selon Théorème Codd, l'algèbre et le calcul relationnel sont équivalentes. Il est bien connu que l'algèbre relationnelle est pas Turing complet, donc ni est calcul relationnel.

[Modifier] Vous ne pouvez pas, par exemple, effectuer des opérations globales (comme somme, max) ou effectuer des requêtes récursives en algèbre relationnelle / calcul. Voir (à la fin) .