Report Number: CS-TR-96-1576
Institution: Stanford University, Department of Computer Science
Title: Query Reformulation under Incomplete Mappings
Author: Huyn, Nam
Date: December 1996
Abstract: This paper focuses on some of the important new
translatability issues that arise in the problem of
interoperation between two database schemas when mappings
between these schemas are inherently more complex than
traditional views or pure Datalog programs can capture. In
many cases, sources cannot be redesigned, and mappings among
them exhibit some form of incompleteness under which the
question of whether 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 definite: answers
cannot be disjunctive or conditional and must refer only to
domain constants. In this paper, mappings are modeled by Horn
programs that allow existential variables, and queries are
modeled by pure Datalog 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 defined here as yielding the
same function-free answer.
http://i.stanford.edu/pub/cstr/reports/cs/tr/96/1576/CS-TR-96-1576.pdf