Resumo Técnico: Consulta e Reparação de Bases de Conhecimento Prioritárias Inconsistentes

1. Declaração do Problema

O artigo aborda o desafio de lidar com inconsistência na Resposta a Consultas Mediadas por Ontologias (OMQA) quando a base de conhecimento (KB) subjacente contém fatos priorizados. Enquanto semânticas padrão tolerantes à inconsistência (como AR, IAR e brave) dependem do conceito de reparações (subconjuntos consistentes maximalmente inclusivos dos dados), elas frequentemente falham em distinguir entre reparações com base na confiabilidade ou preferência de fatos específicos.

Em contextos de banco de dados, Staworko, Chomicki e Marcinkowski (2012) introduziram três noções de reparações ótimas (Pareto, global e de conclusão) baseadas em uma relação de prioridade entre fatos conflitantes. Este artigo investiga a transferência dessas noções para o cenário OMQA, especificamente para Lógicas de Descrição leves (DL-Lite). Os problemas centrais analisados são:

1. Entailment de Consulta: Determinar se uma consulta se mantém sob semânticas tolerantes à inconsistência baseadas em reparações ótimas (variantes AR, IAR e brave).
2. Unicidade: Decidir se uma reparação ótima única existe.
3. Enumeração: Enumerar todas as reparações ótimas.
4. Vínculo com Argumentação: Estabelecer uma correspondência formal entre essas reparações e extensões em frameworks de argumentação abstrata.

2. Metodologia

Os autores empregam uma metodologia de duas vertentes que combina análise de complexidade com teoria de argumentação abstrata.

2.1 Análise de Complexidade

O estudo foca na complexidade de dados, onde a ontologia ($T$) e a consulta ($q$) são fixas, e a complexidade é medida em relação ao tamanho do ABox ($A$). A análise abrange:

• Dialectos DL-Lite: Primariamente $DL\text{-}Lite_{core}$ e $DL\text{-}Lite_{H_{horn}}$.
• Tipos de Reparação: Reparações padrão ($SRep$), Pareto-ótimas ($PRep$), Globalmente-ótimas ($GRep$) e de Conclusão-ótimas ($CRep$).
• Semânticas: Variantes de AR (entailment de todas as reparações), IAR (entailment da interseção) e brave (entailment de pelo menos uma).
• Relações de Prioridade: Relações acíclicas gerais, relações transitivas e relações estruturadas por pontuação (onde as prioridades são derivadas de níveis de prioridade).

2.2 Mapeamento para Frameworks de Argumentação

O artigo introduz uma tradução inovadora de KBs prioritárias para Frameworks de Argumentação Baseados em Conjuntos com Preferências (PSETAFs).

• Argumentos: Asserções do ABox.
• Ataques: Derivados de conflitos (subconjuntos inconsistentes mínimos). Um ataque $S \to \alpha$ ocorre se $S \cup \{\alpha\}$ for inconsistente.
• Preferências: A relação de prioridade $\succ$ sobre fatos é mapeada para uma relação de preferência sobre argumentos.
• Redução: Os autores definem uma redução de PSETAFs para SETAFs padrão, permitindo a aplicação de semânticas de argumentação estabelecidas (estável, preferida, fundamentada) para definir reparações.

3. Principais Contribuições e Resultados

3.1 Complexidade de Tarefas de Raciocínio

O artigo fornece um quadro quase completo da complexidade de dados para o raciocínio com reparações ótimas em DL-Lite.

• Verificação de Reparação:
  • Pareto e Conclusão: Em P (tempo polinomial).
  • Global: coNP-completo.
• Entailment de Consulta:
  • Pareto/Conclusão (AR/IAR): coNP-completo.
  • Pareto/Conclusão (Brave): NP-completo.
  • Global (AR/IAR): $\Pi^p_2$-completo.
  • Global (Brave): $\Sigma^p_2$-completo.
  • Nota: Ao contrário das reparações padrão, onde as semânticas IAR e brave são tratáveis (em $AC^0$), a introdução de critérios de otimalidade geralmente aumenta a complexidade para o segundo nível da hierarquia polinomial para reparações globais.
• Unicidade e Enumeração:
  • Unicidade Pareto: coNP-completo.
  • Unicidade Global: $\Pi^p_2$-completo.
  • Enumeração: A enumeração de reparações Pareto e Globais não está em TOTALP (não pode ser feita com tempo total polinomial) para $DL\text{-}Lite_{core}$. No entanto, para reparações de Conclusão-ótimas, a enumeração está em DELAYP (atraso polinomial) para conflitos binários.
• Transitividade: Se a relação de prioridade for transitiva, a unicidade para reparações Globais torna-se tratável (P), embora outros limites inferiores permaneçam inalterados.

3.2 Conexão com Argumentação

Uma contribuição teórica central é o mapeamento preciso entre reparações ótimas e extensões de argumentação:

• Reparações Pareto-ótimas: Correspondem exatamente às extensões estáveis do PSETAF associado.
• Extensões Preferidas: Sob suposições razoáveis (especificamente, se a relação de prioridade for transitiva ou os conflitos forem binários), as reparações Pareto-ótimas também coincidem com extensões preferidas.
• Reparações Globais e de Conclusão: Estas correspondem a subconjuntos próprios de extensões estáveis, mas atualmente carecem de um análogo direto na literatura padrão de argumentação.

3.3 Semântica Fundamentada

Inspirados pela extensão fundamentada na argumentação, os autores propõem uma nova semântica para KBs prioritárias:

• Definição: Uma consulta é entailed sob semântica fundamentada se ela se mantém na extensão fundamentada do PSETAF associado.
• Propriedades:
  • A extensão fundamentada é um subconjunto de toda reparação Pareto-ótima (uma sub-aproximação de P-IAR).
  • É estritamente mais produtiva (contém mais asserções) do que a semântica Elect proposta recentemente.
  • Complexidade: O entailment de consulta sob semântica fundamentada é P-completo na complexidade de dados para $DL\text{-}Lite_{H_{horn}}$.
• Implementação: A extensão fundamentada pode ser computada via semântica de bem-fundamento de um programa lógico normal, ou aproximada por uma consulta de primeira ordem (SQL) para profundidades de iteração fixas.

4. Significado e Alegações

O artigo alega significado em três áreas principais:

1. Paisagem de Complexidade: Esclarece que, embora reparações ótimas ofereçam um tratamento de inconsistência mais nuances, elas vêm com um custo computacional significativo em comparação com reparações padrão, frequentemente empurrando problemas para o segundo nível da hierarquia polinomial. No entanto, identifica casos tratáveis específicos (entailment Pareto/Conclusão, semântica fundamentada).
2. Ponte com Argumentação: Estabelece um vínculo rigoroso entre reparações de banco de dados prioritárias e argumentação abstrata. Ao mostrar que reparações Pareto-ótimas são extensões estáveis, o artigo situa a OMQA dentro de um contexto teórico mais amplo, permitindo a importação de resultados da argumentação (por exemplo, propriedades de coerência de frameworks simétricos).
3. Semânticas Práticas: A proposta da semântica fundamentada oferece uma alternativa tratável para o tratamento de inconsistência. Fornece uma aproximação computável em tempo polinomial da semântica Pareto-IAR que é mais informativa do que alternativas existentes como Elect. O artigo demonstra que essa semântica pode ser implementada usando programação lógica padrão ou sistemas de banco de dados relacionais.

Os autores observam que, embora não respondam definitivamente qual das três noções de reparações ótimas (Pareto, Global, Conclusão) é "mais natural", a correspondência das reparações Pareto com extensões estáveis e preferidas sugere uma forte justificação teórica para sua adoção. O trabalho também contribui com novos resultados técnicos para a comunidade de argumentação, como a coerência de PSETAFs fortemente simétricos com preferências transitivas.