Registro de datos disyuntivo

Datalog disyuntivo es una extensión del lenguaje de programación lógica Datalog que permite disyunciones en las cabezas de las reglas. Esta extensión permite que Datalog disyuntivo exprese varios problemas NP-difíciles que no se sabe que se puedan expresar en Datalog estándar. Datalog disyuntivo se ha aplicado en el contexto del razonamiento sobre ontologías en la web semántica . ^{[ 1 ]} DLV es una implementación de Datalog disyuntivo.

Un programa Datalog disyuntivo es una colección de reglas. Una regla es una cláusula de la forma: ^{[ 2 ]}

${\displaystyle a_{1}\vee \dots \vee a_{n}\leftarrow b_{1}\wedge \dots \wedge b_{m}\quad 1\leq n,0\leq m}$

dónde${\displaystyle b_{1}}$, ...,${\displaystyle b_{m}}$pueden ser negadas y pueden incluir restricciones de (des)igualdad.

Hay al menos tres formas de definir la semántica de Datalog disyuntivo: ^{[ 3 ]}

• semántica de modelo mínimo
• semántica de modelo perfecto
• Semántica de modelos estables disyuntivos, que generaliza la semántica de modelos estables.

El Datalog disyuntivo puede expresar varios problemas NP-completos y NP-difíciles , incluyendo el problema del viajante , la coloración de grafos , el problema del clique máximo y la cobertura mínima de vértices . ^{[ 3 ]} Estos problemas solo se pueden expresar en Datalog si la jerarquía polinómica colapsa.

El sistema DLV ( Data Log with Disyunction, donde se utiliza el símbolo de disyunción lógica V ) implementa la semántica del modelo estable disyuntivo. ^{[ 4 ]}

• Sintaxis y semántica de la programación lógica