## Resumen

While checking containment of Datalog programs is undecidable, checking whether a Datalog program is contained in a union of conjunctive queries (UCQ), in the context of relational databases, or a union of conjunctive 2-way regular path queries (UC2RPQ), in the context of graph databases, is decidable. The complexity of these problems is, however, prohibitive: 2EXPTIME-complete. We investigate to which extent restrictions on UCQs and UC2RPQs, which have been known to reduce the complexity of query containment for these classes, yield a more "manageable" single-exponential time bound, which is the norm for several static analysis and verification tasks. Checking containment of a UCQ⊖′ in a UCQ ⊖ is NP-hard, in general, but better bounds can be obtained if ⊖ is restricted to belong to a tractable class of UCQs, e.g., a class of bounded treewidth or hypertreewidth. Also, each Datalog program ∏ is equivalent to an infinite union of CQs. This motivated us to study the question of whether restricting ⊖ to belong to a tractable class also helps alleviate the complexity of checking whether ∏ is contained in ⊖. We study such question in detail and show that the situation is much more delicate than expected: First, tractability of UCQs does not help in general, but further restricting ⊖ to be acyclic and have a bounded number of shared variables between atoms yields better complexity bounds. As corollaries, we obtain that checking containment of ∏ in ⊖ is in EXPTIME if ⊖ is of treewidth one, or it is acyclic and the arity of the schema is fixed. In the case of UC2RPQs we show an EXPTIME bound when queries are acyclic and have a bounded number of edges connecting pairs of variables. As a corollary, we obtain that checking whether ∏ is contained in UC2RPQ Γ is in EXPTIME if Γ is a strongly acyclic UC2RPQ. Our positive results for UCQs and UC2RPQs are optimal, in a sense, since slightly extending the conditions turns the problem 2EXPTIME-complete. Copyright ACM.

Idioma original | Inglés |
---|---|

Título de la publicación alojada | PODS 2014 - Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems |

Editorial | Association for Computing Machinery |

Páginas | 188-199 |

Número de páginas | 12 |

ISBN (versión impresa) | 9781450323758 |

DOI | |

Estado | Publicada - 2014 |

Publicado de forma externa | Sí |

Evento | 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014 - Snowbird, UT, Estados Unidos Duración: 22 jun. 2014 → 27 jun. 2014 |

### Serie de la publicación

Nombre | Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems |
---|

### Conferencia

Conferencia | 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014 |
---|---|

País/Territorio | Estados Unidos |

Ciudad | Snowbird, UT |

Período | 22/06/14 → 27/06/14 |