Tuple relationales Kalkül

Question

Ist sicher Tupel relationales Kalkül eine Turing komplette Sprache?

Answer 1

Lassen Sie uns über die Sicherheit vergessen. Von Codds Theorems , relational Calculus entspricht Logik erster Ordnung. FOL sehr begrenzt ist, kann es nicht die Tatsache ausdrücken, dass es eine Route von einem Punkt A zu Punkt B in einem gewissen Graphen (es die Tatsache ausdrücken kann, dass es eine Route von einem Punkt A zu Punkt B in begrenzten Länge, beispielsweise ∃ x ∃y ∃z ∃t Strecke (a, x) und Strecke (x, y) und Strecke (y, z) und Strecke (z, t) und Strecke (t, b) bedeutet, dass es eine Route der Länge 4).

Siehe deskriptive Komplexität für eine Beschreibung dessen, was die Stärke der verschiedenen Logiken.

Answer 2

Nach Codds Satz , relationale Algebra und relationalen Kalkül sind gleichwertig. Es ist wohlbekannt, dass relationale Algebra ist nicht vollständig Turing, so ist weder relationalen Kalkül.

[Bearbeiten] Sie können zum Beispiel nicht, tun Aggregat (wie Summe, max) oder make rekursive Abfragen in relationalen Algebra / Kalkül. Siehe hier (am Ende) .