The problem of incomplete data in SPARQL

Abstract

La información incompleta es uno de los mayores desafíos para la gestión de datos en la Web. Los datos en son incompletos en la Web por varias razones: porque hay datos que se desconocen, porque es ocultada por privacidad, o porque aún no ha sido agregada a los datos, porque aún no se ha integrado con otras fuentes de datos, etc. Una pregunta fundamental en la exploración de datos en la Web es cómo definir la semántica de las consultas sobre datos incompletos. Esta tesis estudia el problema de información incompleta en SPARQL, el lenguaje de consulta definido por el W3C para los datos de la Web. Nos enfocamos en dos formas básicas de incompletitud en SPARQL: los blancos y variables con valores no asignados (unbound values). Su principal metodología es la aplicación de ideas y técnicas conocidas del modelo relacional para enfrentar estos problemas en SPARQL. Con este fin, contrastamos los nodos blancos y los valores no asignados con tres tipos de valores nulos usados en el modelo relacional: valores que se sabe que existen, pero se desconocen; valores que se sabe que no existen; y valores de los que no se sabe si existen. Las contribuciones de esta tesis son las siguientes. Primero, mostramos que de acuerdo a la especificación de RDF y el uso de los nodos blancos en la base de conocimiento Wikidata, estos corresponden a los nulos que denotan valores que existen, pero se desconocen. Sin embargo, las consultas SPARQL entregan respuestas que son incorrectas de acuerdo a la semántica de los nodos blancos como valores que existen pero son desconocidos. Nosotros exploramos la factibilidad de que SPARQL retorne solo resultados correctos (certain answers) implementando métodos que son usados con el mismo fin en el modelo relacional. Para entender el impacto que este cambio puede tener en SPARQL, analizamos cómo afecta los ejemplos de consulta de usuarios de Wikidata. En relación con la semántica de los valores no asignados, mostramos que ellos se comportan en algunos casos como valores que no existen y en otros como valores que no se sabe que existen. Proponemos una extensión del álgebra relacional inspirada en las tablas con tuplas posibles de Biskup (maybe-tuples). Esta álgebra es el resultado de escoger dos operadores para cada operador del álgebra relacional, donde uno entrega resultados correctos y el otro resultados posibles. Este resultado mejora nuestro entendimiento de SPARQL al hacer explícito que SPARQL es un resultado particular de escoger para cada operador uno de los dos operadores alternativos del álgebra que proponemos. Uno de los problemas para analizar la información incompleta en SPARQL es la falta de un formalismo para comparar las diferentes propuestas. Nosotros abordamos este problema proponiendo un nuevo formalismo llamado Nested Datalog, que extiende Datalog para componer consultas. Extendiendo la codificación de SPARQL en Datalog por Angles y Gutiérrez (después de corregir algunos de sus problemas para consultas que implican información incompleta), mostramos cómo codificar SPARQL usando Nested Datalog, en particular para la cláusula EXISTS y la información incompleta. En este nuevo formalismo, describimos las tres semánticas propuestas por la comunidad para la cláusula EXISTS (particularmente para los problemas de correlación y substitución), mostramos los supuestos hechos en cada una de ellas y entregamos un menú de estrategias para abordar los problemas de correlación y substitución.