Resumen Técnico: Consulta y Reparación de Bases de Conocimiento Priorizadas Inconsistentes

1. Enunciado del Problema

El artículo aborda el desafío de manejar la inconsistencia en la Respuesta a Consultas Mediada por Ontologías (OMQA) cuando la base de conocimientos (KB) subyacente contiene hechos priorizados. Mientras que las semánticas estándar tolerantes a la inconsistencia (como AR, IAR y valiente) se basan en el concepto de reparaciones (subconjuntos consistentes maximalmente inclusivos de los datos), a menudo no logran distinguir entre reparaciones basándose en la fiabilidad o preferencia de hechos específicos.

En entornos de bases de datos, Staworko, Chomicki y Marcinkowski (2012) introdujeron tres nociones de reparaciones óptimas (Pareto, global y de completitud) basadas en una relación de prioridad entre hechos conflictivos. Este artículo investiga la transferencia de estas nociones al entorno OMQA, específicamente para Lógicas de Descripción ligeras (DL-Lite). Los problemas centrales analizados son:

1. Entailment de Consultas: Determinar si una consulta se cumple bajo semánticas tolerantes a la inconsistencia basadas en reparaciones óptimas (variantes de AR, IAR y valiente).
2. Unicidad: Decidir si existe una única reparación óptima.
3. Enumeración: Enumerar todas las reparaciones óptimas.
4. Vínculo con Argumentación: Establecer una correspondencia formal entre estas reparaciones y extensiones en marcos de argumentación abstracta.

2. Metodología

Los autores emplean una metodología de doble enfoque que combina el análisis de complejidad con la teoría de argumentación abstracta.

2.1 Análisis de Complejidad

El estudio se centra en la complejidad de datos, donde la ontología ($T$) y la consulta ($q$) son fijas, y la complejidad se mide frente al tamaño del ABox ($A$). El análisis abarca:

• Dialectos DL-Lite: Principalmente $DL\text{-}Lite_{core}$ y $DL\text{-}Lite_{H_{horn}}$.
• Tipos de Reparación: Reparaciones estándar ($SRep$), óptimas de Pareto ($PRep$), óptimas globales ($GRep$) y óptimas de completitud ($CRep$).
• Semánticas: Variantes de AR (entailment desde todas las reparaciones), IAR (entailment desde la intersección) y valiente (entailment desde al menos una).
• Relaciones de Prioridad: Relaciones acíclicas generales, relaciones transitivas y relaciones estructuradas por puntuación (donde las prioridades se derivan de niveles de prioridad).

2.2 Mapeo al Marco de Argumentación

El artículo introduce una traducción novedosa desde KBs priorizadas hacia Marcos de Argumentación Basados en Conjuntos con Preferencias (PSETAFs).

• Argumentos: Afirmaciones del ABox.
• Ataques: Derivados de conflictos (subconjuntos inconsistentes mínimos). Un ataque $S \to \alpha$ ocurre si $S \cup \{\alpha\}$ es inconsistente.
• Preferencias: La relación de prioridad $\succ$ sobre hechos se mapea a una relación de preferencia sobre argumentos.
• Reducción: Los autores definen una reducción desde PSETAFs hacia SETAFs estándar, permitiendo la aplicación de semánticas de argumentación establecidas (estable, preferida, fundamentada) para definir reparaciones.

3. Contribuciones y Resultados Clave

3.1 Complejidad de las Tareas de Razonamiento

El artículo proporciona un panorama casi completo de la complejidad de datos para el razonamiento con reparaciones óptimas en DL-Lite.

• Verificación de Reparaciones:
  • Pareto y Completitud: En P (tiempo polinomial).
  • Global: coNP-completo.
• Entailment de Consultas:
  • Pareto/Completitud (AR/IAR): coNP-completo.
  • Pareto/Completitud (Valiente): NP-completo.
  • Global (AR/IAR): $\Pi^p_2$-completo.
  • Global (Valiente): $\Sigma^p_2$-completo.
  • Nota: A diferencia de las reparaciones estándar donde las semánticas IAR y valiente son tratables (en $AC^0$), la introducción de criterios de optimalidad generalmente aumenta la complejidad al segundo nivel de la jerarquía polinomial para reparaciones globales.
• Unicidad y Enumeración:
  • Unicidad de Pareto: coNP-completo.
  • Unicidad Global: $\Pi^p_2$-completo.
  • Enumeración: La enumeración de reparaciones Pareto y Globales no está en TOTALP (no se puede realizar con tiempo total polinomial) para $DL\text{-}Lite_{core}$. Sin embargo, para reparaciones óptimas de completitud, la enumeración está en DELAYP (retraso polinomial) para conflictos binarios.
• Transitividad: Si la relación de prioridad es transitiva, la unicidad para reparaciones Globales se vuelve tratable (P), aunque otros límites inferiores permanecen sin cambios.

3.2 Conexión con la Argumentación

Una contribución teórica central es el mapeo preciso entre reparaciones óptimas y extensiones de argumentación:

• Reparaciones Óptimas de Pareto: Corresponden exactamente a las extensiones estables del PSETAF asociado.
• Extensiones Preferidas: Bajo suposiciones razonables (específicamente, si la relación de prioridad es transitiva o los conflictos son binarios), las reparaciones óptimas de Pareto también coinciden con las extensiones preferidas.
• Reparaciones Globales y de Completitud: Estas corresponden a subconjuntos propios de extensiones estables, pero actualmente carecen de un análogo directo en la literatura estándar de argumentación.

3.3 Semántica Fundamentada

Inspirados por la extensión fundamentada en argumentación, los autores proponen una nueva semántica para KBs priorizadas:

• Definición: Una consulta se cumple bajo semántica fundamentada si se cumple en la extensión fundamentada del PSETAF asociado.
• Propiedades:
  • La extensión fundamentada es un subconjunto de toda reparación óptima de Pareto (una subaproximación de P-IAR).
  • Es estrictamente más productiva (contiene más afirmaciones) que la semántica Elect propuesta recientemente.
  • Complejidad: El entailment de consultas bajo semántica fundamentada es P-completo en complejidad de datos para $DL\text{-}Lite_{H_{horn}}$.
• Implementación: La extensión fundamentada puede calcularse mediante la semántica de base bien fundada de un programa lógico normal, o aproximarse mediante una consulta de primer orden (SQL) para profundidades de iteración fijas.

4. Significado y Afirmaciones

El artículo afirma su relevancia en tres áreas principales:

1. Landscape de Complejidad: Aclara que, aunque las reparaciones óptimas ofrecen un manejo de inconsistencia más matizado, conllevan un costo computacional significativo en comparación con las reparaciones estándar, a menudo empujando los problemas al segundo nivel de la jerarquía polinomial. Sin embargo, identifica casos tratables específicos (entailment Pareto/Completitud, semántica fundamentada).
2. Puente con la Argumentación: Establece un vínculo riguroso entre las reparaciones de bases de datos priorizadas y la argumentación abstracta. Al demostrar que las reparaciones óptimas de Pareto son extensiones estables, el artículo sitúa a OMQA dentro de un contexto teórico más amplio, permitiendo la importación de resultados de la argumentación (por ejemplo, propiedades de coherencia de marcos simétricos).
3. Semánticas Prácticas: La propuesta de la semántica fundamentada ofrece una alternativa tratable para el manejo de inconsistencias. Proporciona una aproximación computable en tiempo polinomial de la semántica Pareto-IAR que es más informativa que alternativas existentes como Elect. El artículo demuestra que esta semántica puede implementarse utilizando programación lógica estándar o sistemas de bases de datos relacionales.

Los autores señalan que, aunque no responden definitivamente cuál de las tres nociones de reparación óptima (Pareto, Global, Completitud) es "más natural", la correspondencia de las reparaciones Pareto con extensiones estables y preferidas sugiere una fuerte justificación teórica para su adopción. El trabajo también contribuye con nuevos resultados técnicos a la comunidad de argumentación, como la coherencia de PSETAFs fuertemente simétricos con preferencias transitivas.