Flodin, S. and Risch, T. (1995). Processing Object-Oriented Queries with Invertible Late Bound Functions. Technical Report LiTH-IDA-R-95-10, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: New demands are put on query processing in Object-Oriented (OO) databases to provide efficient and relationally complete query languages. A flexible OO data model requires overloading and late binding of function names. Relational completeness requires capabilities to handle queries where functions are inverted, i.e. where it is possible to select those objects y that satisfies fn(y)=x where x is known. A system that supports both late binding and inverted functions must be able to solve fn(y)=x for a given x and unknown y when fn is late bound, i.e. the resolvent (implementation of a function name) to apply on y is selected based on the type of y. This combination of late binding and inverted function calls require novel query processing capabilities to fully utilize indexes referenced in late bound function calls. This paper presents an approach to the management of late binding in query processing. The main result is a query processing method where late bound function calls are efficiently executed and optimized for both inverted and regular execution. The proposed solution is based on substituting each late bound function call in the execution plan with a special function, DTR, which dynamically selects the actual resolvent to call. We define the inverse of DTR and its correctness. We show a dramatic execution time improvement by making DTR invertible and by defining its cost model for query optimization. The improvements are verified by performance measurements.
CS Dept TR Overview