Answering regular path queries in expressive description logics An automata-theoretic appro.pdf

Answering Regular Path Queries in Expressive Description Logics: An Automata-Theoretic Approach ? Diego Calvanese Faculty of Computer Science Free University of Bozen-Bolzano Piazza Domenicani 3, Bolzano, Italy calvanese@inf.unibz.it Thomas Eiter and Magdalena Ortiz Institute of Information Systems Vienna University of Technology Favoritenstra?e 9-11, Vienna, Austria eiter|ortiz@kr.tuwien.ac.at Abstract Expressive Description Logics (DLs) have been advocated as formalisms for modeling the domain of interest in various ap- plication areas. An important requirement is the ability to an- swer complex queries beyond instance retrieval, taking into account constraints expressed in a knowledge base. We con- sider this task for positive existential path queries (which gen- eralize conjunctive queries and unions thereof), whose atoms are regular expressions over the roles (and concepts) of a knowledge base in the expressive DL ALCQIbreg . Using techniques based on two-way tree-automata, we first provide an elegant characterization of TBox and ABox reasoning, which gives us also a tight EXPTIME bound. We then prove decidability (more precisely, a 2EXPTIME upper bound) of query answering, thus significantly pushing the decidabil- ity frontier, both with respect to the query language and the considered DL. We also show that query answering is EXP- SPACE-hard already in rather restricted settings. Introduction Description Logics (DLs) (Baader et al. 2003) are a well- established branch of logics for knowledge representation and reasoning, and the premier logic-based formalism for modeling concepts (i.e., classes of objects) and roles (i.e., binary relationships between classes). They have gained in- creasing attention in different areas including the Seman- tic Web, data and information integration, peer-to-peer data management, and ontology-based data access. In particular, some of the standard Web ontologies from the OWL family are based on DLs (Heflin Hendler 2001). In DLs,