Stanford InfoLab Publication Server

Query Reformulation under Incomplete Mappings

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
Projects:Information Integration
Related URLs:Project Homepage
ID Code:219
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:08 Dec 2008 15:42

Download statistics

Repository Staff Only: item control page