Query Reformulation under Incomplete Mappings

Abstract

This paper focuses on some of the important new translatability issues that arise in the problem of interop-eration between two database schemas when mappings between these schemas are inherently more com-plex than traditional views or pure Datalog programs can capture. In many cases, sources cannot beredesigned, and mappings among them exhibit some form of incompleteness under which the question ofwhether a query can be translated across different schemas is not immediately obvious. The notion of query we consider here is the traditional one, in which the answers to a query are required to be denite:answers cannot be disjunctive or conditional and must refer only to domain constants. In this paper, map-pings are modeled by Horn programs that allow existential variables, and queries are modeled by pureDatalog programs. We then consider the problem of eliminating functional terms from the answers to a Horn query where function symbols are allowed. We identify a class of Horn queries called term-bounded that are equivalent to pure Datalog queries. We present an algorithm that rewrites a term-bounded query into an equivalent pure Datalog query. Equivalence is dened here as yielding the samefunction-free answer.1. This work was originally written in October 1994 but has never been published before taking the current form of a technical report.