BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-96-1576
       ENTRY:: December 06, 1996
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Query Reformulation under Incomplete Mappings
        TYPE:: Technical Report
      AUTHOR:: Huyn, Nam
        DATE:: December 1996
       PAGES:: 13
    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.
       NOTES:: [Adminitrivia V1/Prg/19961206]
         END:: STAN//CS-TR-96-1576