An Overwiew of Evolution of Lexical Query Optimization Techniques
https://doi.org/10.15514/ISPRAS-2012-23-12
Abstract
The presented overview is concerned with lexical query optimization and covers papers published in the last four decades. The paper consists of five sections. The first section – Introduction – classifies query optimization techniques into semantic optimizations and lexical optimizations. Semantic optimizations usually relies on data integrity rules that are stores within metadata part of databases, and on data statistics. This kind of optimizations is discussed in many textbooks and papers. Lexical optimizations (more often called rewriting) use only a text of query and no other information about database and its structure. Lexical optimizations are further classified into query transformations, query amelioration, and query reduction. The second section of the paper discusses techniques of query transformation such as predicate pushdown, transformation of nested query into query with joins, etc. Query amelioration is a topic of the third section with a focus on magic set optimizations. The forth section covers query reduction optimizations. The section briefly describes traditional approaches (such as tableau -based) are briefly described and considers in more details three new algorithms proposed by authors. The fifth section concludes the paper.
About the Authors
N. A. Mendkovich
OOO «FREEnet Group», Moscow
Russian Federation
Russian Federation
S. D. Kuznetsov
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. Re C., Simeon J., Fernandez M. F. A Complete and Efficient Algebraic Compiler for XQuery. Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April, 2006, Atlanta, GA, USA: IEEE Computer Society, 2006. Lecture Notes on Computer Society, 2007. Volume 4797. Pp. 81-96.
2. Palermo F. A data base search problem. Proceedings of the 4th Symposium on Computer and Information Sciences, Virginia, USA, 1972. Restion: AFIPS Press, 1972. Pp. 67-101.
3. Ghelli G., Onose N., Rose K., Siméon J. XML Query Optimization in the Presence of Side Effects. Proceedings of the 2008 ACM SIGMOD international conference on Management of data. New York, USA, 2008. New York: ACM, 2008. Pp. 339-352.
4. Jarke M., Koch J. Query Optimization in Database Systems. ACM Computing Surveys (CSUR), 1984. March, Volume 16, Issue 2. Pp. 111-152.
5. Lukichev M., Barashev D. XML Query Algebra for Cost-based Optimization. SYRCODIS*07 The Fourth Spring Young Researchers Colloquium on Databases and Information Systems, Moscow, May 31 - June 1, 2007. http://ceur-ws.org/Vol-256/ (in Russian).
6. Mannino M. V., Chu P., Sager T. Statistical profile estimation in database systems. ACM Computing Surveys, 1988. September, Volume 20, Issue 3. Pp. 191-221.
7. Lukichev M. S. Optimizacija zaprosov v slabostrukturirovannoj modeli dannyh [Query optimization in a semistructured data model]. Dissertacija kandidata fiziko-matematicheskih nauk: 05.13.11. Sankt-Peterburg: Sankt-Peterburgskij Gosudarstvennyj Universitet, 2009. 120 s. (in Russian).
8. Ionnidis Y. E. Query Optimization. The Computer Science and Engineering Handbook. Boca Raton: CRC Press, 1996. Pp. 1038-1054.
9. Smith M., Chang P. Y. W. Optimizing the performance of a relational algebra database interface. Communications for the ACM, October, 1975. Volume 18, Issue 10. Pp. 568-579.
10. Chaudhari S. An Overview of Query Optimization in Relational Systems. Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. New York: SIGMOD, 1998. Pp. 34-43.
11. Hall P. A. V. Optimization of single expressions in a relational data base system. IBM Journal of Research and Development. Volume 20, Number 3, 1976. Pp. 244-257.
12. Kuznetsov S.D. Metody optimizacii vypolnenija zaprosov v reljacionnyh SUBD [Query optimization techniques for relational DBMSs]. http://www.citforum.ru/database/articles/art_26.shtml (in Russian).
13. Chaudhuri S., Shim K. Including Group-By in Query Optimization. Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. San Francisco: Morgan Kaufmann Publishers Inc., 1994. Pp. 354-366.
14. Graefe G. Query Evaluation Techniques for Large Databases. ACM Computing Surveys, 1993. Volume 25, Issue 2. P. 73-169.
15. Levy Y., Mumick I. S., Sagiv Y. Query Optimization by Predicate Move Around. Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. Morgan Kaufmann Publishers Inc., 1994. Pp. 96-107.
16. Date C. J. Vvedenie v sistemy baz dannyh [An Introduction to Database Systems]. Moskva – Sankt-Peterburg – Kiev: Izdatel'skij dom «Vil'jams», 2001. 1072 s. (in Russian).
17. Wong E., Youssefi K. Decomposition - a strategy for query processing. ACM Transactions On Database Systems, September 1976. Volume 1, Number 3. Pp. 223–241.
18. Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. Second Edition. New Jersey: Prentice Hall International, 1999. 666 pp.
19. Yannakakis M. Algorithms for acyclic database schemes. Proceedings of Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981. New York: IEEE Press, 1981. Pp. 82-94.
20. Ramakrishnan R., Gehrcke J. Database System Management. 2nd Edition. Singapore: The McGraw-Hill Book Co, 2000. 906 pp.
21. McMahan B., Porter P., Pan G., M. Y. Vardi. Projection Pushing Revisited. Proceedings of the 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. Berlin: Springer, 2004. Pp. 441-458.
22. Karayannidis N. Query Optimization Bibliography, http://www.dbnet.ece.ntua.gr/~nikos/edith/qopt_bibl/.
23. McMahan B. J. Structural Heuristics for Query Optimization. Master of Science Degree Thesis. Houston: Rice University, 2004. 64 pp.
24. MySQL 5.5 Reference Manual. Chapter 7. Optimization. http://dev.mysql.com/doc/refman/5.5/en/optimization.html.
25. Kim W. On optimizing an SQL-Like Nested Query. ACM Transactions on Database Systems (TODS), September, 1982. Volume 7 Issue 3. Pp. 443-469.
26. Vellin L., Tomson Dzh. MySQL. Uchebnoe posobie [Textbook on MySQL]. Perevod s anglijskogo. M.: Izdatel'skij dom «Vil'jams», 2005. 292 c.
27. Kisessling W. On Semantic Reefs and Efficient Processing of Correlation Queries Revisited. Proceedings of 11th International Conference for Very Large Data Bases. August 21-23, Stockholm, Sweden, 1985. New York: Morgan Kaufmann, 1985. Pp. 241-250.
28. Upgrading from Oracle Database 10 g to 11 g: What to expect from the Optimizer. An Oracle White Paper, November 2009. Redwood Shores: Oracle Corporation, 2009. 36 pp.
29. Ganski R. A., Wong H. K. T. Optimization of Nested SQL Queries Revisited. Proceedings of the ACM SIGMOD international conference on Management of data. San Francisco, May 1987. New York: ACM, 1987. Pp. 23-33.
30. Comparison of Materialized Views & Analytic Workspaces in Oracle Database 11 g. An Oracle White Paper, March 2008. Redwood Shores: Oracle Corporation, 2008. 27 pp.
31. Muralikrishna M. Improved unnesting algorithms for join aggregate SQL queries. Proceedings of the 18th International Conference on Very Large Data Bases, August 23-27, Vancouver, Canada, 1992. San Francisco: Morgan Kaufmann Publishers Inc., 1992. Pp. 91-102.
32. Markl V., Lohman G. M., Raman V. LEO: An autonomic query optimizer for DB2. IBM System Journal, 2003. V. 42, № 1. Pp. 98-106.
33. Khaitan P., Satish K. M., S. B. Korra, S. K. Jena Improved query plans for unnesting nested SQL queries. Proceedings of 2nd International Conference on Computer Science and its Applications, December 10-12, South Korea, 2009. Jeju Island : IEEE, 2009. Pp. 147-152.
34. PostgreSQL 8.1.19 Documentation. Chapter VII: Internals, http://www.postgresql.org/docs/8.1/interactive/internals.html.
35. Fegaras L., D. Levine, S. Bose, V. Chaluvadi. Query processing of streamed XML data. Proceedings of the eleventh international conference on Information and knowledge management. ACM Press, New York, USA, 2002. Berlin: Springer, 2004. Pp. 195-215.
36. Ioannidis Y. The History of Histograms. Proceedings of 29th International Conference on Very Large Data Bases, September 9-12, 2003, Berlin, Germany. Berlin: Morgan Kaufmann, 2003. Pp. 19-30.
37. May N., Moerkotte G. Normalization and Translation of XQuery. Advanced Applications and Structures in XML Processing: Label Streams, Semantics Utilization and Data Query Technologies. Hershey: Igi Global Publishing, 2010. Pp. 283-307.
38. Halevy Y. Answering queries using views: A survey. The International Journal on Very Large Data Bases, December 2001. Volume 10 Issue 4. Pp. 270-294.
39. Pirahesh H., Hellerestein J., Hasan W. Extensible/rule based query rewrite optimization in Starburst. ACM SIGMOD Record, June 1, 1992. Volume 21, Issue 2. Pp. 39-48.
40. Braga D., Ceri S., Grossniklaus M. Join Methods and Query Optimization. Lecture Notes on Computer Science, 2010. Issue 5950. Pp. 188-210.
41. MySQL Nested-Loop Join Algorithms, http://dev.mysql.com/doc/refman/5.5/en/nested-loop-joins.html.
42. Query Optimization in Oracle Database 10g Release 2. An Oracle White Paper, June 2005. Redwood Shores: Oracle Corporation, 2005. 31 pp.
43. Bancilhon F., Maierl D., Sagiv Y., Ullman J. D. Magic Sets and Other Strange Ways to Implement Logic Programs. Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Cambridge, Massachusetts, March 24-26, 1986. New York: ACM, 1986. Pp. 1-15.
44. Smirnov S. N., Zadvor'ev I. S. Rabotaem s Oracle: Uchebnoe posobie [Working with Oracle: textbook]. M: Gelios ARV, 2002. 496 s. (in Russian).
45. Mumick S., Finkelsteint S. J., Pirahesh H., Ramakrishnan R. Magic Conditions. ACM Transactions on Database Systems (TODS), March 1996. Volume 21 Issue 1. Pp. 107-155.
46. Shenoy S. T., Ozsoyoglu Z. M. A System for Semantic Query Optimization. SIGMOD Record, 1987. Volume 16, Number 3. Pp. 181-195
47. Mumick I. S., Finkelstein S. J., Pirahesh H., Ramakrishnan R. Magic is Relevant. Proceedings of the 1990 ACM SIGMOD international conference on Management of data. New York: ACM, 1990. Pp. 247-258.
48. Geng K., Dobbie G., Meng Y. Survey of XML Semantic Query Optimization. Proceedings 4th International Conference on Internet Computing for Science and Engineering (ICICSE), Harbin, 2009. Washington D. C.: IEEE Computer Society, 2009. Pp. 297-300
49. Jezek K., Zima M. Query optimization in deductive programs with aggregates. Proceeding of the 4th International Conference Information Systems Modelling, Ostrava: MARQ, 2001. Pp. 85-92.
50. Zverev D. L. Optimizacija potokov prostyh SQL-zaprosov [Optimization of simple SQL query’ streams]: Dissertacija kandidata tehnicheskih nauk: 05.13.11. Sankt-Peterburg: Sankt-Peterburgskij Gosudarstvennyj Universitet Ajerokosmicheskogo Priborostroenija, 2005. 169 s. (in Russian).
51. Seshadri P., Hellerstein J. M., Pirahesh H., Cliff Leung T. Y., Ramakrishnan R., Srivastava D., Stuckey P. J., Sudarshan S. Cost-Based Optimization for Magic: Algebra and Implementation. ACM SIGMOD Record, June 1996. Volume 25, Issue 2, Pp. 28-33.
52. XQuery 1.0 and XPath 2.0 Formal Semantics. World Wide Web Consortium (W3C), W3C Recommendation, 2007..
53. Sagiv Y. Is there anything better than magic?. Logic Programming, Proceedings of the 1990 North American Conference, Austin, Texas, October 29 - November 1, 1990. Austin: MIT Press 1990. Pp. 235-254.
54. Deutsch A., V. Tannen XML queries and constraints, containment and reformulation. Theoretical Computer Science, 2005. № 336. Pp. 57-87.
55. Sippu S., Soisalon-Soininen E. An Analysis of Magic Sets and Related Optimization Strategies for Logic Queries. Journal of the ACM, November 1996. Volume 43, № 6. Pp. 1046-1088.
56. Fan W., Xu J. Y., Ding B., Qin L., Rastogi R. Query Translation from XPath to SQL in the Presence of Recursive DTDs. Very Large Data Bases Journal, 2009. Issue 18. Pp. 857-883.
57. Azevedo P. J. Magic sets with full sharing. The Journal of Logic Programming, 1997. Volume 30, № 3. Pp. 223-237.
58. Barashev D. V., Gorshkova E. A., Novikov B. A. Optimizacija predstavlenija XML dokumentov v reljacionnoj baze dannyh [Optimization of XML document’s representation within a relational database]. Vtoraja Vserossijskaja nauchnaja konferencija. Jelektronnye biblioteki. Perspektivnye metody i tehnologii, jelektronnye kollekcii. 26-28 sentjabrja, Protvino, 2000. C. 224-229 (in Russian).
59. Faber W., Greco G., Leone N. Magic Sets and their application to data integration. Journal of Computer and System Sciences, June 2007. Volume 73, Issue 4. Pp. 584-609.
60. Manolescu I., Florescu D., Kossmann D. Answering xml queries on heterogeneous data sources. Proceedings of the 27th International Conference on Very Large Data Bases, San Francisco, 2001. San Francisco: Morgan Kaufmann Publishers Inc., 2001. Pp.241-250.
61. Ruckhaus E., Ruiz E., Vidal M. E. OnEQL: An Ontology Efficient Query Language Engine for the Semantic Web. Proceedings of the Workshop on Applications of Logic Programming to the Web, Semantic Web and Semantic Web Services (ALPSWS), Porto, Portugal, September 13th, 2007. Porto: CEUR Workshop Proceedings, 2007. Pp. 65-88.
62. Krishnamurthy R., Kaushik R., Naughton J. XML-SQL query translation literature: The state of the art and open problems. XML Database Symposium (XSym 2003) at VLDB 2003. Berlin, September 2003. Lecture Notes in Computer Science, Volume 2824, 2003. Pp. 1-18.
63. Alviano M., Faber W., Greco G., Leone N. Magic Sets for Disjunctive Datalog Programs. Artificial Intelligence, 2012. Volume 187. Pp. 156-192.
64. Cluet S., Moerkotte G. Nested queries in object bases. Proceedings of the 4th International Workshop on Database Programming Languages: Object Models and Language. Manhattan, New York City, USA, 30 August-1 September, 1993. London: Springer-Verlag, 2004. Pp. 226-242.
65. Almendros-Jiménez M., Becerra-Terón A., Enciso-Banos F. J. Magic Sets for the XPath Language. Journal of Universal Computer Science, 2006. Volume 12, № 11. Pp. 1651-1678.
66. Steenhagen H. J., Apers P. M. G., Blanken H.M., de By R. A. From nested-loop to join queries in OODB. Proceedings of the 20th International Conference on Very Large Data Bases, 1994. Santiago: Morgan Kaufman, 1994 P. 618-629.
67. Ozcan F., Seemann N., Wang L. XQuery Rewrite Optimization in IBM DB2 pureXML. IEEE, Data Engineering Bulletin, December 2008. Volume 34, Number 4. Pp. 25-32.
68. Frasincar F., Houben G.-J., Pau C. XAL: An algebra for XML query optimization. Proceedings of the 13th Australasian Database Conference, Australian Computer Society, Inc. Darlinghurst, Australia, 2002. Volume 5. Melbourne: Australian Computer Society, 2002. Pp. 49-56.
69. Kolaitis P. G., Martin D.L., Thakur M.N. On the complexity of the containment problem for conjunctive queries with built-in predicates. Proceeding of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA, June 1-3, 1998. New York: ACM, 1998. Pp. 197-204.
70. May N., Helmer S., Moerkotte G. Strategies for Query Unnesting in XML Databases. ACM Transactions on Database Systems (TODS) 2006. Volume 31, Issue 3. Pp. 968-1013.
71. Benedikt M., Gottlob G. The Impact of Virtual Views on Containment. Proceedings of the The Very Large Data Bases, September 2010. Volume 3 Issue 1-2. Pp. 297-308.
72. Re C., Simeon J., Fernandez M. F. A Complete and Efficient Algebraic Compiler for XQuery. Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April, 2006, Atlanta, GA, USA: IEEE Computer Society, 2006. Lecture Notes on Computer Society, 2007. Volume 4797. Pp. 81-96.
73. Kolaitis P. G., Vardi M. Conjunctive-query containment and constraint satisfaction. Proceeding of the 17th ACM SIGACT-SIGMOD-SIGART SIGART Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA, June 1-3, 1998. New York: ACM, 1998. Pp. 205-213.
74. Ghelli G., Onose N., Rose K., Siméon J. XML Query Optimization in the Presence of Side Effects. Proceedings of the 2008 ACM SIGMOD international conference on Management of data. New York, USA, 2008. New York: ACM, 2008. Pp. 339-352.
75. Kolaitis P. G., Vardi M. Conjunctive-Query Containment and Constraint Satisfaction. Journal of Computer and System Sciences, 2000. № 61. Pp. 302-332.
76. Lukichev M., Barashev D. XML Query Algebra for Cost-based Optimization. SYRCODIS*07 The Fourth Spring Young Researchers Colloquium on Databases and Information Systems, Moscow, May 31 - June 1, 2007. http://ceur-ws.org/Vol-256/ (in Russian).
77. Goldstein J., Larson P.-A. Optimization Queries Using Materialized Views: A Practical Scalable Solution. ACM SIGMOD Record, June 2001. Volume 30 Issue 2. Pp.331-342.
78. Lukichev M. S. Optimizacija zaprosov v slabostrukturirovannoj modeli dannyh [Query optimization in a semistructured data model]. Dissertacija kandidata fiziko-matematicheskih nauk: 05.13.11. Sankt-Peterburg: Sankt-Peterburgskij Gosudarstvennyj Universitet, 2009. 120 s. (in Russian).
79. Pashinin O. V. Optimizacija zaprosov k bazam dannyh [Optimization of queries to relational databases] . Matematicheskie struktury i modelirovanie. Vypusk 17, 2007. S. 100-107 (in Russian).
80. Smith M., Chang P. Y. W. Optimizing the performance of a relational algebra database interface. Communications for the ACM, October, 1975. Volume 18, Issue 10. Pp. 568-579.
81. Chandra K., Merlin P. M. Optimal Implementation of Conjunctive Queries in Relational Databases. Proceedings of the 9th annual ACM symposium on Theory of computing, May, 1977. New York: ACM, 1977. Pp. 77-90.
82. Hall P. A. V. Optimization of single expressions in a relational data base system. IBM Journal of Research and Development. Volume 20, Number 3, 1976. Pp. 244-257.
83. Stroet J. W. M., Engmann R. Manipulation of expressions in a relational algebra. Information Systems, 1979. Volume 4, Issue 4. Pp. 195-203.
84. Chaudhuri S., Shim K. Including Group-By in Query Optimization. Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. San Francisco: Morgan Kaufmann Publishers Inc., 1994. Pp. 354-366.
85. Aho V., Sagiv Y., Ullman J. D. Equivalences among relational expressions. Society for Industrial and Applied Mathematics Journal on Computing, 1979. Volume 8, Issue 2. Pp. 218-246.
86. Levy Y., Mumick I. S., Sagiv Y. Query Optimization by Predicate Move Around. Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. Morgan Kaufmann Publishers Inc., 1994. Pp. 96-107.
87. Aho V., Sagiv Y., Ullman J. D. Efficient optimization of a class of relational expressions. Journal ACM Transactions on Database Systems (TODS), December 1979. Volume 4, Issue 4. Pp.435-454.
88. Wong E., Youssefi K. Decomposition - a strategy for query processing. ACM Transactions On Database Systems, September 1976. Volume 1, Number 3. Pp. 223–241.
89. Sagiv Y., Yannakakis M. Equivalences among relational expressions with the union and difference operators. Journal of the ACM, October 1980. Volume 27, Issue 4. Pp. 633-655.
90. Yannakakis M. Algorithms for acyclic database schemes. Proceedings of Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981. New York: IEEE Press, 1981. Pp. 82-94.
91. 2.1.2 How MySQL Optimizes WHERE Clauses http://dev.mysql.com/doc/refman/5.5/en/where-optimizations.html.
92. McMahan B., Porter P., Pan G., M. Y. Vardi. Projection Pushing Revisited. Proceedings of the 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. Berlin: Springer, 2004. Pp. 441-458.
93. Prilozhenie PostgreSQL 8.3.3., http://www.postgresql.org/download/. Adres fajla, soderzhashhego obsuzhdaemyj kod, v arhive postgresql-8.3.3\src\backend\optimizer\util\predtest.c.
94. McMahan B. J. Structural Heuristics for Query Optimization. Master of Science Degree Thesis. Houston: Rice University, 2004. 64 pp.
95. Veitch E. W. A Chart Method for Simplifying Truth Functions. ACM Annual Conference/Annual Meeting: Proceedings of the 1952 ACM Annual Meeting. Pittsburg: ACM, NY, 1952. Pp. 127-133.
96. Kim W. On optimizing an SQL-Like Nested Query. ACM Transactions on Database Systems (TODS), September, 1982. Volume 7 Issue 3. Pp. 443-469.
97. Karnaugh M. The Map Method for Synthesis of Combinational Logic Circuits. Transactions of the American Institute of Electrical Engineers, November 1953. Part I, № 72 (9). Pp. 593-599.
98. Kisessling W. On Semantic Reefs and Efficient Processing of Correlation Queries Revisited. Proceedings of 11th International Conference for Very Large Data Bases. August 21-23, Stockholm, Sweden, 1985. New York: Morgan Kaufmann, 1985. Pp. 241-250.
99. Quin W. V. On Cores and Prime Implicants of Truth Functions. American Mathematics Monthly, 1959. V. 66, № 9. P. 755-760.
100. Ganski R. A., Wong H. K. T. Optimization of Nested SQL Queries Revisited. Proceedings of the ACM SIGMOD international conference on Management of data. San Francisco, May 1987. New York: ACM, 1987. Pp. 23-33.
101. McCluskey E. J. Minimization of Boolean Functions. The Bell System Technical Journal, November 1956. V. 35, Issue 5. Pp. 1236-1249.
102. Muralikrishna M. Improved unnesting algorithms for join aggregate SQL queries. Proceedings of the 18th International Conference on Very Large Data Bases, August 23-27, Vancouver, Canada, 1992. San Francisco: Morgan Kaufmann Publishers Inc., 1992. Pp. 91-102.
103. [87]. Wu M.-C. Query Optimizatiom for Selecting Using Bitmaps. ACM SIGMOD Record, June 1999. Volume 28 Issue 2. Pp. 227-238.
104. Khaitan P., Satish K. M., S. B. Korra, S. K. Jena Improved query plans for unnesting nested SQL queries. Proceedings of 2nd International Conference on Computer Science and its Applications, December 10-12, South Korea, 2009. Jeju Island : IEEE, 2009. Pp. 147-152.
105. Das Sarma A., Theobald M., Widom J. Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases. Technical Report. Stanford, 2007. http://ilpubs.stanford.edu:8090/800/.
106. Fegaras L., D. Levine, S. Bose, V. Chaluvadi. Query processing of streamed XML data. Proceedings of the eleventh international conference on Information and knowledge management. ACM Press, New York, USA, 2002. Berlin: Springer, 2004. Pp. 195-215.
107. Tarasenko P. F., Buharova M. F. Tehnologija «The Reporter» dlja postroenija otchetov po bazam dannyh [The Reporter technology for database reporting]. Vestnik Tomskogo Gosudarstvennogo Universiteta, № 275, aprel' 2002. S. 167-176 (in Russian).
108. May N., Moerkotte G. Normalization and Translation of XQuery. Advanced Applications and Structures in XML Processing: Label Streams, Semantics Utilization and Data Query Technologies. Hershey: Igi Global Publishing, 2010. Pp. 283-307.
109. Mendkovich N., Kuznetsov S. New Algorithms for Lexical Query Optimization. Proceedings of the 31st International Conference on Information Technology Interfaces. Cavtat/Dubrovnik, Croatia, June 22-25, 2009. Zagreb: University of Zagreb, 2009. Pp. 187-192.
110. Pirahesh H., Hellerestein J., Hasan W. Extensible/rule based query rewrite optimization in Starburst. ACM SIGMOD Record, June 1, 1992. Volume 21, Issue 2. Pp. 39-48.
111. Kuznetsov S. D., Mendkovich N. A. Novye algoritmy leksicheskoj optimizacii zaprosov [New Algorithms for Lexical Query Optimization]. Modeli i analiz informacionnyh sistem, 2009. T. 16, № 4. S. 22-33 (in Russian).
112. MySQL Nested-Loop Join Algorithms, http://dev.mysql.com/doc/refman/5.5/en/nested-loop-joins.html.
113. Mendkovich N. A., Kuznetsov S. D. Optimizacija kon#junktov uslovij v sostave zaprosov [Optimization of query condition’ conjucts]. Modeli i analiz informacionnyh sistem, 2011. T. 18, № 3. S. 144-154 (in Russian).
114. Bancilhon F., Maierl D., Sagiv Y., Ullman J. D. Magic Sets and Other Strange Ways to Implement Logic Programs. Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Cambridge, Massachusetts, March 24-26, 1986. New York: ACM, 1986. Pp. 1-15.
115. Bellamkonda S., Ahmed R., Witkowski A., Amor A., Zait M., Lin Ch.-Ch. Enhanced Subquery Optimizations in Oracle /. Proceedings of the 35th international conference on Very large data base, August 2009. Volume 2 Issue 2. Pp. 1366-1377.
116. Mumick S., Finkelsteint S. J., Pirahesh H., Ramakrishnan R. Magic Conditions. ACM Transactions on Database Systems (TODS), March 1996. Volume 21 Issue 1. Pp. 107-155.
117. Chaudhuri S. Query Optimizers: Time to Rethink the Contract?. Proceedings of the ACM SIGMOD International Conference on Management of Data, Providence, Rhode Island, USA, June 29 - July 2, 2009. New York: ACM, 2009. Pp. 961-968.
118. Mumick I. S., Finkelstein S. J., Pirahesh H., Ramakrishnan R. Magic is Relevant. Proceedings of the 1990 ACM SIGMOD international conference on Management of data. New York: ACM, 1990. Pp. 247-258.
119. Jezek K., Zima M. Query optimization in deductive programs with aggregates. Proceeding of the 4th International Conference Information Systems Modelling, Ostrava: MARQ, 2001. Pp. 85-92.
120. Seshadri P., Hellerstein J. M., Pirahesh H., Cliff Leung T. Y., Ramakrishnan R., Srivastava D., Stuckey P. J., Sudarshan S. Cost-Based Optimization for Magic: Algebra and Implementation. ACM SIGMOD Record, June 1996. Volume 25, Issue 2, Pp. 28-33.
121. Sagiv Y. Is there anything better than magic?. Logic Programming, Proceedings of the 1990 North American Conference, Austin, Texas, October 29 - November 1, 1990. Austin: MIT Press 1990. Pp. 235-254.
122. Sippu S., Soisalon-Soininen E. An Analysis of Magic Sets and Related Optimization Strategies for Logic Queries. Journal of the ACM, November 1996. Volume 43, № 6. Pp. 1046-1088.
123. Azevedo P. J. Magic sets with full sharing. The Journal of Logic Programming, 1997. Volume 30, № 3. Pp. 223-237.
124. Faber W., Greco G., Leone N. Magic Sets and their application to data integration. Journal of Computer and System Sciences, June 2007. Volume 73, Issue 4. Pp. 584-609.
125. Ruckhaus E., Ruiz E., Vidal M. E. OnEQL: An Ontology Efficient Query Language Engine for the Semantic Web. Proceedings of the Workshop on Applications of Logic Programming to the Web, Semantic Web and Semantic Web Services (ALPSWS), Porto, Portugal, September 13th, 2007. Porto: CEUR Workshop Proceedings, 2007. Pp. 65-88.
126. Alviano M., Faber W., Greco G., Leone N. Magic Sets for Disjunctive Datalog Programs. Artificial Intelligence, 2012. Volume 187. Pp. 156-192.
127. Almendros-Jiménez M., Becerra-Terón A., Enciso-Banos F. J. Magic Sets for the XPath Language. Journal of Universal Computer Science, 2006. Volume 12, № 11. Pp. 1651-1678.
128. Ozcan F., Seemann N., Wang L. XQuery Rewrite Optimization in IBM DB2 pureXML. IEEE, Data Engineering Bulletin, December 2008. Volume 34, Number 4. Pp. 25-32.
129. Kolaitis P. G., Martin D.L., Thakur M.N. On the complexity of the containment problem for conjunctive queries with built-in predicates. Proceeding of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA, June 1-3, 1998. New York: ACM, 1998. Pp. 197-204.
130. Benedikt M., Gottlob G. The Impact of Virtual Views on Containment. Proceedings of the The Very Large Data Bases, September 2010. Volume 3 Issue 1-2. Pp. 297-308.
131. Kolaitis P. G., Vardi M. Conjunctive-query containment and constraint satisfaction. Proceeding of the 17th ACM SIGACT-SIGMOD-SIGART SIGART Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA, June 1-3, 1998. New York: ACM, 1998. Pp. 205-213.
132. Kolaitis P. G., Vardi M. Conjunctive-Query Containment and Constraint Satisfaction. Journal of Computer and System Sciences, 2000. № 61. Pp. 302-332.
133. Goldstein J., Larson P.-A. Optimization Queries Using Materialized Views: A Practical Scalable Solution. ACM SIGMOD Record, June 2001. Volume 30 Issue 2. Pp.331-342.
134. Pashinin O. V. Optimizacija zaprosov k bazam dannyh [Optimization of queries to relational databases] . Matematicheskie struktury i modelirovanie. Vypusk 17, 2007. S. 100-107 (in Russian).
135. Chandra K., Merlin P. M. Optimal Implementation of Conjunctive Queries in Relational Databases. Proceedings of the 9th annual ACM symposium on Theory of computing, May, 1977. New York: ACM, 1977. Pp. 77-90.
136. Stroet J. W. M., Engmann R. Manipulation of expressions in a relational algebra. Information Systems, 1979. Volume 4, Issue 4. Pp. 195-203.
137. Aho V., Sagiv Y., Ullman J. D. Equivalences among relational expressions. Society for Industrial and Applied Mathematics Journal on Computing, 1979. Volume 8, Issue 2. Pp. 218-246.
138. Aho V., Sagiv Y., Ullman J. D. Efficient optimization of a class of relational expressions. Journal ACM Transactions on Database Systems (TODS), December 1979. Volume 4, Issue 4. Pp.435-454.
139. Sagiv Y., Yannakakis M. Equivalences among relational expressions with the union and difference operators. Journal of the ACM, October 1980. Volume 27, Issue 4. Pp. 633-655.
140. 2.1.2 How MySQL Optimizes WHERE Clauses http://dev.mysql.com/doc/refman/5.5/en/where-optimizations.html.
141. Prilozhenie PostgreSQL 8.3.3., http://www.postgresql.org/download/. Adres fajla, soderzhashhego obsuzhdaemyj kod, v arhive postgresql-8.3.3\src\backend\optimizer\util\predtest.c.
142. Veitch E. W. A Chart Method for Simplifying Truth Functions. ACM Annual Conference/Annual Meeting: Proceedings of the 1952 ACM Annual Meeting. Pittsburg: ACM, NY, 1952. Pp. 127-133.
143. Karnaugh M. The Map Method for Synthesis of Combinational Logic Circuits. Transactions of the American Institute of Electrical Engineers, November 1953. Part I, № 72 (9). Pp. 593-599.
144. Quin W. V. On Cores and Prime Implicants of Truth Functions. American Mathematics Monthly, 1959. V. 66, № 9. P. 755-760.
145. McCluskey E. J. Minimization of Boolean Functions. The Bell System Technical Journal, November 1956. V. 35, Issue 5. Pp. 1236-1249.
146. [87]. Wu M.-C. Query Optimizatiom for Selecting Using Bitmaps. ACM SIGMOD Record, June 1999. Volume 28 Issue 2. Pp. 227-238.
147. Das Sarma A., Theobald M., Widom J. Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases. Technical Report. Stanford, 2007. http://ilpubs.stanford.edu:8090/800/.
148. Tarasenko P. F., Buharova M. F. Tehnologija «The Reporter» dlja postroenija otchetov po bazam dannyh [The Reporter technology for database reporting]. Vestnik Tomskogo Gosudarstvennogo Universiteta, № 275, aprel' 2002. S. 167-176 (in Russian).
149. Mendkovich N., Kuznetsov S. New Algorithms for Lexical Query Optimization. Proceedings of the 31st International Conference on Information Technology Interfaces. Cavtat/Dubrovnik, Croatia, June 22-25, 2009. Zagreb: University of Zagreb, 2009. Pp. 187-192.
150. Kuznetsov S. D., Mendkovich N. A. Novye algoritmy leksicheskoj optimizacii zaprosov [New Algorithms for Lexical Query Optimization]. Modeli i analiz informacionnyh sistem, 2009. T. 16, № 4. S. 22-33 (in Russian).
151. Mendkovich N. A., Kuznetsov S. D. Optimizacija kon#junktov uslovij v sostave zaprosov [Optimization of query condition’ conjucts]. Modeli i analiz informacionnyh sistem, 2011. T. 18, № 3. S. 144-154 (in Russian).
152. Bellamkonda S., Ahmed R., Witkowski A., Amor A., Zait M., Lin Ch.-Ch. Enhanced Subquery Optimizations in Oracle /. Proceedings of the 35th international conference on Very large data base, August 2009. Volume 2 Issue 2. Pp. 1366-1377.
153. Chaudhuri S. Query Optimizers: Time to Rethink the Contract?. Proceedings of the ACM SIGMOD International Conference on Management of Data, Providence, Rhode Island, USA, June 29 - July 2, 2009. New York: ACM, 2009. Pp. 961-968.
Review
For citations:
Mendkovich N.A., Kuznetsov S.D. An Overwiew of Evolution of Lexical Query Optimization Techniques. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;23. (In Russ.) https://doi.org/10.15514/ISPRAS-2012-23-12
Email this article 