Lazy Structure Sharing for Query Optimization
Report ID: TR-422-93Author: Buchsbaum, Adam L. / Tarjan, Robert E. / Sundar, Rajamani
Date: 1993-04-00
Pages: 12
Download Formats: |Postscript|
Abstract:
We study lazy structure sharing as a tool for optimizing equivalence testing on complex data types. We investigate a number of strategies for a restricted case of the problem and provide upper and lower bounds on their performance (how quickly they effect ideal configurations of our data structure). In most cases, the bounds provide nontrivial improvements over the na"{i}ve linear-time equivalence-testing strategy that employs no optimization.