Accession Number:

ADA278688

Title:

Reformulating Query Plans for Multidatabase Systems

Descriptive Note:

Research rept.

Corporate Author:

UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST

Personal Author(s):

• Hsu, Chu-Nan
• Knoblock, Craig

Report Date:

1993-11-01

Pagination or Media Count:

20.0

Abstract:

A practical heterogeneous, distributed multidatabase system must answer queries efficiently. Conventional query optimization techniques are not adequate here because these techniques are dependent on the database structure, and rely on limited information which is not sufficient in complicated multidatabase queries. This paper presents an automated approach to reformulating query plans to improve the efficiency of multidatabase queries. This approach uses database abstractions, the knowledge about the contents of databases, to reformulate a query plan into a less expensive but semantically equivalent one. We present two algorithms. The first algorithm reformulates subqueries to individual databases, the second algorithm extends the first one and reformulates the entire query plan. Empirical results show that the reformulations can provide significant savings with minimal overhead. The reformulation approach provides a global reduction in the amount of the intermediate data as well as local optimizations on the subqueries. Semantic query optimization, Query reformulation, Multidatabase queries, SIMS.

Descriptors:

• *DATA BASES
• *INTERROGATION
• *MULTIPLE ACCESS
• ALGORITHMS
• GLOBAL
• OPTIMIZATION
• DISTRIBUTED DATA PROCESSING
• APPROACH
• SAVINGS
• SEMANTICS
• EFFICIENCY
• DATA REDUCTION
• HETEROGENEITY

Subject Categories:

• Computer Programming and Software
• Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE