New complexity bounds for evaluating CRPQs with path comparisons

Abstract

En muchos problemas que surgen en el contexto de consultar información en bases de datos estructuradas sobre grafos (como encontrar asociaciones semanticas en grafos RDF, encontrar emparejamientos exactos o aproximados the patrones de texto, realizar alineación de secuencias de texto, etc.) es un requerimiento común el buscar entidades unidas por secuencias de etiquetas relacionales de acuerdo a un patrón regular. Para este propósito, el lenguaje de consulta $\CRPQ(\S)$ ha sido propuesto para extender la altamente estudiada clase de consultas conjuntivas por caminos regulares (CRPQs por su sigla en inglés), la cual es insuficiente para esta tarea, realizando comparación de caminos con relaciones en la clase $\S$.\\ Poco es conocido acerca de la complejidad computacional precisa de la evaluación de consultas en $\CRPQ(\S)$ cuando $\S$ es una relación de interés por aparecer naturalmente en aplicaciones en bases de datos, como lo son \emph{subsecuencia} ($\ss$), \emph{sufijo} $(\suff)$ y \emph{subpalabra} ($\sw$). Esta pregunta es consecuentemente estudiada en esta tesis, proporcionando nuevas cotas de complejidad para la evaluación de consultas en los lenguajes $\CRPQ(\ss)$, $\CRPQ(\suff)$ y $\CRPQ(\sw)$. Se muestra que el primer lenguaje es dificil de ser practicable, construyendo una consulta en él cuya complejidad de evaluación es $\NP$-completo. Se muestra también que la evaluación de consultas en los últimos dos lenguajes puede realizarse en $\PSPACE$, mediante la reducción del problema a \emph{ecuaciones de palabras con restricciones regulares}. Adicionalmente, se muestra que la classe $\CRPQ(\suff)$ es práctica, construyendo un algoritmo de evaluación cuya complejidad, cuando la consulta es considerada una constante, está en $\NLOGSPACE$ , la cuál es una complejidad de evaluación estandar en este contexto.\\ Esta tesis plantea además interesantes preguntas teóricas sobre ecuaciones de palabras con restricciones regulares. Más precisamente, cuál es la complejidad de resolver ecuaciones fijas con restricciones como entrada, la cual es una pregunta abierta en la literatura al leal saber y entendimiento del autor. Un resultado es establecido para el caso más simple, mostrando una clase de ecuaciones cuya satisfacibilidad con restricciones regulares puede ser decidida en $\NLOGSPACE$.