Answering regular path queries in expressive Description Logics via alternating tree-automata

Expressive Description Logics (DLs) have been advocated as formalisms for modeling the domain of interest in various application areas, including the Semantic Web, data and information integration, peer-to-peer data management, and ontology-based data access. An important requirement there is the ability to answer complex queries beyond instance retrieval, taking into account constraints expressed in a knowledge base. We consider this task for positive 2-way regular path queries (P2RPQs) over knowledge bases in the expressive DL ZIQZIQ. P2RPQs are more general than conjunctive queries, union of conjunctive queries, and regular path queries from the literature. They allow regular expressions over roles and data joins that require inverse paths. The DL ZIQZIQ extends the core DL ALCALC with qualified number restrictions, inverse roles, safe Boolean role expressions, regular expressions over roles, and concepts of the form ∃S.Self∃S.Self in the style of the DL SRIQSRIQ. Using techniques based on two-way tree-automata, we first provide as a stepping stone an elegant characterization of TBox and ABox satisfiability testing which gives us a tight ExpTime bound for this problem (under unary number encoding). We then establish a double exponential upper bound for answering P2RPQs over ZIQZIQ knowledge bases; this bound is tight. Our result significantly pushes the frontier of 2ExpTime decidability of query answering in expressive DLs, both with respect to the query language and the considered DL. Furthermore, by reducing the well known DL SRIQSRIQ to ZIQZIQ (with an exponential blow-up in the size of the knowledge base), we also provide a tight 2ExpTime upper bound for knowledge base satisfiability in SRIQSRIQ and establish the decidability of query answering for this significant fragment of the new OWL 2 standard.