Lazy structure sharing for query optimization (Q1892716)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Lazy structure sharing for query optimization
scientific article

    Statements

    Lazy structure sharing for query optimization (English)
    0 references
    0 references
    0 references
    0 references
    21 June 1995
    0 references
    We study lazy structure sharing as a tool for optimizing equivalence testing on complex data types. We investigate a number of strategies for implementing lazy structure sharing and provide upper and lower bounds on their performance (how quickly they effect ideal configurations of our data structure). In most cases when the strategies are applied to a restricted case of the problem, the bounds provide nontrivial improvements over the naive linear-time equivalence-testing strategy that employs no optimization. Only one strategy, however, which employs path compression, seems promising for the most general case of the problem.
    0 references
    lazy structure sharing
    0 references
    equivalence testing
    0 references
    complex data
    0 references

    Identifiers