Über Codds Reduktionsalgorithmus

Der Algorithmus von Codd konvertiert einen Ausdruck in Tupelrelationsrechnung in relationale Algebra.

1. Gibt es eine Standardimplementierung des Algorithmus?
2. Wird dieser Algorithmus irgendwo verwendet? (Es scheint, dass die Branche nur SQL und Varianten benötigt. Ich bin mir nicht sicher, was Datenbanktheoretiker im akademischen Bereich betrifft.)
3. Was ist die Komplexität der Reduktion?

_{Dies wurde vor über einem Jahr auf SO gepostet , erhielt aber keine gute Antwort.}

Diese Reduktion ist die konstruktive Beweismethode, um zu zeigen, dass eine Teilmenge (mit dem Namen safe) Tuple Relational Calculus (TRC) weniger aussagekräftig ist als Relational Algebra (RA). Auch umgekehrt haben Safe-TRC und RA die gleiche Aussagekraft. Siehe zum Beispiel Satz 5.3.10 . Die syntaktische "Sicherheits" -Einschränkung stellt die domänenunabhängige Eigenschaft des Kalküls sicher und wird benötigt.

In R-DBMS kann SQL als die konkrete (deklarative) Sprache für TRC angesehen werden. Das RA-Gegenstück ist der Prozedurplan (eine Abfolge von Operationen), in dem ein SQL-Ausdruck kompiliert wird. Die Konvertierung ist also eigentlich die formale Beschreibung des Kompilierungsprozesses. Beachten Sie, dass SQL Erweiterungen wie DISTINCT, ORDER BY, GROUP BY einführt, die eindeutig außerhalb des Geltungsbereichs der TRC- und RA-Theorie liegen.

Ich kenne die genaue theoretische Komplexität der Konvertierung nicht, aber es muss eindeutig "billig" sein. Photonenkolaitis gibt an, dass es linear ist.

Mir ist keine Proof-of-Concept-Implementierung dieses Algorithmus bekannt.