Stanford InfoLab Publication Server

Expressive Capabilities Description Languages and Query Rewriting Algorithms

Vassalos, V. and Papakonstantinou, Y. (1998) Expressive Capabilities Description Languages and Query Rewriting Algorithms. Technical Report. Stanford InfoLab. (Publication Note: Journal of Logic Programming, Special issue on Logic-Based Heterogeneous Information Systems, Volume 43, Number 1, April 2000.)




Information integration systems have to cope with a wide variety of different information sources, which support query interfaces with very varied capabilities. To deal with this problem, the integration systems need descriptions of the query capabilities of each source, i.e., the set of queries supported by each source. Moreover, the integration systems need algorithms for deciding how a query can be answered given the capabilities of the sources. Finally, they need to translate a query into the format that the source understands. We present two languages suitable for descriptions of query capabilities of sources and compare their expressive power. We also use one of the languages to automatically derive the capabilities description of the integration system itself, in terms of the capabilities of the sources it integrates. We describe algorithms for deciding whether a query "matches" the description and show their application to the problem of translating user queries into source-specific queries and commands. We propose new, improved algorithms for the problem of answering queries using these descriptions. Finally, we identify an interesting class of source capability descriptions, for which our algorithms are much more effcient

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:information integration, mediators, heterogeneous databases, capability-based rewriting, query languages, expressibility
Subjects:Computer Science > Data Integration and Mediation
Projects:Information Integration
Related URLs:Project Homepage
ID Code:331
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:29 Dec 2008 11:53

Download statistics

Repository Staff Only: item control page