Huyn, N. (1996) Query Reformulation under Incomplete Mappings. Technical Report. Stanford.
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.
|Item Type:||Techreport (Technical Report)|
|Subjects:||Computer Science > Query Processing|
|Related URLs:||Project Homepage||http://infolab.stanford.edu/serf/|
|Deposited By:||Import Account|
|Deposited On:||25 Feb 2000 16:00|
|Last Modified:||08 Dec 2008 15:42|
Repository Staff Only: item control page