New complexity bounds for evaluation and containment of graph query languages

Abstract

Las bases de datos de grafos han recibido mucho interés en los últimos años, debido a sus aplicaciones en temas como las redes sociales o la Web Semántica. En esta tesis estudiamos lenguajes de consultas que poseen las características navegaciones fundamentales para las distintas aplicaciones de bases de datos de grafos. Estos incluyen la clase de consultas regulares de caminos (RPQs), las cuales chequean si dos nodos están conectados por un camino cuya etiqueta satisface una expresión regular; la clase de las RPQs con inversos (2RPQs), que adicionalmente permiten navegar arcos en la dirección reversa; la clase de las uniones de conjunciones de 2RPQs (UC2RPQs), que resulta de cerrar las 2RPQs bajo las operaciones de join, projección y unión; y la clase de las consultas regulares (RQs) que adicionalmente cierra las UC2RPQs bajo clausura transitiva. En esta tesis demostramos nuevos resultados de complejidad para UC2RPQs y RQs. En la primera parte, estudiamos evaluación de UC2RPQs. Este problema es computacionalmente difícil: NP-completo en general y W[1]-completo en complejidad parametrizada. Esto ha motivado la búsqueda de restricciones que hacen que la evaluación sea tratable o tratable de parámetro fijo. Las más importantes son las clases de UC2RPQs de treewidth acotado, que se pueden evaluar en tiempo polinomial, pero hasta la fecha no se conocen otras restricciones que sean tratables o tratables de parámetro fijo. El resultado principal de esta parte es que la evaluación de UC2RPQs de treewidth acotado módulo equivalencia es tratable de parámetro fijo. Más precisamente, demostramos que, para cada k fijo, existe un algoritmo tratable de parámetro fijo que evalúa UC2RPQs que son equivalentes a alguna UC2RPQ de treewidth a lo más k. También estudiamos el caso cuando la cota k es 1, esto es, la clase de UC2RPQs semánticamente acíclicas, y obtenemos aún más resultados. En particular, demostramos que chequear acaso una UC2RPQ es semánticamente acíclica es decidible y EXPSPACE-completo. En la segunda parte, estudiamos contención de RQs. Las RQs han emergido recientemente como un lenguaje natural para bases de datos de grafos. Las RQs tienen propiedades naturales de clausura, no como las UC2RPQs que no son cerradas bajo clausura transitiva. Además, evaluar RQs no es más difícil que evaluar UC2RPQs (NP-completo). Sin embargo, el problema de contención de RQs aún está abierto. Este problema es decidible, pero sólo cotas no elementales son conocidas. En contraste, es sabido que contención de UC2RPQs es elemental, específicamente, EXPSPACE-completo. El resultado principal de esta parte es que contención de RQs es 2EXPSPACE-completo, y luego, tiene complejidad elemental tal como las UC2RPQs. También estudiamos restricciones de RQs que mejoran la complejidad de evaluación o contención, y algunas extensiones. En particular, demostramos que contención para una generalización natural de RQs para bases de datos relacionales es 2EXPSPACE-completo.

Graph databases have gained renewed interest in recent years, due to their application in areas such as social networks and the Semantic Web. We study graph query languages that provide the fundamental navigational features needed in di erent graph database applications. This includes the class of regular path queries (or RPQs for short), which check whether two nodes are connected by a path whose label satis es a regular expression; the class of two-way RPQs (2RPQs), which additionally enables backward navigation of edges; the class of unions of conjunctive 2RPQs (UC2RPQs), which results from closing 2RPQs under the operations of join, projection, and union; and the class of regular queries (RQs), which additionally closes UC2RPQs under transitive closure. In this thesis, we provide new complexity results for UC2RPQs and RQs. In the rst part, we study query evaluation for UC2RPQs. This problem is known to be computationally hard: NP-complete in combined complexity and W[1]-complete in parameterized complexity. This has motivated the search for restrictions that lead to ( xed-parameter) tractable evaluation. The most prominent restrictions are the classes of UC2RPQs of bounded treewidth, which can be evaluated in polynomial time, but no other tractable or xed-parameter tractable restrictions are known to date. Our main result in this part is that evaluation for UC2RPQs of bounded treewidth modulo equivalence is xed-parameter tractable. More precisely, we show that, for each xed k 1, there is a xed-parameter tractable algorithm that evaluates UC2RPQs that are equivalent to some UC2RPQ of treewidth at most k. We also study the case when the bound k equals 1, that is, the class of semantically acyclic UC2RPQs, and provide further results. In particular, we show that checking whether a UC2RPQ is semantically acyclic is decidable and Expspace-complete. In the second part, we study query containment for RQs. The class of RQs has emerged only recently as a natural graph query language. RQs have natural closure properties, unlike UC2RPQs that are not closed under transitive closure. Moreover, RQs are not harder to evaluate than UC2RPQs (NP-complete). Nevertheless, the containment problem for RQs has been open so far. This problem is decidable, but only nonelementary complexity upper bounds are known. In contrast, query containment for UC2RPQs is known to be elementary, speci cally, Expspace-complete. Our main result in this part is that containment of RQs is 2Expspace-complete, and therefore, it has elementary complexity just like UC2RPQs. We also study restrictions of RQs that help to alleviate the complexity of evaluation or containment, and also some extensions. In particular, we show that containment of a natural generalization of RQs for relational databases is still 2Expspace-complete.