Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

Resumo Técnico: Semântica Baseada em Custos para Consulta de Bases de Conhecimento Pesadas Inconsistentes

Enunciado do Problema
O endereçamento de consultas mediadas por ontologias (OMQA) baseia-se em bases de conhecimento (KBs) de Lógica de Descrição (DL) compostas por uma TBox (ontologia) e uma ABox (dados). A semântica clássica de OMQA, baseada em lógica de primeira ordem, falha ao não fornecer respostas informativas quando a KB está inconsistente, pois tudo é acarretado a partir de uma contradição. Embora abordagens existentes lidem com a inconsistência via reparos (ex: AR e semântica brava), estas tipicamente assumem que a TBox é confiável e apenas modificam a ABox. Além disso, as semânticas de reparo padrão geralmente tratam todas as asserções como igualmente confiáveis ou dependem de maximalidade baseada em cardinalidade, carecendo de uma forma matizada de priorizar informações conflitantes com base em graus variados de confiança.

Este artigo aborda o desafio de consultar KBs de DL inconsistentes introduzindo um framework quantitativo. O problema central é definir respostas certas e possíveis significativas quando tanto os axiomas da TBox quanto as asserções da ABox podem ser violados, com as violações sendo penalizadas de acordo com pesos atribuídos.

Metodologia e Framework
Os autores propõem um framework de Base de Conhecimento Pesada (WKB), denotado como $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$.

• Pesos: Uma função de custo $\omega$ atribui um valor em $\mathbb{N}_{>0} \cup \{+\infty\}$ a cada axioma em $\mathcal{T}$ e asserção em $\mathcal{A}$. Pesos infinitos representam restrições "rígidas" que devem ser satisfeitas, enquanto pesos finitos representam restrições "suaves", onde valores mais altos indicam maior confiabilidade.
• Custo de Interpretação: O custo de uma interpretação $I$ é definido como a soma dos pesos de todos os axiomas e asserções violados. Especificamente, para uma inclusão de conceito $\tau$, o custo inclui $\omega_\tau \times |vio_\tau(I)|$, onde $vio_\tau(I)$ é o conjunto de elementos do domínio que violam a inclusão. Asserções podem ser violadas, no máximo, uma vez.
• Semântica: O artigo define quatro semânticas de acarretamento de consulta baseadas no custo das interpretações:
  1. Certo limitado por custo $k$ ($K_\omega \models^k_c q$): $q$ ocorre em todas as interpretações com custo $\le k$.
  2. Possível limitado por custo $k$ ($K_\omega \models^k_p q$): $q$ ocorre em pelo menos uma interpretação com custo $\le k$.
  3. Certo de custo ótimo ($K_\omega \models^{opt}_c q$): $q$ ocorre em todas as interpretações com custo mínimo ($optc(K_\omega)$).
  4. Possível de custo ótimo ($K_\omega \models^{opt}_p q$): $q$ ocorre em pelo menos uma interpretação com custo mínimo.

O framework generaliza as semânticas de reparo existentes. Especificamente, quando os axiomas da TBox possuem pesos infinitos, a semântica de certo de custo ótimo coincide com a semântica $\le_\omega$-AR (Bienvenu, Bourgaux, e Goasdoué 2014), que seleciona reparos que maximizam a soma dos pesos das asserções retidas.

Principais Contribuições
A principal contribuição é uma análise abrangente da complexidade combinada e de dados dos principais problemas de decisão neste cenário:

1. Satisfatibilidade de Custo Limitado (BCS): Determinar se existe uma interpretação com custo $\le k$.
2. Reconhecimento de Respostas Certas e Possíveis: Decidir o acarretamento sob as quatro semânticas definidas.

O estudo abrange uma gama de Lógicas de Descrição, desde a leve $\mathcal{EL}^\bot$ até a expressiva $\mathcal{ALCO}$ (e $\mathcal{ALCO}^\mathcal{Q}$ para provas de limites superiores), tratando tanto de Consultas de Instância (IQs) quanto de Consultas Conjuntivas (CQs).

Resultados de Complexidade
O artigo estabelece limites de complexidade estreitos, resumidos a seguir:

• Complexidade Combinada:

  • A maioria dos problemas é EXPTIME-completa.
  • O reconhecimento de resposta certa para CQs (tanto limitada por custo quanto de custo ótimo) é 2EXPTIME-completo. Esta alta complexidade surge da necessidade de verificar o acarretamento em todos os modelos de um custo específico, o que se relaciona com KBs circunscritas.
  • Estes limites mantêm-se mesmo quando os pesos e o limite de custo $k$ são codificados em binário.

• Complexidade de Dados:

  • Satisfatibilidade de Custo Limitado (BCS): NP-completo.
  • Resposta de Custo Limitado (IQs/CQs): NP-completo (possível) e coNP-completo (certo).
  • Resposta de Custo Ótimo: A complexidade depende fortemente da codificação dos pesos:
    • Se os pesos forem codificados em unário ou limitados independentemente do tamanho da ABox, os problemas são $\Theta^p_2$-completos (resolvíveis em tempo polinomial com chamadas logarítmicas a um oráculo NP).
    • Se os pesos forem codificados em binário e puderem ser exponenciais em relação ao tamanho da ABox, os problemas tornam-se $\Delta^p_2$-completos (resolvíveis em tempo polinomial com acesso a um oráculo NP).
  • O artigo observa que, para a semântica de certo de custo ótimo com pesos binários, o limite superior permanece em aberto, embora os limites inferiores sejam $\Delta^p_2$-duros.

Significância e Alegações
Os autores alegam fornecer um "quadro quase completo" do cenário de complexidade para consulta de KBs inconsistentes sob uma semântica baseada em custo. A significância do trabalho reside na:

1. Flexibilidade Quantitativa: Ir além da consistência binária para uma abordagem graduada onde as respostas podem ser classificadas ou filtradas com base em sua "robustez" (isto é, se elas ocorrem em interpretações próximas ao custo ótimo).
2. Generalização: Unificar conceitos de restrições suaves em bancos de dados (Carmeli et al. 2021) e reparos pesados em ontologias, mostrando que as semânticas de custo ótimo generalizam naturalmente as semânticas de reparo preferencial.
3. Profundidade Técnica: As provas de complexidade utilizam e adaptam técnicas avançadas de raciocínio em DL, incluindo:
   • Filtração e propriedades de modelo limitado para estabelecer limites superiores.
   • Reduções de resposta de consulta de cardinalidade e KBs circunscritas para estabelecer limites inferiores.
   • Adaptações de construções de "entrelaçamento" (interlacing) e "quociente" da literatura de consulta de contagem (Manière 2022) para lidar com as restrições específicas de violações pesadas.

O artigo conclui identificando direções futuras, especificamente a extensão destes resultados para DLs com papéis inversos, inclusões de papéis e papéis funcionais (ex: a família DL-Lite), observando que as técnicas atuais para limites superiores não se transferem facilmente para estes construtos. Também destaca o desafio de desenvolver algoritmos práticos para implementação.