Resumo Técnico: Abdução de ABox para Bases de Conhecimento Inconsistentes sob Semântica de Reparo

Definição do Problema

O artigo aborda o problema de abdução de ABox no contexto de Bases de Conhecimento (BCs) inconsistentes que utilizam semântica de reparo.

Na abdução padrão, dada uma BC $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ e uma observação $\Phi$ (um fato não entido por $\mathcal{K}$), o objetivo é encontrar uma hipótese $H$ (um conjunto de fatos) tal que $\langle \mathcal{T}, \mathcal{A} \cup H \rangle \models \Phi$. Tradicionalmente, isso assume que $\mathcal{K}$ é consistente. No entanto, em cenários realistas, os dados frequentemente contêm erros que levam a inconsistências. Sob semântica clássica, uma BC inconsistente entende todo fato, tornando a abdução e a dedução padrão inúteis.

Para abordar isso, os autores definem abdução sob semântica de reparo, especificamente as semânticas Brave e AR (Todos os Reparos). Um reparo é um subconjunto maximal consistente do ABox.

• Semântica Brave: $\mathcal{K} \models_{Brave} \alpha$ se $\alpha$ é entido por pelo menos um reparo.
• Semântica AR: $\mathcal{K} \models_{AR} \alpha$ se $\alpha$ é entido por todo reparo.

O desafio central é definir noções adequadas de hipóteses neste cenário. O artigo introduz critérios específicos para guiar a abdução em direção a hipóteses "úteis":

1. Confinamento de Conflito: Uma hipótese $H$ é de confinamento de conflito se não introduzir novos conflitos na BC (ou seja, $\text{Conf}(\langle \mathcal{T}, \mathcal{A} \cup H \rangle) = \text{Conf}(\langle \mathcal{T}, \mathcal{A} \rangle)$).
2. Não trivialidade: A hipótese $H$ não deve ser simplesmente a própria observação ($\alpha \notin H$).
3. Restrição de Assinatura: $H$ deve usar apenas símbolos de uma assinatura especificada $\Sigma$.
4. Minimalidade: As hipóteses são avaliadas com base na minimalidade por subconjunto ($\subseteq$-min), minimalidade por cardinalidade ($\leq$-min) ou minimalidade por conflito ($\subseteq_c$-min, $\leq_c$-min).

Metodologia

Os autores realizam uma análise abrangente de complexidade dos problemas de Existência e Verificação para essas variantes de abdução. O estudo foca em duas lógicas de descrição (LDs) tratáveis proeminentes, amplamente utilizadas em BCs de grande escala:

• $\mathcal{EL}^\bot$: Suporta conjunção e restrições existenciais.
• DL-Lite: Especificamente DL-Lite$_{core}$ e DL-Lite$_R$, que fundamentam o perfil OWL 2 QL.

A metodologia envolve:

1. Definições Formais: Definir rigorosamente $S$-hipóteses (onde $S \in \{Brave, AR\}$) e suas propriedades (confinamento de conflito, não trivialidade, etc.) dentro de BCs inconsistentes.
2. Análise de Complexidade: Determinar a complexidade computacional (variando de NL a $\Pi^P_2$) para várias combinações de lógicas, semânticas e propriedades de hipóteses.
3. Reduções: Provar resultados de dureza e pertinência via reduções de problemas de complexidade conhecidos (por exemplo, Alcance Direcionado, SAT, QBF, MUS) e adaptar construções existentes para raciocínio tolerante a inconsistências.
4. Análise Estrutural: Investigar propriedades do espaço de soluções, como a não convexidade do conjunto de hipóteses AR (onde um subconjunto de uma hipótese não é necessariamente uma hipótese), e como isso afeta abordagens algorítmicas.

Principais Contribuições e Resultados

1. Paisagem de Complexidade

O artigo fornece uma tabela detalhada de complexidade (Tabela 1 no artigo) cobrindo a existência e verificação de hipóteses. As principais descobertas incluem:

• DL-Lite:

  • Verificação: Geralmente alinha-se com a complexidade da entailment (NL para Brave, coNP para AR).
  • Existência: Surpreendentemente, a existência de hipóteses gerais e de confinamento de conflito é NL-completa para ambas as semânticas Brave e AR. Isso é frequentemente menor que a complexidade da entailment geral sob AR (coNP).
  • Minimalidade: A verificação de hipóteses AR $\subseteq$-mínimas é DP-completa.
  • Insight Estrutural: Em DL-Lite, os suportes T mínimos são de tamanho 1. Isso permite a construção "de baixo para cima" de hipóteses, contornando o problema de não convexidade que aflige $\mathcal{EL}^\bot$.

• $\mathcal{EL}^\bot$:

  • Verificação: Geralmente corresponde à complexidade da entailment (NP para Brave, coNP para AR).
  • Existência:
    • Hipóteses gerais: P-completa (Brave), coNP-completa (AR).
    • Hipóteses com restrição de assinatura/não triviais: A complexidade salta para $\Sigma^P_2$-completa para ambas as semânticas.
  • Confinamento de Conflito:
    • Brave: A existência torna-se $\Sigma^P_2$-completa (maior que a existência geral).
    • AR: A existência permanece coNP-completa.
  • Minimalidade: A verificação de hipóteses AR $\subseteq$-mínimas é $\Pi^P_2$-completa, impulsionada pela não convexidade do espaço de hipóteses.

2. Insights Teóricos

• Hipótese Trivial: Sob semântica AR, a existência de qualquer hipótese é equivalente à existência da hipótese trivial $\{\alpha\}$, desde que $\{\alpha\}$ seja de confinamento de conflito. Isso simplifica significativamente as verificações de existência.
• Não Convexidade: O conjunto de hipóteses AR não é necessariamente convexo (um subconjunto de uma hipótese pode não ser uma hipótese). Essa propriedade leva a classes de complexidade mais altas (DP, $\Pi^P_2$) para verificação em $\mathcal{EL}^\bot$, enquanto as propriedades estruturais do DL-Lite permitem complexidade menor.
• Confinamento de Conflito vs. Trivialidade: Em $\mathcal{EL}^\bot$, uma hipótese de confinamento de conflito pode existir mesmo se a própria observação não for de confinamento de conflito (Observação 25). Isso contrasta com o DL-Lite, onde a própria observação deve ser de confinamento de conflito se uma hipótese de confinamento de conflito existir.

3. Comparação com Cenários Consistentes

O artigo observa que, enquanto a abdução em BCs consistentes frequentemente se reduz à entailment, o cenário inconsistente introduz mudanças significativas de complexidade. Por exemplo, exigir confinamento de conflito em $\mathcal{EL}^\bot$ sob semântica Brave aumenta a complexidade, enquanto em cenários consistentes, tal restrição não é aplicável ou significativa da mesma maneira.

Significado e Alegações

Os autores afirmam fornecer a primeira análise abrangente da abdução de ABox sob semântica de reparo. Seu trabalho preenche uma lacuna na literatura, que anteriormente focava em BCs consistentes ou sistemas práticos específicos (por exemplo, Du et al. [12] para semântica IAR) sem uma paisagem teórica completa.

• Completude: O artigo estabelece uma classificação de complexidade quase completa, com apenas a verificação de hipóteses Brave $\leq_c$-mínimas em $\mathcal{EL}^\bot` permanecendo aberta (colocada em PSPACE,$\Pi^P_2$-dura).
• Relevância Prática: Ao focar em DL-Lite e $\mathcal{EL}^\bot$, os resultados são diretamente aplicáveis a sistemas de acesso a dados baseados em ontologias de grande escala onde inconsistências são comuns.
• Compreensão Nuanceada: O trabalho demonstra que a escolha da semântica (Brave vs. AR) e as propriedades específicas da hipótese (confinamento de conflito, não trivialidade) alteram drasticamente a dificuldade computacional, às vezes tornando os problemas mais fáceis (existência em DL-Lite) e às vezes mais difíceis (existência em $\mathcal{EL}^\bot$) em comparação com seus equivalentes consistentes.

O artigo conclui sugerindo trabalhos futuros sobre complexidade de dados (fixando o TBox), explorando observações expressivas (conceitos complexos) e investigando indivíduos frescos em hipóteses, notando que admitir indivíduos frescos poderia alterar significativamente a paisagem de complexidade.