O algorytmie redukcji Codda

Algorytm Codda konwertuje wyrażenie w krotkowym rachunku relacyjnym na relacyjną algebrę.

1. Czy istnieje standardowa implementacja algorytmu?
2. Czy ten algorytm jest używany gdziekolwiek? (Wydaje się, że branża potrzebuje tylko SQL i wariantów, nie jestem pewien co do teoretyków baz danych w środowisku akademickim).
3. Jaka jest złożoność redukcji?

_{Zostało to opublikowane w SO ponad rok temu, ale nie otrzymało dobrej odpowiedzi.}

Ta redukcja jest konstruktywną techniką dowodową pokazującą, że podzbiór (zwany bezpiecznym) Tuple Relational Calculus (TRC) jest mniej ekspresyjny niż Relational Algebra (RA). Z drugiej strony jest to prawda, Safe-TRC i RA mają równoważną moc ekspresyjną. Patrz na przykład Twierdzenie 5.3.10 . Składniowe ograniczenie „bezpieczeństwa” zapewnia niezależną od domeny właściwość rachunku różniczkowego i jest potrzebne.

W R-DBMS SQL może być postrzegany jako konkretny (deklaratywny) język dla TRC. Odpowiednikiem RA jest plan proceduralny (sekwencja operacji), w którym kompilowane jest wyrażenie SQL. Konwersja jest więc formalnym opisem procesu kompilacji. Zauważ, że SQL wprowadza rozszerzenia takie jak DISTINCT, ORDER BY, GROUP BY, które są wyraźnie poza zakresem teorii TRC i RA.

Nie znam dokładnej teoretycznej złożoności konwersji, ale najwyraźniej musi to być „tanie”. Photon Kolaitis twierdzi, że jest liniowy.

Nie jestem świadomy implementacji tego algorytmu na zasadzie proof-of-concept.