Completeness of Relational Algebra via Cylindric Algebra

Título: Completude da Álgebra Relacional via Álgebra Cilíndrica

Autor: Jan Laštovička (Universidade Palacký, Olomouc, República Tcheca)

1. Problema e Motivação

O artigo aborda o problema fundamental da completude da álgebra relacional em relação às fórmulas da lógica de primeira ordem (LPO).

• Contexto: A álgebra relacional é uma linguagem procedural usada em bancos de dados, enquanto a LPO é uma linguagem declarativa. Embora toda expressão da álgebra relacional possa ser traduzida para LPO, o inverso não é verdadeiro para todas as fórmulas (ex: negações de fórmulas relacionais puras podem não ter equivalente relacional).
• Restrição: O foco recai sobre as fórmulas permitidas (allowed formulas), uma subclasse de fórmulas da LPO que possuem a propriedade de serem semanticamente equivalentes a expressões da álgebra relacional.
• Limitação das Abordagens Anteriores: A prova de completude existente (VGT91) é complexa e não se generaliza facilmente para modelos de dados que lidam com informações incompletas ou vagas.
• Objetivo: Apresentar uma prova alternativa de completude baseada na álgebra cilíndrica, que é mais algébrica e passível de generalização para modelos de dados avançados. Além disso, o autor propõe um algoritmo alternativo para converter fórmulas permitidas em expressões relacionais.

2. Metodologia

A abordagem do autor baseia-se na incorporação (embedding) da álgebra relacional dentro da estrutura de álgebra cilíndrica, introduzida por Tarski para a algebraização da lógica de primeira ordem.

• Fundamentos Teóricos:
  • Define-se a sintaxe e semântica da LPO e da álgebra relacional sobre domínios finitos.
  • Utiliza-se a correspondência entre relações e conjuntos de valorações (funções que atribuem valores às variáveis).
  • A semântica das fórmulas é mapeada para operações em uma álgebra cilíndrica de dimensão $X$ (conjunto de variáveis), onde:
    • Conjunção ($\land$) corresponde à interseção ($\cap$).
    • Disjunção ($\lor$) corresponde à união ($\cup$).
    • Quantificador existencial ($\exists x$) corresponde à cilindrificação ($C_x$).
    • Igualdade ($x \approx y$) corresponde à diagonal ($D_{xy}$).
• Conceitos Chave Definidos:
  • Fórmulas Permitidas: Definidas estruturalmente, garantindo que as variáveis livres de uma fórmula sejam geradas pelas variáveis dos predicados atômicos e que os quantificadores existenciais respeitem certas condições de dependência.
  • Normalização: O autor introduz um processo de transformação de uma fórmula permitida em uma fórmula normalizada.
  • Geradores e Cogeneradores: São fórmulas auxiliares ($gen(\phi)$ e $cogen(\phi)$) derivadas da estrutura da fórmula original. Eles restringem o domínio de valores da fórmula, garantindo que a equivalência semântica seja mantida dentro do "espaço" relevante (domínio ativo).
  • Algoritmo de Conversão: O processo ocorre em duas etapas:
    1. Transformação da fórmula permitida em uma fórmula normalizada (usando os geradores/cogeneradores).
    2. Tradução direta da fórmula normalizada para uma expressão da álgebra relacional (usando regras de mapeamento para união, diferença, projeção, seleção, etc.).

3. Principais Contribuições

1. Nova Prova de Completude: O autor fornece uma prova alternativa do teorema de completude, demonstrando que toda fórmula permitida é semanticamente equivalente a uma expressão da álgebra relacional. A prova é conduzida inteiramente dentro do contexto da álgebra cilíndrica, o que simplifica a lógica ao tratar a negação como um conectivo lógico completo e permitir o uso direto da igualdade.
2. Algoritmo de Normalização: Desenvolvimento de um algoritmo sistemático para converter fórmulas permitidas em fórmulas normalizadas. Este algoritmo preserva a estrutura da fórmula de entrada de maneira mais clara do que abordagens anteriores.
3. Generalização Potencial: A principal vantagem metodológica é que, ao basear-se na álgebra cilíndrica, a prova e os algoritmos podem ser adaptados para modelos relacionais generalizados, como aqueles que lidam com informações incompletas (nulls) ou valores vagos (fuzzy), onde as álgebras cilíndricas podem ser estendidas para acomodar essas semânticas.
4. Tratamento da Igualdade: Diferente de algumas abordagens anteriores que exigiam a eliminação da igualdade antes do processamento, este método permite o uso direto de igualdade nas fórmulas.

4. Resultados

• Teorema 6.8: Estabelece que toda fórmula permitida é semanticamente equivalente à sua normalização.
• Teorema 6.9: Demonstra que as fórmulas permitidas são independentes do domínio (domain independent), uma propriedade crucial para a execução eficiente em bancos de dados, pois o resultado da consulta não depende do tamanho do domínio não ativo.
• Correspondência Algébrica: O artigo valida que a tradução de fórmulas normalizadas para expressões da álgebra relacional (via funções como $expr(\phi)$) preserva a semântica, confirmando a completude.
• Exemplo Prático: O artigo ilustra o processo com a "divisão relacional", mostrando como uma fórmula complexa de LPO é normalizada e convertida na expressão relacional padrão de divisão.

5. Significado e Impacto

Este trabalho é significativo por oferecer uma ponte mais robusta e algébrica entre a lógica de primeira ordem e a álgebra relacional.

• Para a Teoria de Bancos de Dados: Refina a compreensão teórica sobre quais consultas declarativas podem ser executadas eficientemente como consultas procedurais.
• Para a Pesquisa Futura: A maior contribuição é a viabilidade de generalização. Ao provar a completude via álgebra cilíndrica, o autor abre caminho para aplicar técnicas semelhantes a modelos de dados que fogem do modelo relacional clássico (ex: bancos de dados com incerteza, dados fuzzy ou incompletos), onde as provas tradicionais baseadas em indução estrutural direta sobre fórmulas lógicas seriam muito mais difíceis ou impossíveis de adaptar.
• Implementação: O algoritmo de normalização proposto pode ser utilizado como base para otimizadores de consultas em sistemas de gerenciamento de banco de dados (SGBDs), permitindo a tradução de subconjuntos declarativos complexos para planos de execução físicos.

Em resumo, o artigo não apenas reconfirma um resultado clássico (a completude da álgebra relacional para fórmulas permitidas), mas o faz através de uma lente algébrica (álgebra cilíndrica) que promete ser mais flexível e adaptável aos desafios modernos de modelagem de dados.