Query processing under GLAV mappings for relational and graph databases

Schema mappings establish a correspondence between data stored in two databases, called source and target respec- tively. Query processing under schema mappings has been investigated extensively in the two cases where each target atom is mapped to a query over the source (called GAV, global-as-view), and where each source atom is mapped to a query over the target (called LAV, local-as-view). The general case, called GLAV, in which queries over the source are mapped to queries over the target, has attracted a lot of attention recently, especially for data exchange. How- ever, query processing for GLAV mappings has been con- sidered only for the basic service of query answering, and mainly in the context of conjunctive queries (CQs) in rela- tional databases. In this paper we study query processing for GLAV mappings in a wider sense, considering not only query answering, but also query rewriting, perfectness (the property of a rewriting to compute exactly the certain an- swers), and query containment relative to a mapping. We deal both with the relational case, and with graph databases, where the basic querying mechanism is that of regular path queries. Query answering in GLAV can be smoothly reduced to a combination of the LAV and GAV cases, and for CQs this reduction can be exploited also for the remaining query processing tasks. In contrast, as we show, GLAV query pro- cessing for graph databases is non-trivial and requires new insights and techniques. We obtain upper bounds for an- swering, rewriting, and perfectness, and show decidability of relative containment.