Lazy structure sharing for query optimization

Adam L. Buchsbaum, Rajamani Sundar, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review


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 naïve 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.

Original languageEnglish (US)
Pages (from-to)255-270
Number of pages16
JournalActa Informatica
Issue number3
StatePublished - Mar 1995

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Lazy structure sharing for query optimization'. Together they form a unique fingerprint.

Cite this