Resumo Técnico: Resposta de Consultas Orientada a Objetivos sobre Dependências de Primeira e Segunda Ordem com Igualdade

1. Declaração do Problema

Dependências em bancos de dados são usadas para expressar restrições de integridade, lidar com incompletude de dados e especificar transformações de esquemas. Embora dependências de primeira ordem (como Dependências Geradoras de Tuplas (TGDs) e Dependências Geradoras de Igualdade (EGDs)) sejam padrão, dependências de segunda ordem (SO) são necessárias para expressar a composição de certas classes de mapeamentos de esquemas. Quando estendidas com átomos de igualdade nos consequentes, dependências SO podem expressar composições de mapeamentos de esquemas altamente expressivos.

A abordagem padrão para responder consultas sobre tais dependências envolve calcular um modelo universal usando uma variante do algoritmo de perseguição (chase). No entanto, essa abordagem tem limitações significativas:

1. Ineficiência: Calcular o modelo universal completo frequentemente gera um vasto número de inferências irrelevantes para uma consulta específica.
2. Escalabilidade: Se os dados mudam frequentemente, recalcular a perseguição completa é proibitivamente caro.
3. Complexidade da Igualdade: Técnicas orientadas a objetivos existentes (como Magic Sets) lutam com dependências contendo igualdade e variáveis de função. Abordagens ingênuas que axiomatizam explicitamente a igualdade (usando axiomas de congruência e reflexividade funcional) levam a raciocínios ineficientes e computações de ponto fixo não terminantes devido à proliferação de inferências redundantes.

O artigo aborda o problema aberto de desenvolver uma técnica eficiente de resposta de consultas orientada a objetivos para dependências de primeira e segunda ordem com igualdade que evite inferências desnecessárias enquanto garante correção e terminação.

2. Metodologia

Os autores propõem uma abordagem baseada em transformação que modifica as dependências de entrada para que um cálculo subsequente de perseguição responda à consulta enquanto minimiza inferências irrelevantes. A técnica é implementada como um pipeline (Algoritmo 1) consistindo em sete etapas-chave:

2.1 Eliminação da Quantificação de Segunda Ordem

A dependência SO de entrada $\Sigma$ é transformada em um conjunto de fórmulas de primeira ordem (FO) ($\Sigma_1$) descartando quantificadores de segunda ordem e convertendo variáveis de função em símbolos de função. Essa transformação preserva as respostas das consultas, permitindo que as etapas subsequentes operem dentro do arcabouço da lógica de primeira ordem, embora com símbolos de função.

2.2 Singularização

Para lidar com a igualdade eficientemente sem a sobrecarga de axiomas de congruência completos, os autores aplicam uma variante novel de singularização (estendendo o trabalho de Marnette).

• Mecanismo: A técnica modifica os corpos das dependências para "podar" inferências redundantes. Em vez de usar axiomas de congruência para copiar fatos através de termos iguais, as dependências são reescritas para unir explicitamente átomos via igualdade.
• Correção de Trabalho Anterior: Os autores identificam uma incompletude em uma formulação anterior de ten Cate et al. regarding reflexividade funcional (a propriedade de que se $a \approx b$, então $f(a) \approx f(b)$). Simplesmente adicionar axiomas completos de reflexividade funcional causa não terminação.
• Solução: Os autores introduzem axiomas de reflexividade funcional D-restritos. Esses axiomas derivam igualdades apenas para termos que aparecem em fatos relacionais (rastreados por um predicado de domínio $D$). Isso garante que o modelo universal permaneça finito enquanto preserva todas as respostas relevantes de consultas.

2.3 Skolemização

As dependências FO são convertidas em um programa lógico ($P_3$) substituindo quantificadores existenciais por símbolos de função de Skolem. Crucialmente, a distinção entre símbolos de função "reais" (das dependências SO originais) e símbolos de Skolem é mantida. Axiomas de reflexividade funcional são aplicados apenas a símbolos de função reais, prevenindo derivações infinitas para termos de Skolem.

2.4 Análise de Relevância

Uma técnica de encadeamento reverso é usada para eliminar regras inteiras que comprovadamente não contribuem para as respostas da consulta.

• Abstração: A instância base é abstraída em uma menor "instância crítica" contendo uma constante representativa para cada predicado.
• Análise: O ponto fixo do programa sobre essa instância abstrata é calculado. Regras que não podem disparar na instância abstrata são consideradas irrelevantes e removidas.
• Otimização: O algoritmo explora o fato de que átomos de igualdade podem frequentemente ser derivados de átomos relacionais e regras de domínio, evitando a necessidade de considerar a regra de reflexividade para cada correspondência potencial.

2.5 Transformação Magic Sets

Uma variante do algoritmo Magic Sets é aplicada às regras restantes para podar instâncias de regras irrelevantes (em vez de apenas regras inteiras).

• Adornos: Predicados são adornados com marcadores "ligado" (b) ou "livre" (f) para simular a passagem lateral de informações.
• Tratamento de Igualdade: A transformação é otimizada para igualdade tratando o predicado de igualdade simetricamente e evitando o processamento da regra de reflexividade, que de outra forma dispararia todos os predicados.
• Terminação: Os autores provam que, se a perseguição original termina, o ponto fixo do programa transformado também termina, mesmo com a introdução de predicados mágicos.

2.6 Remoção de Constantes e Símbolos de Função nos Corpos

A transformação Magic Sets pode introduzir termos funcionais nos corpos das regras, que a variante padrão de perseguição não consegue lidar. Os autores aplicam uma transformação (defun) que substitui constantes e termos funcionais nos corpos por variáveis novas e predicados auxiliares ($F_f$), efetivamente axiomatizando a aplicação de função sem embutir termos no corpo.

2.7 Desingularização

Finalmente, as igualdades introduzidas durante a singularização são removidas dos corpos das regras substituindo variáveis por seus termos iguais. Isso resulta em um programa lógico "seguro" ($P_7$) contendo nenhuma igualdade, constantes ou símbolos de função nos corpos, pronto para avaliação eficiente.

2.8 Avaliação Final

O programa final $P_7$ é avaliado usando uma variante de perseguição que trata a igualdade como igualdade "verdadeira" (usando os predicados $V_f$ para rastrear aplicações de função) mas não impõe reflexividade funcional para símbolos de Skolem. Isso garante que o passo final seja eficiente e não sofra com a sobrecarga da axiomatização explícita de igualdade.

3. Contribuições Chave

1. Primeira Técnica Orientada a Objetivos para Dependências SO com Igualdade: O artigo apresenta a primeira técnica capaz de resposta de consultas orientada a objetivos para dependências de segunda ordem generalizadas com igualdade.
2. Singularização Revisada: Uma técnica de singularização corrigida e estendida que lida com variáveis de função e garante completude ao abordar a reflexividade funcional sem causar não terminação.
3. Análise de Relevância para Igualdade: Uma técnica de análise novel que identifica dependências irrelevantes calculando uma abstração do modelo universal, filtrando efetivamente regras que não podem contribuir para respostas de consultas mesmo na presença de igualdade.
4. Magic Sets Otimizados: Uma variante Magic Sets que lida com igualdade eficientemente explorando simetria e evitando o processamento de regras de reflexividade, que são tipicamente uma fonte de sobrecarga.
5. Geração de Benchmarks: Uma nova técnica para gerar dependências de segunda ordem sintéticas e conjuntos de dados que são garantidos para exibir inferências não triviais, abordando a falta de benchmarks existentes para este domínio.
6. Implementação e Avaliação: A primeira implementação de uma perseguição para dependências de segunda ordem com igualdade e uma avaliação empírica extensa.

4. Resultados Experimentais

Os autores implementaram um protótipo em Java, utilizando o sistema RDFox para cálculo de ponto fixo. Eles avaliaram a abordagem em:

• Benchmarks de Primeira Ordem: Conjuntos de dados padrão (LUBM, Deep, Ont) de Benedikt et al.
• Benchmarks de Segunda Ordem: Novos conjuntos de dados sintéticos (Gen-26, Gen-27, Gen-28) gerados por sua ferramenta.

Principais Descobertas:

• Ganhos de Desempenho: A resposta de consultas orientada a objetivos pode ser ordens de magnitude mais rápida do que calcular o modelo universal completo. Em alguns casos (por exemplo, o cenário Deep300), a perseguição completa falhou em terminar dentro do limite de tempo, enquanto a abordagem orientada a objetivos respondeu com sucesso a todas as consultas.
• Comparação de Técnicas:
  • Análise de Relevância foi identificada como o principal motor de melhorias de desempenho, frequentemente reduzindo significativamente o número de fatos derivados.
  • Magic Sets forneceram benefícios adicionais, particularmente quando combinados com análise de relevância, embora em alguns casos (por exemplo, Ont-256) a sobrecarga das regras mágicas pudesse superar os benefícios.
  • Sobrecarga de Segunda Ordem: Para dependências de segunda ordem, a sobrecarga de gerar fatos para aplicações de função (via predicados $F_f$) foi significativa. A análise de relevância foi particularmente eficaz aqui porque reduziu o número de termos para os quais esses fatos precisavam ser gerados.
• Redução de Fatos: As técnicas reduziram significativamente o número de fatos "úteis" derivados, frequentemente por ordens de magnitude, em comparação com a perseguição completa.

5. Significado e Alegações

O artigo afirma resolver um gargalo crítico na integração de dados e composição de mapeamentos de esquemas, onde a composição de mapeamentos frequentemente resulta em dependências de segunda ordem complexas com igualdade. Ao demonstrar que técnicas orientadas a objetivos podem ser adaptadas a esse cenário complexo, os autores mostram que:

• É possível evitar a "maldição da dimensionalidade" associada ao cálculo de modelos universais completos.
• A combinação de singularização, análise de relevância e magic sets fornece um arcabouço robusto para lidar com os desafios específicos de igualdade e variáveis de função.
• A abordagem é prática, conforme evidenciado pelo manuseio bem-sucedido de benchmarks sintéticos em grande escala onde métodos tradicionais falham.

Os autores permanecem modestos sobre trabalhos futuros, notando que estender essas técnicas para cenários de perseguição não terminantes (por exemplo, dependências guardadas) e reduzir ainda mais a sobrecarga de fatos auxiliares (como predicados $D$ e $F_f$) permanecem desafios abertos.