×

Lazy structure sharing for query optimization. (English) Zbl 0824.68027

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.
Reviewer: A.L.Buchsbaum

MSC:

68P05 Data structures
68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, J.: Anatomy of LISP. McGraw-Hill Computer Science Series. New York: McGraw-Hill 1978
[2] Boyer, R.S., Moore, J.S.: The sharing of structure in theorem-proving programs. Machine Intelligence7, 101-116 (1972) · Zbl 0249.68032
[3] Cordin, J., Bidoit, M.: A rehabilitation of Robinson’s unification algorithm. In Proc. 9th IFIP World Computer Cong., pp. 909-914 (1983)
[4] Flickinger, D., Pollard, C., Wasow, T.: Structure-sharing in lexical representation. In Proc. 23rd Ann. Mtg. of the Asso. for Computational Linguistics, pp. 262-267, 1985
[5] Greene, D.H., Knuth, D.E.: Mathematics for the analysis of algorithms 2nd edn. Boston: Birkhäuser, 1982
[6] Karttunen, L., Kay, M.: Structure sharing with binary trees. In Proc. 23rd Ann. Mtg. of the Asso. for Computational Linguistics, pp. 133-136a, 1985
[7] Martelli, A., Montanari, U.: Theorem proving with structure sharing and efficient unification. In Proc. 5th Int. Joint Conf. on Artificial Intelligence, pp. 543, 1977
[8] Pereira, F.C.N.: A structure-sharing representation for unification-based grammar functions. In Proc. 23rd Ann. Mtg. of the Asso. for Computational Linguistics, pp 137-144, 1985
[9] Pugh, W.W.: Incremental computation and the incremental evaluation of functional programs. Ph.D. Thesis, Department of Computer Science, Cornell University, 1988
[10] Spitzer, J.M., Levitt, K.N., Robinson, L.: An example of hierarchical design and proof. Commun. ACM21 (12), 1064-1075 (1978) · Zbl 0387.68010 · doi:10.1145/359657.359667
[11] Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM22 (2), 215-225 (1975) · Zbl 0307.68029 · doi:10.1145/321879.321884
[12] Yellin, D.M.: Algorithms for subset testing and finding maximal sets. In Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, pp. 386-92, 1992 · Zbl 0829.68067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.