Sesión Lógica y ComputabilidadLógicas de Descripción sobre Grafos de Datos
Juliana Putero
FAMAF - Universidad Nacional de Córdoba, y CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
La tarea de representar y manipular información de manera compacta y eficiente resulta, en general, compleja desde un punto de vista computacional. En este sentido, es de gran interés y utilidad contar con modos eficientes de almacenamiento y con mecanismos que permitan inferir propiedades acerca de dicha información. El desarrollo y estudio de representaciones compactas de datos, como así también de procedimientos eficientes para su manipulación, pueden ser abordados desde un punto de vista formal utilizando herramientas de la lógica. En particular, uno de los enfoques más utilizados en la práctica, es el basado en las llamadas Lógicas de Descripción [1] .
Las Lógicas de Descripción fueron diseñadas con el propósito de describir abstracciones de algún dominio de interés. En general, dichas abstracciones están constituidas por tres componentes principales: Conceptos, que representan conjuntos de elementos; Nombres de Roles, que representan relaciones binarias entre elementos; e Individuos, que representan elementos específicos del dominio.
Por ejemplo, consideremos un dominio de datos sobre la estructura de la currícula de una carrera universitaria. La Lógica de Descripción nos permite construir expresiones de la forma $\exists \mathsf{teaches.Course}$, donde Course es un concepto y teaches es un rol. De esta manera, la expresión caracteriza a “los elementos del dominio que corresponden con individuos que enseñan algún curso”. Este tipo de expresiones de la Lógica de Descripción se combinan luego para definir las bases de conocimiento que proveen descripciones abstractas de la información concreta contenida, por ejemplo, en una base de datos. Una base de conocimiento es un par $K= (T, A)$ denominados TBox y ABox, respectivamente. La TBox contiene las condiciones generales sobre el dominio de datos, mientras que la ABox puede entenderse como una descripción de elementos concretos de dicho dominio. Por ejemplo, expresiones del tipo $\forall \mathsf{teaches.Course} \sqsubseteq \mathsf{Teacher}$ pertenecen a la TBox, ya que denota la propiedad “quienes enseñan cursos son docentes”. Por su parte, una expresión $\mathsf{Mary:Teacher}$ pertenece a la ABox, ya que denota el hecho de que “Mary es docente”. Una vez definida una base de conocimiento sobre alguna Lógica de Descripción en particular, es interesante contar con mecanismos de inferencia eficientes para extraer información a partir de la misma. Por ejemplo, para verificar si un concepto está incluido en otro (tarea conocida como subsunción), o verificar si una base de conocimientos se encuentra libre de contradicciones (conocido como chequeo de consistencia). Para ello, se utilizan métodos lógicos, como pueden ser procedimientos basados en tableaux.
Sin embargo, tal como suele ocurrir a la hora de utilizar cualquier lenguaje lógico, la expresividad del mismo puede resultar insuficiente para el problema que se busca abordar. Por ejemplo, cuando se manipulan grandes cantidades de datos, es interesante comparar ciertos atributos que aparecen en los mismos, como pueden ser la cantidad de horas asignadas a cada estudiante o cada docente en el ejemplo mencionado anteriormente. En los enfoques tradicionales, la capacidad de comparar los valores de cada atributo se encuentra ausente. Es por ello que en este trabajo, y siguiendo las ideas propuestas en [2,3], extendemos lenguajes de descripción tradicionales con operadores que nos permiten comparar atributos de datos entre los elementos del dominio. De esta manera podemos contar con tal información en nuestras bases de conocimiento, interpretadas sobre los llamados Grafos de Datos. A su vez avanzamos con el estudio de mecanismos de inferencia basados en tableaux sobre este nuevo tipo de bases de conocimiento. Este enfoque nos permite además, estudiar la complejidad computacional de realizar inferencia con estas lógicas, como así también buscar fragmentos que admiten algoritmos eficientes de razonamiento.
Trabajo en conjunto con: Valentin Cassano (Universidad Nacional de Río Cuarto y CONICET, Argentina) y Raul Fervari (Universidad Nacional de Córdoba y CONICET, Argentina).
Referencias
[1] Baader, F., Horrocks, I., Lutz, C., & Sattler, U. An Introduction to Description Logic. Cambridge: Cambridge University Press (2017).
[2] Kostylev, E., Reutter, J., & Vrgoc, D. XPath for DL Ontologies. Proceedings of the AAAI Conference on Artificial Intelligence, 29 (2015).
[3] Areces, C., & Fervari, R. Axiomatizing Hybrid XPath with Data. Logical Methods in Computer Science (LMCS), volume 17, issue 3, 2021.