## Abstract

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.

Original language | English |
---|---|

Title of host publication | PODS 2014 - Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems |

Publisher | Association for Computing Machinery |

Pages | 188-199 |

Number of pages | 12 |

ISBN (Print) | 9781450323758 |

DOIs | |

State | Published - 2014 |

Externally published | Yes |

Event | 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014 - Snowbird, UT, United States Duration: 22 Jun 2014 → 27 Jun 2014 |

### Publication series

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

### Conference

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

Country/Territory | United States |

City | Snowbird, UT |

Period | 22/06/14 → 27/06/14 |

## Keywords

- Conjunctive queries
- Conjunctive regular path queries
- Containment
- Datalog
- Tree automata