References
[BGW+81] P. A. Bernstein, N. Goodman, E. Wong, C. L. Reeve and J. B. Rothnie. Query processing in a system for distributed databases (SDD1) ACM Transactions on Database Systems, 6(4):602--625, 1981.
[BMSU86] F. Bancilhon, D. Maier, Y. Sagiv and J. D. Ullman. Magic sets and other strange ways to execute logic programs. In Proceedings of the ACM Symposium on Principles of Database Systems, 1--15, 1986.
[BR91] C. Beeri and R. Ramakrishnan. On the power of Magic. Journal of Logic Programming, 10(3&4):255--300, 1991.
[Blo70] B. H. Bloom. Space/time tradeoffs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970.
[CG85] S. Ceri and G. Gottlob. Translating SQL into relational algebra: Optimization, semantics,and equivalence of SQL queries. IEEE Transactions on Software Engineering, 11(4):324--345, 1985.
[DGK82] U. Dayal, N. Goodman, and R. H. Katz. An extended relational algebra with control over duplicate elimination. In Proceedings of the ACM Symposium on Principles of Database Systems, 1982.
[EN94] R. Elmasri and S. B. Navathe. Fundamentals of database systems. Benjamin/Cummings Publishers, 2nd edition, 1994.
[GHK92] S. Ganguly, W. Hasan and R. Krishnamurthy. Query optimization for parallel execution. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1992.
[GM93] G. Graefe and W. J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In Proceedings of the IEEE International Conference on Data Engineering, 1993.
[HCL+90] L. Haas, W. Chang, G. M. Lohman, J. McPherson, P. F. Wilms, G. Lapis, B. Lindsay, H. Pirahesh, M. Carey, and E. Shekita. Starburst midflight: As the dust clears. IEEE Transactionson Knowledgeand Data Engineering, March 1990.
[Hel95] J. M. Hellerstein. Optimization and execution techniques for queries with expensive methods Ph.D. Thesis, University of Wisconsin, August 1995.
[IK84] T. Ibaraki and T. Kameda. Optimal nesting for computing Nrelational joins.
In ACM Transactions on Database Systems, 9(3):482--502, 1984.
[INSS92] Y. Ioannidis, R. Ng, K. Shim and T. K. Sellis. Parametric query optimization. In Proceedings of the International Conference on Very Large Databases (VLDB), 103--114, 1992.
[KBZ86] R. Krishnamurthy, H. Boral, and C. Zaniolo. Optimization of nonrecursive queries. In Proceedings of the International Conference on Very Large Databases (VLDB), 128--137, 1986.
[Klu82] A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM, 29(3):699--717, 1982.
[LMH+85] G. M. Lohman, C. Mohan, L. M. Haas, D. Daniels, B. G. Lindsay, P. G. Selinger and P. F. Wilms. Query processing in R*. In Query Processing in Database Systems, (W. Kim, D. S. Reiner, and D. S. Batory, eds.), SpringerVerlag, 30--47, 1985.
[LNSS93] R. J. Lipton, J. F. Naughton, D. A. Schneider and S. Seshadri. Efficient sampling strategies for relational database operations. Theoretical Computer Science, 116:195--226, 1993.
[MFPR90] I. S. Mumick, S. Finkelstein, H. Pirahesh, and R. Ramakrishnan. Magic is relevant. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1990.
[MP94] I. S. Mumick and H. Pirahesh. Implementation of magicsets in a relational database system. In Proceedings of ACM SIGMOD International Conference on Management of Data, 1994.
[RLK86] J. Rohmer, R. Lescoeur,and J. M. Kerisit. The Alexander method: A technique for the processing of recursive axioms in deductive databases. In New Generation Computing, 4(3):273--285, 1986.
[RSSS94] R. Ramakrishnan, D. Srivastava, S. Sudarshan and P. Seshadri. The CORAL deductive system. The VLDB Journal, Special Issue on Prototypes of Deductive Database Systems, 1994.
[SAC+79] P. G. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access path selection in a relational database management system. In Proceedings of ACM SIGMOD International Conferenceon Managementof Data, 23--34, 1979.
[Sag90] Y. Sagiv. Is there anything better than magic? In Proceedings of the North American Conference on Logic Programming, 235--254, 1990.
[SPL96] P. Seshadri, H. Pirahesh,and T. Y. C. Leung. Decorrelating complex queries. In Proceedings of the Twelfth International Conference on Data Engineering, 1996.
[SS88] S. Sippu and E. SoisalonSoinen. An optimization strategy for recursive queries in logic databases. In Proceedings of the Fourth International Conference on Data Engineering, 1988.
[SS94] P. J. Stuckey and S. Sudarshan. Compiling query constraints. In Proceedingsof the ACM Symposiumon Principles of Database Systems, 1994.
[SSS95] D. Srivastava, P. J. Stuckey and S. Sudarshan. The magic of thetasemijoins. AT&T Bell Laboratories Technical Report, 1995.
[TPCD94] TPC benchmark group. TPCD Draft, December 1994. Information Paradigm. Suite 7, 115 North Wahsatch Avenue, Colorado Springs, CO 80903.
[Yao77] S. B. Yao. Approximating the number of accesses in database organizations. Communications of the ACM, 20(4):260--261, 1977.
6 Заметим, что это условие применимости может всегда удовлетворяться путем выбора в качестве ?2 предиката true.
7 В предположении, что E1 выбирается в качестве первого отношения в порядке сторонней передачи информации.
8 В действительности, при CM-перезаписи используется проекция F на уместные атрибуты, но для простоты изложения мы используем само отношение F. Проекция может быть введена после выполнения шага CMT.
