💻 computer science

Using ASP(Q) to Handle Inconsistent Prioritized Data

Este artigo apresenta a primeira implementação de semânticas baseadas em reparações globalmente ótimas e de uma aproximação tratável (grounded) para consultas tolerantes a inconsistências em dados prioritários, utilizando a extensão ASP(Q) para definir e avaliar três noções de reparação ótima com complexidade computacional no primeiro ou segundo nível da hierarquia polinomial.

Autores originais: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta

Publicado 2026-04-24

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um juiz tentando resolver um caso complexo. Você tem um monte de testemunhas (os dados) e um conjunto de leis (a lógica). O problema é que algumas testemunhas estão mentindo ou se contradizendo: uma diz "estava chovendo", a outra diz "estava sol". Se você tentar usar todas as informações ao mesmo tempo, o caso quebra e não há solução.

Na ciência de dados e inteligência artificial, isso é chamado de inconsistência. O artigo que você pediu para explicar trata de como os computadores podem "consertar" esses dados contraditórios para responder a perguntas de forma inteligente, mesmo quando as informações estão bagunçadas.

Aqui está a explicação do artigo, traduzida para uma linguagem simples, usando analogias do dia a dia:

1. O Problema: A Sala de Reunião Caótica

Pense em uma empresa onde os funcionários enviam relatórios.

O Conflito: O João diz que o projeto A foi concluído. A Maria diz que o projeto A foi cancelado. Ambos não podem estar certos ao mesmo tempo.
A Prioridade: Mas, e se o João é o gerente sênior e a Maria é um estagiário? Ou se o relatório do João é de ontem e o da Maria é de hoje? Nós temos uma relação de prioridade. Sabemos que, em caso de briga, o relatório do gerente (ou o mais recente) deve vencer.

O objetivo do artigo é: como o computador decide quais informações manter e quais descartar para responder a perguntas como "O projeto A está ativo?", respeitando essas prioridades?

2. A Solução: Os "Reparos" (Consertos)

Para resolver a briga, o computador cria "reparos". Um reparo é uma versão da história onde removemos o mínimo possível de informações para que tudo faça sentido.

Reparo 1: Mantemos o João, removemos a Maria.
Reparo 2: Mantemos a Maria, removemos o João.

Agora, temos várias versões possíveis da verdade. A pergunta é: qual versão a gente usa?

3. Os Três Tipos de "Melhores Consertos"

Os autores do artigo focam em três maneiras de escolher o melhor reparo, baseadas em quem tem mais "poder" (prioridade):

Reparo Pareto (O "Justo"): Você não pode melhorar a situação trocando uma informação ruim por uma boa sem piorar outra coisa. É como um jogo de tabuleiro onde você não pode ganhar uma peça sem perder outra de valor igual.
Reparo Global (O "Mestre Estratégico"): Aqui, olhamos para o todo. Se existe qualquer maneira de trocar um conjunto de informações ruins por um conjunto de informações boas (mesmo que seja uma troca complexa), nós fazemos. É o nível mais difícil de calcular, como resolver um quebra-cabeça gigante onde você precisa pensar em todas as peças de uma vez.
Reparo de Conclusão (O "Acordo Total"): Imagine que os funcionários não têm uma regra clara de quem manda em quem. O computador tenta inventar uma regra de prioridade completa (uma "ordem do dia") que faça sentido e veja qual reparo sobra.

A Grande Descoberta: Até agora, os computadores conseguiam calcular facilmente os tipos "Justo" e "Acordo Total". O tipo "Mestre Estratégico" (Global) era considerado impossível de calcular em tempo útil para grandes quantidades de dados. Este artigo é o primeiro a conseguir fazer isso!

4. A Ferramenta Mágica: ASP(Q)

Como eles conseguiram fazer o impossível? Usando uma ferramenta chamada ASP(Q).

A Analogia do Detetive: Imagine que o ASP é um detetive que investiga um caso. O ASP(Q) é um detetive sênior que pode contratar outros detetives e perguntar: "Existe algum cenário onde o suspeito é inocente?" ou "Para TODOS os cenários possíveis, o suspeito é culpado?".
Essa capacidade de fazer perguntas sobre "existem" e "para todos" permite resolver problemas muito mais complexos (como o reparo Global) do que as ferramentas antigas conseguiam.

5. O Truque Inteligente: A "Semântica de Fundamento"

Calcular o reparo "Mestre Estratégico" é muito lento e pesado para o computador. O artigo mostra algo surpreendente:

Existe uma versão simplificada e rápida chamada Semântica de Fundamento (Grounded Semantics).
A Analogia da Peneira: Imagine que você quer separar areia de ouro. A peneira rápida (Fundamento) pega 90% do ouro de forma instantânea. Para os 10% restantes, você precisa usar a peneira lenta e pesada (Global).
O estudo mostrou que, na maioria dos casos, a peneira rápida é tão boa que você nem precisa usar a pesada. Isso torna o sistema muito mais prático para o mundo real.

6. O Que Eles Descobriram (Os Resultados)

Os autores testaram tudo isso em computadores reais com milhares de dados:

É possível, mas difícil: Conseguir calcular o reparo "Mestre Estratégico" (Global) é muito mais lento e consome mais memória do que os outros tipos. É como escalar uma montanha em vez de subir uma rampa.
A aproximação é incrível: A versão simplificada (Fundamento) funciona tão bem que, na prática, muitas vezes é melhor usá-la primeiro. Se ela não der a resposta, aí sim você tenta o método pesado.
Localização: Eles aprenderam que não precisa olhar para todo o banco de dados. Se a pergunta é sobre o "Projeto A", o computador só precisa olhar para as pessoas que falaram sobre o "Projeto A", ignorando o resto da empresa. Isso acelera tudo.

Resumo Final

Este artigo é um marco porque:

Quebrou o recorde: Foi a primeira vez que conseguiram implementar a versão mais complexa e rigorosa de conserto de dados (Global).
Encontrou um atalho: Mostrou que uma versão mais simples e rápida (Fundamento) é extremamente eficaz e pode ser usada como um primeiro passo para economizar tempo e energia.
Ferramenta nova: Usou uma tecnologia de programação (ASP(Q)) que permite lidar com a complexidade de forma mais elegante do que os métodos antigos.

Em suma, eles ensinaram aos computadores uma nova maneira de resolver brigas de dados, permitindo que eles tomem decisões mais inteligentes e precisas, mesmo quando as informações estão bagunçadas e contraditórias.

1. Problema Investigado

O artigo aborda o desafio de realizar consultas em bases de dados ou ontologias que contêm inconsistências em relação a uma teoria lógica (como restrições de integridade ou ontologias). Quando os dados são inconsistentes, a resposta tradicional (que exigiria consistência total) seria vazia ou inútil.

A abordagem padrão para lidar com isso são as semânticas baseadas em reparos (repair-based semantics), onde se considera subconjuntos maximais dos dados que são consistentes (chamados de reparos). No entanto, quando há múltiplos reparos possíveis, surgem três semânticas principais de consulta:

AR (Aristotélica): A resposta deve valer em todos os reparos.
Brave: A resposta vale se existir pelo menos um reparo onde ela é verdadeira.
IAR (Intersection of All Repairs): A resposta vale se estiver na interseção de todos os reparos.

O foco deste trabalho é lidar com dados priorizados, onde fatos conflitantes possuem uma relação de preferência ( $\succ$ ). Isso leva a três tipos de reparos ótimos:

Pareto-ótimos: Nenhum reparo pode ser melhorado trocando um fato não selecionado por um fato preferido.
Globalmente ótimos: Nenhum reparo pode ser melhorado globalmente (troca de um conjunto de fatos por outro conjunto preferido).
Ótimos de conclusão (Completion-optimal): Reparos que são globalmente ótimos para alguma extensão total da relação de preferência parcial.

O Desafio Principal: Enquanto reparos Pareto e de conclusão têm complexidade de dados no primeiro nível da hierarquia polinomial (NP ou coNP), os reparos globalmente ótimos atingem o segundo nível da hierarquia polinomial ( $\Sigma^p_2$ e $\Pi^p_2$ ). Isso torna o raciocínio computacionalmente muito mais difícil, e até então, não havia implementações práticas para semânticas baseadas em reparos globalmente ótimos.

2. Metodologia

Os autores propõem o uso de Programação por Resposta de Conjuntos com Quantificadores (ASP(Q)) para modelar e resolver esses problemas.

ASP(Q): Uma extensão do ASP que permite quantificar sobre os conjuntos de resposta (answer sets) de programas ASP aninhados. Isso permite modelar problemas que exigem alternância de quantificadores (existencial/universal), característica do segundo nível da hierarquia polinomial, de forma mais natural e compacta do que o ASP disjuntivo tradicional (que exigiria técnicas complexas como saturation).
Codificação (Encoding):
- Os autores desenvolveram codificações em ASP(Q) para verificar se uma consulta é válida sob as semânticas de reparos Pareto, Completos e, crucialmente, Globalmente Ótimos.
- Para a semântica G-Brave (existencial), o programa verifica se existe um reparo que contém uma causa da consulta e que não possui nenhum "melhoramento global".
- Para a semântica G-AR (universal), verifica-se se para todo reparo, ou ele contém a causa, ou ele possui um melhoramento global (o que o invalidaria como ótimo).
Otimizações e Aproximações:
- Localização (Localization): Para evitar processar todo o conjunto de dados, os autores utilizam noções de "alcance" (forte e fraco) baseadas nos conflitos e na relação de prioridade para restringir o escopo da codificação apenas aos fatos relevantes para a consulta.
- Codificações para Conflitos Binários: Simplificações específicas para o caso onde os conflitos envolvem apenas dois fatos.
- Semântica Fundada (Grounded Semantics): Uma aproximação tratável (complexidade PTIME) baseada em teoria de argumentação abstrata. Ela calcula um reparo "fundado" que é um subconjunto de todos os reparos Pareto. O artigo explora sua eficácia como uma aproximação inferior (under-approximation) para filtrar respostas rapidamente.

3. Principais Contribuições

Primeira Implementação de Reparos Globalmente Ótimos: O trabalho apresenta a primeira implementação funcional de semânticas baseadas em reparos globalmente ótimos, superando a barreira de complexidade através do uso de ASP(Q).
Primeira Implementação da Semântica Fundada: Introduz a implementação prática da semântica fundada para bases de conhecimento priorizadas, oferecendo uma alternativa tratável.
Framework Unificado: Desenvolve um sistema que suporta todas as três semânticas de reparos ótimos (Pareto, Global, Conclusão) e as três semânticas de consulta (AR, Brave, IAR), além das aproximações.
Análise Comparativa: Fornece uma comparação empírica rigorosa entre as diferentes semânticas, codificações e aproximações.

4. Resultados Experimentais

Os experimentos foram realizados utilizando o benchmark ORBITS/CQAPri (baseado em DL-Lite) com conjuntos de dados sintéticos de diferentes tamanhos e densidades de conflito.

Viabilidade de Reparos Globais: Embora a complexidade teórica seja alta, os resultados mostram que é possível computar respostas sob semântica globalmente ótima para instâncias de tamanho moderado. No entanto, o tempo de execução é significativamente maior e há mais timeouts (esgotamento de tempo) comparado às semânticas Pareto ou Completas.
Eficácia da Semântica Fundada: A semântica fundada provou ser uma aproximação surpreendentemente eficaz. Em muitos casos, ela captura uma grande proporção das respostas válidas sob as semânticas mais complexas (IAR), permitindo filtrar rapidamente respostas que não precisam de verificação mais cara.
Impacto da Localização: A técnica de localização é crítica; sem ela, a maioria das instâncias resulta em timeout.
Diferenças entre Semânticas:
- As semânticas Pareto e Completas frequentemente produzem o mesmo conjunto de respostas em muitos cenários.
- A semântica Globalmente Ótima tende a ser mais restritiva (para AR) ou mais permissiva (para Brave) dependendo da estrutura de prioridades, mas com um custo computacional alto.
Estratégia Híbrida Sugerida: Os autores sugerem uma estratégia prática: primeiro tentar resolver usando a semântica fundada (rápida) e depois as semânticas Pareto/Completas. Apenas se o status da resposta permanecer indeciso, deve-se acionar o solver mais pesado para a semântica Globalmente Ótima.

5. Significado e Conclusão

Este trabalho é um marco na área de resposta a consultas tolerantes a inconsistências e lógica não monotônica.

Avanço Teórico-Prático: Demonstra que problemas no segundo nível da hierarquia polinomial, anteriormente considerados intratáveis para implementação prática em larga escala, podem ser abordados eficientemente usando ASP(Q).
Aplicabilidade: Oferece ferramentas para cenários onde a priorização de dados é crucial (ex: integração de dados de múltiplas fontes com confiança variável, sistemas de recomendação com regras conflitantes).
Direção Futura: A eficácia da semântica fundada como pré-processamento abre caminho para o desenvolvimento de métodos altamente otimizados para grandes volumes de dados, permitindo o uso de semânticas rigorosas com um overhead mínimo.

Em resumo, o artigo valida o ASP(Q) como a ferramenta adequada para lidar com a complexidade de reparos ótimos globais e fornece um conjunto de técnicas (localização, aproximações) que tornam o raciocínio sobre dados inconsistentes priorizados viável na prática.