Preview

Труды Института системного программирования РАН

Расширенный поиск

Оценка эффективности минимизации ограничений запросов к СУБД

Аннотация

Эта статья описывает усовершенствованные алгоритмы лексической оптимизации запросов. Алгоритмы обнаруживают и удаляют избыточные условия из ограничения запроса, чтобы упростить его. Cтатья также представляет результаты применения этих оптимизационных техник и их влияние на скорость обработки запроса.

Об авторах

Н. А. Мендкович
OOO «FREEnet Group»
Россия


С. Д. Кузнецов
ИСП РАН
Россия


Список литературы

1. Jarke M., Koch J. Query Optimization in Database Systems // ACM Computing Surveys (CSUR), 1984. March, Volume 16, Issue 2. Pp. 111-152.

2. Mannino M. V., Chu P., Sager T. Statistical profile estimation in database systems // ACM Computing Surveys, Volume 20, Issue 3. September 1988.

3. Ionnidis Y. E. Query Optimization // The Computer Science and Engineering Handbook. Boca Raton, CRC Press, 1996.

4. Chaudhari S. An Overview of Query Optimization in Relational Systems // Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, 1998.

5. Кузнецов С. Д. Методы оптимизации выполнения запросов в реляционных СУБД. [http://www.citforum.ru/database/articles/art_26.shtml]. [Обращение 20 ноября 2012].

6. 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.

7. Khaitan P., Satish K. M., Korra S. B., Jena S. K. 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.

8. 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.

9. Sippu S., Soisalon-Soininen E. An Analysis of Magic Sets and Related Optimization Strategies for Logic Queries // Journal of the ACM, Volume 43, № 6, November 1996.

10. Мендкович Н. А., Кузнецов С. Д. Обзор развития методов лексической оптимизации запросов // Труды Института системного программирования, т. 23, М., ИСП РАН, 2012. Сс. 204-207.

11. 2.1.2 How MySQL Optimizes WHERE Clauses [http://dev.mysql.com/doc/refman/5.5/en/where-optimizations.html]. [Обращение 20 ноября 2012].

12. MySQL 5.5 Reference Manual. Chapter 7. Optimization. http://dev.mysql.com/doc/refman/5.5/en/optimization.html, [Опубликовано в 2010 году, обращение 20 ноября 2012].

13. Пакет PostgreSQL 8.3.3. Адрес файла postgresql-8.3.3srcbackendoptimizerutilpredtest.c.

14. Query Optimization in Oracle Database 10g Release 2. An Oracle White Paper, June 2005. Redwood Shores, Oracle Corporation, 2005.

15. Mendkovich N., Kuznetcov 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.

16. Кузнецов С. Д., Мендкович Н. А. Новые алгоритмы лексической оптимизации запросов // Модели и анализ информационных систем, 2009. Т. 16, № 4. С. 22-33.

17. Мендкович Н. А., Кузнецов С. Д. Оптимизация конъюнктов условий в составе запросов // Модели и анализ информационных систем, 2011. Т. 18, № 3. С. 144-154.

18. Hall P. A. V. Optimization of single expressions in a relational data base system // IBM Journal of Research and Development, 1976. Volume 20, Number 3.

19. 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. P. 1368.

20. 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.

21. Karnaugh M. The Map Method for Synthesis of Combinational Logic Circuits // Transactions of the American Institute of Electrical Engineers. Part I, № 72 (9), November 1953.

22. Quin W. V. O cores and prime implicants of truth functions // American Mathematics Monthly. 1959. V. 66. №9.

23. McCluskey E. J. Minimization of Boolean Functions // The Bell System Technical Journal. November 1956. V. 35, Issue 5.

24. Wu M. C. Query Optimization for Selecting Using Bitmaps // ACM SIGMOD Record Volume 28 Issue 2, June 1999. P. 234.

25. Тарасенко П. Ф., Бухарова М. Ф. Технология «The Reporter» для построения отчетов по базам данных // Вестник Томского Государственного Университета, № 275, апрель 2002.

26. 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/] [Обращение 20 ноября 2012].

27. Saad Y., van der Vorst H. A. Iterative solution of linear systems in the 20th Century // Journal of Computational and Applied Mathmatics, Issue 123, 2000.

28. Benzi M. The Early History of Matrix Iterations: With a Focus on the Italian Contribution // SIAM Conference on Applied Linear Algebra, Monterey Bay, Seaside, California, 26 October 2009.

29. Бронштейн И. Н., Семедяев К. А. Справочник по математике для инженеров и учащихся втузов. 13-е изд. исправленное. М.: Наука, 1986.

30. Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. Second Edition. New Jersey, 1999. P. 233.

31. Graefe G. Query Evaluation Techniques for Large Databases // ACM Computing Surveys, 1993. Volume 25, Issue 2.

32. Hromkovi J. Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin: Springer, 2004.

33. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. Third Edition. Cambridge-London: Massachusetts Institute of Technology Press, 2009.


Рецензия

Для цитирования:


Мендкович Н.А., Кузнецов С.Д. Оценка эффективности минимизации ограничений запросов к СУБД. Труды Института системного программирования РАН. 2013;25:113-130.

For citation:


Mendkovich N.A., Kuznetsov S.D. Minimization of data base query's conditions: evoluation of efficiency. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;25:113-130. (In Russ.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)