Оптимизация запросов в слабоструктурированной модели данных
Диссертация
Предложена новая алгебра XQuery-запросов, удовлетворяющая требованиям, сформулированным на основе анализа существующих подходов к оптимизации XQuery-запросов, которым должна отвечать алгебра для построения высокопроизводительных систем выполнения запросов. Сформулированы ограничения на пространство допустимых планов, позволяющих применять алгоритмы блочной оптимизации. Доказано, что данные… Читать ещё >
Содержание
- 1. Методы и средства обработки запросов
- 1. 1. Модель данных XML и язык запросов XQuery
- 1. 1. 1. Модель данных XML
- 1. 1. 2. Язык XQuery
- 1. 1. 2. 1. Навигационные выражения
- 1. 1. 2. 2. Элементарные операции
- 1. 1. 2. 3. FLWOR выражения
- 1. 1. 2. 4. Условные и кванторные выражения
- 1. 1. Модель данных XML и язык запросов XQuery
- 1. 2. Основные принципы оптимизации запросов
- 1. 2. 1. Основные понятия
- 1. 2. 2. Основные элементы оптимизатора
- 1. 2. 3. Алгоритмы поиска оптимального плана
- 1. 2. 3. 1. Алгоритм динамического программирования
- 1. 2. 3. 2. Стохастические алгоритмы поиска
- 1. 3. 1. Методы сортировки и хэширования для больших объёмов данных
- 1. 3. 1. 1. Сортировка
- 1. 3. 1. 2. Хэширование
- 1. 3. 2. Алгоритмы соединения
- 1. 3. 2. 1. Алгоритм вложенных циклов
- 1. 3. 2. 2. Алгоритм сортировки и слияния
- 1. 3. 2. 3. Алгоритм хэшируюгцего соединения
- 1. 3. 3. Прямое и обратное вычисление навигационного выражения
- 1. 3. 4. Структурное соединение
- 1. 3. 5. Целостное соединение
- 1. 4. 1. Обзор и классификация XQuery-алгвбр
- 1. 4. 2. Анализ требований к алгебре для высокопроизводительного оптимизатора
- 2. 1. Структуры данных алгебры
- 2. 2. Основные операции алгебры
- 2. 2. 1. Базисные операции
- 2. 2. 2. Дополнительные операции
- 2. 3. Основные тождества операций
- 2. 4. Построение алгебраического выражения
- 2. 4. 1. Нормализация запроса
- 2. 4. 2. Трансляция в выражения алгебры
- 2. 5. Оптимизация
- 2. 5. 1. Изменение порядка блоков
- 2. 5. 2. Исключение избыточных операций
- 2. 5. 3. Преобразования, обеспечивающие ленивые вычисления
- 2. 6. Обсуждение
- 2. 7. Выводы
- 3. 1. Основные понятия
- 3. 1. 1. Модель стоимости
- 3. 1. 2. Граф классов частичных планов
- 3. 1. 3. Блочный алгоритм
- 3. 2. Оптимизация для XQuery
- 3. 3. Выводы
- 4. 1. Прототип исполнителя запросов XAnswer
- 4. 1. 1. Организация хранилища данных и исполнителя запросов СУБД eXist
- 4. 2. Постановка экспериментов
- 4. 2. 1. Эталонный набор данных и запросов XMark
- 4. 2. 2. Описание экспериментов
- 4. 3. Выводы
Список литературы
- Романовский. Алгоритмы решения экстремальных задач. — Москва, 1977.
- Balmin A., et al. Cost-based optimization in db2 xml // IBM Syst. J.— 2006. Vol. 45, no. 2. — Pp. 299−319.
- Beeri C., Tzaban Y. Sal: An algebra for semistructured data and xml // WebDB (Informal Proceedings). — 1999. Pp. 37−42.
- Bennett K., Ferris M. Ioannidis Y. A genetic algorithm for database query-optimization //In Proceedings of the fourth International Conference on Genetic Algorithms. — Morgan Kaufinann Publishers, 1991.— Pp. 400 407.
- Berkley DB Home Page, http://www.oracle.com/technology/products/berkeley-db/index.html. — Berkley DB Home Page.
- Blasgen M., Eswaran K. Storage and access in relational databases // IBM Systems Journal. — 1977. — Vol. 16, no. 4. — Pp. 363−377.
- Borkar V., et al. Query processing in the aqualogic data services platform // Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment, 2006. — Pp. 1037−1048.
- Bratbergsen K. Hashing methods and relational algebra operations // Proceedings of Conferece on Very Large Data Bases. — 1984. — Pp. 323−333.
- Chean, et al. From tree patterns to generalized tree patterns: On efficient evaluation of xquery // VLDB. — 2003. Pp. 237−248.
- Choi В., Fernandez M., Simeon J. The xquery formal semantics: A foundation for implementation and opitmization. — 2002.
- Codd E. A relational model of data for large shared data banks // CACM.- 1970, — Vol. 13, no. 6.
- Deutsch A., et al. The next framework for logical xquery optimization // VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases. — VLDB Endowment, 2004. — Pp. 168−179.
- Dewitt D., et al. Implementation techniques for main memory database systems // Proceedings of ACM SIGMOD conference. — 1984.
- DeWitt D., Gerber В. Multiprocessor hash-based join algorithms // Proceedings of Conferece on Very Large Data Bases. — 1985. — Pp. 151−164.
- El-Masri R., et al. Fundamentals of database systems. —¦ 1989.
- Exist DBMS Home Page, http://exist-db.org/. — Exist DBMS Home Page.
- Extensible Markup Language (XML) 1.0 (Second Edition). — 6 October 2000. — W3C Recommendation.
- Fankhauser P. Xquery formal semantics state and challenges // SIGMOD Rec. 2001. — Vol. 30, no. 3. — Pp. 14−19.
- Fernandez M., et al. Xml query languages: Experiences and exemplars.— 1999.
- Gerber R. Dataflow query processing using multiprocessor hash partitioned algorithms. — 1986. — Technical Report. Computer Sciences Department, University of Wisconsin.
- Goldberg D. Genetic algorithms in search, optimization and machine learning. addison-wesley. — 1989.
- Goodman J. An investigation of multiprocessor structures and algorithms for database management. — 1981. — Technical Report. University of California.
- Graefe G. Query evaluation technques for large databases // ACM Computing Surveys. — 1993. — Vol. 25, no. 2. — Pp. 121−123.
- Graefe G., DeWitt D. The exodus optimizer generator // Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data. 1987. — Pp. 160−172.
- Graefe G., McKenna B. The volcano optimizer generator: Extensibility and efficient search // IEEE Data Engineering Conference. — 1993.
- Grinev M., Kuznetsov S. Towards an exhaustive set of rewriting rules for xquery optimization: Bizquery experience // ADBIS.— 2002, — Pp. 340 345.
- Grust T. Accelerating xpath location steps // SIGMOD Conference. — 2002.
- Haas L., et al. Starburst mid-flight: As the dust clears // IEEE Transactions on Knowledge and Data Engineering. — 1990. — Pp. 143−160.
- Ioannidis Y. Query optimization // ACM Comput. Surv.— 1996.— Vol. 28, no. 1, — Pp. 121−123.
- Ioannidis Y. The history of histograms // VLDB '2003: Proceedings of the 29th international conference on Very large data bases. — VLDB Endowment, 2003. Pp. 19−30.
- Ioannidis Y., Kang Y. Randomized algorithms for optimizing large join queries // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. — 1990. — Pp. 312−321.
- Ioannidis Y., Wong E. Query optimization by simulated annealing // Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data. — 1987. — Pp. 9−22.
- Jagadish H., et al. Tax: A tree algebra for xml // DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages. — London, UK: Springer-Verlag, 2002.
- Jagadish H., et al. Timber, a native xml database // The VLDB Journal. — 2002, — Vol. 11, no. 4. — Pp. 274−291.
- Jiang H., et al. Holistic twig joins on indexed xml documents // Proceedings of International Conference on Very Large Data Bases. — 2003. — Pp. 273−284.
- Josifovski V., et al. Querying xml streams // The VLDB Journal.— 2005. Vol. 14, no. 2. — Pp. 197−210.
- Kang Y. Randomized Algorithms for Query Optimization: Ph.D. thesis / University of Wisconsin, Madison. — 1991.
- Khalifa S., et al. Structural joins: A primitive for efficient xml query pattern matching // icde.— 2002.
- Kirkpatrick S., Gelatt C., Vecchi M. Optimization by simulated annealing // Science. 1983. — Vol. 220. — Pp. 671−680.
- Kitsuregawa M., Nakayama M., Takagi M. The effecy of bucket size tuning in the dynamic hybrid grace hash join method // Proceedings of the International Conference on Very Large Data Bases. — 1989.
- Kitsuregawa M., Tanaka H.} Motooka T. Application of hash to database machine and its architecture // New Generation Computing. — 1983.
- Kitsuregawa M., Yang W., Fushimi S. Application of hash to database machine and its architecture // Proceedings of the 6th International Workshop on Database Machines. — 1989.
- Knuth D. The Art of Computer Programming. — Addison-Wesley, 1973.
- Lohman G. Grammar-like functional rules for representing query optimiza,-tion alternatives // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data. — 1988. — Pp. 18−27.
- Lukichev M., Barashev D. Xml query algera for cost-based optimization // Proceedings of the SYRCoDIS 2007 Colloquium on Databases and Information Systems. — 2007.
- May N., et al. Nested queries and quantifiers in an ordered context // Proc. ICDE Conference, Boston, USA. — 2004. Pp. 239−250.
- McHugh J., Widom J. Query optimization for xml // Proceedings of 25th International Conference on Very Large Data Bases. — 1999.— Pp. 315 326.
- Meir W. Index-driven xquery processing in the exist xml database. — 2006.
- Michiels P. Xquery optimization. — 2003.
- Mishra P., Eich M. Join processing in relational databases // ACM Com-put. Surv. 1992. — Vol. 24, no. 1.- Pp. 63−113.
- Nahar S., Sahni S., Shragowitz E. Simulated annealing and combinatorial optimization // DAC '86: Proceedings of the 23rd ACM/IEEE conference on Design automation. — 1986. — Pp. 293−299.
- Nakayama M., et al. Hash partitioned join method using dynamic destaging strategy // Proceedings of the International Conference on Very Large Data Bases. 1988.
- Naughton J., et al. The niagara internet query system // IEEE Data Engineering Bulletin. — 2001. — Vol. 24, no. 2. — Pp. 27−33.
- Novak L., et al. Efficient implementation of xquery constructor expressions // Proceedings of the SYRCODIS 2008 Colloquium on Databases and Information Systems. — 2008.
- Re C., et al. A complete and efficient algebraic compiler for xquery // ICDE '06: Proceedings of the 22nd International Conference on Data Engineering. — Washington, DC, USA: IEEE Computer Society, 2006. P. 14.
- Sartiani С., Albano A. Yet another query algebra for xml data // IDEAS '02: Proceedings of the 2002 International Symposium on Database Engineering and Applications. — IEEE Computer Society, 2002. — Pp. 106−115.
- Schmidt A., et al. Xmark: A benchmark for xml data management // Proceedings of International Conference on Very Large Data Bases. — 2002. — Pp. 974−985.
- Schneider D., DeWitt D. Tradeoffs in processing complex join queries via hashing in multiprocessor database machines // Proceedings of the International Conference on Very Large Data Bases. — 1990.
- Sedna DBMS Home Page, http://modis.ispras.ru/sedna/. — Sedna DBMS Home Page.
- Selinger P., et al. Access path selection in a relational database management system // ACM-SIGMOD Conf. on the Management of Data. — 1979. Pp. 23−34.
- Shapiro L. Join processing in database systems with large main memories // ACM Transaction Database Systems. — 1986.— Vol. 11, no. 3.— P. 239.
- Su S. Database computers: Principles, architectures, and techniques. — 1988.
- Swami A. Optimization of large join queries: Combining heuristic and combinatorial techniques // Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data. — 1989. — Pp. 367−376.
- Swami A., Gupta A. Optimization of large join queries // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data. 1988. — Pp. 8−17.
- Wang S., et al. Optimization of nested xquery expressions with order by clauses // ICDEW '05: Proceedings of the 21st International Conference on Data Engineering Workshops. — IEEE Computer Society, 2005.
- Weiner A., Mathis C., Haerder T. Towards cost-based query optimization in native xml database management systems // Proceedings of the SYRCoDIS 2007 Colloquium on Databases and Information Systems. — 2008.67