Resumo Técnico: Uma Abordagem Baseada em Regras para Especificar Preferências sobre Fatos Conflitantes e Consultar Bases de Conhecimento Inconsistentes

Declaração do Problema

A semântica tolerante à inconsistência, particularmente aquela baseada em reparos de subconjuntos (subset repairs), é uma abordagem padrão para consultar bases de conhecimento (KBs) que violam restrições. Embora existam frameworks para definir "reparos ótimos" usando uma relação de prioridade entre fatos conflitantes (por exemplo, o framework de bases de dados priorizadas de Staworko et al.), uma lacuna crítica permanece: como especificar convenientemente a própria relação de prioridade.

A literatura existente assume que a relação de prioridade é dada, mas é irrealista esperar que os usuários insiram manualmente uma relação binária entre todos os fatos conflitantes. Além disso, quando os usuários tentam especificar preferências via regras, essas regras podem induzir ciclos (por exemplo, o fato A é preferido ao B, B ao C, e C ao A), tornando a relação inválida, visto que relações de prioridade devem ser acíclicas. O artigo aborda o desafio de especificar essas preferências de forma declarativa e resolver os ciclos resultantes para permitir a consulta prática de KBs inconsistentes.

Metodologia

1. Especificação de Preferência Baseada em Regras

Os autores introduzem um framework declarativo onde as relações de prioridade são derivadas de regras de preferência avaliadas sobre um conjunto de dados $D$ e um metadados (meta-database) $M$.

• Meta-database: Um conjunto de dados $F$ contendo metadados (ex: datas, confiabilidade da fonte) vinculados a fatos em $D$ via identificadores únicos.
• Regras de Preferência: Regras da forma $Cond(x_1, x_2) \to pref(x_1, x_2)$, onde o corpo $Cond$ pode referenciar:
  • A presença/ausência de fatos em $D$.
  • Metadados em $F$ (ex: comparar datas ou pontuações de confiabilidade).
  • Axiomas de ontologia (ex: relações de subclasse).
  • Negação e desigualdades.
• Relação Induzida: Uma regra induz uma preferência $pref(id(\alpha), id(\beta))$ se a condição for atendida. A relação de prioridade real $\succ_{\Sigma, K, M}$ é formada filtrando essas preferências induzidas para incluir apenas pares $(\alpha, \beta)$ que aparecem juntos em um conflito.

2. Tratamento de Ciclos

Como as relações induzidas podem conter ciclos, o artigo propõe duas estratégias complementares:

• Verificação de Aciclicidade Estática: Investigar se um conjunto de regras garante a produção de uma relação acíclica para qualquer conjunto de dados.
  • O artigo prova que, para a linguagem geral $PL_{DL}$, verificar a aciclicidade é indecidível.
  • No entanto, para uma linguagem restrita $PL_{pos}$ (regras positivas sem átomos de ontologia ou negação) e restrições de negação binária, o problema é decidível em coNP.
  • O conceito de aciclicidade forte é introduzido: um conjunto de regras é fortemente acíclico se a relação induzida for acíclica para qualquer KB e meta-database, independentemente dos conflitos.
• Resolução Pragmática de Ciclos: Quando as regras não são garantidas como acíclicas, o sistema permite que os usuários particionem as regras em níveis de prioridade ($\Sigma_1, \dots, \Sigma_n$), onde índices menores denotam maior prioridade. Quatro estratégias são definidas para extrair uma sub-relação acíclica:
  1. Subindo ($\succ_u$): Adiciona iterativamente níveis começando pelo índice mais baixo (maior prioridade, $\Sigma_1$), parando se a adição do próximo nível formar um ciclo.
  2. Descendo ($\succ_d$): Começa com a união de todos os níveis e remove iterativamente pares dos níveis de índice mais alto (menor prioridade) que participam de ciclos até que a aciclicidade seja alcançada.
  3. Subindo Refinado ($\succ_{ru}$): Uma variante que remove ciclos dentro de um nível antes de adicionar o próximo.
  4. Fundamentado ($\succ_g$): Uma abordagem de ponto fixo inspirada em extensões fundamentadas (grounded) em frameworks de argumentação.
  • O artigo estabelece relações teóricas entre essas estratégias (ex: $\succ_u \subseteq \succ_d \subseteq \succ_g$) e as vincula a noções existentes como reparos possibilísticos e reparos não derrotados.

3. Implementação

Os autores implementaram um sistema de ponta a ponta usando Programação de Conjuntos de Respostas (ASP):

• Codificação de Entrada: Programas lógicos codificam o conjunto de dados, o meta-database, as restrições, as consultas e as regras de preferência.
• Computação de Conflito & Causa: O sistema computa conflitos e causas (subconjuntos inconsistentes mínimos) usando ASP. Notavelmente, esta implementação lida com conflitos não-binários (conflitos de tamanho arbitrário), enquanto muitas ferramentas existentes são limitadas a conflitos binários.
• Computação de Prioridade: As estratégias de resolução de ciclos são codificadas como programas ASP para derivar a relação de prioridade final.
• Resposta de Consulta: O sistema avalia consultas sob várias semânticas (Brave, AR, IAR) combinadas com tipos de reparo (Subset, Pareto-optimal, Completion-optimal).

Principais Resultados

Contribuições Teóricas

• Indecidibilidade: Provou-se que verificar se um conjunto geral de regras de preferência gera uma relação acíclica é indecidível.
• Decidibilidade: Provou-se que para regras positivas sem átomos de ontologia ($PL_{pos}$) e restrições de negação binária, a verificação de aciclicidade é decidível em coNP.
• Equivalência de Estratégia: Estabeleceu-se que as estratégias de resolução de ciclos propostas correspondem a noções de reparo conhecidas na literatura (Possibilística, Não-derrotada, Fundamentada) quando mapeadas para uma estrutura de KB específica.

Avaliação Experimental

O sistema foi avaliado no benchmark CQAPri (KBs DL-Lite sintéticas) com tamanhos variados (até ~2M de fatos) e densidades de conflito.

• Desempenho de Resolução de Ciclos:
  • A estratégia Descendo ($\succ_d$) mostrou-se significativamente mais rápida de computar do que $\succ_g$ e $\succ_u$ na maioria dos cenários, embora frequentemente produza resultados similares (coincidindo em muitos casos).
  • A estratégia Subindo Refinado ($\succ_{ru}$) causou estouros de memória mesmo em conjuntos de dados pequenos devido à complexidade da codificação ASP.
  • O sistema computou com sucesso relações de prioridade para conjuntos de dados com altas proporções de conflito (até 46%) e grande número de fatos de preferência.
• Desempenho de Resposta de Consulta:
  • O sistema baseado em ASP foi geralmente mais lento que a ferramenta existente baseada em SAT, ORBITS (por ordens de magnitude em grandes conjuntos de dados), para computar respostas sob semânticas de reparo ótimo.
  • No entanto, o sistema ASP conseguiu responder consultas sob as semânticas C-AR e C-brave em casos onde o ORBITS falhou (timeout ou estouro de memória).
  • O sistema é o primeiro a implementar semânticas de reparo ótimo para conflitos não-binários.

Significância e Alegações

O artigo afirma fornecer o primeiro framework declarativo, baseado em regras, para especificar relações de prioridade em KBs inconsistentes, abordando uma lacuna que tem dificultado a adoção prática de semânticas de reparo priorizado.

• Flexibilidade: Ao permitir que as regras referenciem metadados e axiomas de ontologia, o framework oferece uma maneira flexível de definir políticas de gerenciamento de inconsistência sem a entrada manual de relação binária.
• Gerenciamento de Ciclos: O artigo fornece uma solução pragmática para o problema dos ciclos, oferecendo múltiplas estratégias de resolução e garantias teóricas para classes específicas de regras.
• Implementação: A implementação demonstra a viabilidade de usar ASP para esta tarefa, particularmente sua capacidade de lidar com conflitos não-binários, um recurso ausente em ferramentas de estado da arte como o ORBITS.
• Modéstia: Os autores reconhecem que, embora sua implementação ASP seja menos eficiente que abordagens baseadas em SAT para conflitos binários, ela oferece maior expressividade (lidando com tamanhos de conflito arbitrários) e modularidade (ex: mais fácil de estender para outros cálculos de reparo). Eles não alegam ter superado o SAT em velocidade bruta, mas destacam as capacidades únicas de sua abordagem.

O trabalho conclui identificando direções futuras, incluindo a extensão da análise estática para classes de teoria mais amplas, investigação da unicidade de reparos ótimos e a construção de um pipeline totalmente automatizado para gerar programas lógicos a partir de formatos de dados padrão.