Математическое и программное обеспечение процесса приближенной обработки запросов в реляционных системах управления базами данных тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Филимонов Алексей Валерьевич

• Филимонов Алексей Валерьевич
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Филимонов Алексей Валерьевич

ВВЕДЕНИЕ

ГЛАВА 1. ИССЛЕДОВАНИЕ СУЩЕСТВУЮЩИХ ПОДХОДОВ К ПРИБЛИЖЕННОЙ ОБРАБОТКЕ ЗАПРОСОВ В РЕЛЯЦИОННОЙ СИСТЕМЕ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

1.1 Анализ методов и технологий интеграции операционных баз данных и систем аналитической обработки информации

1.2 Проблемы преобразования данных в операционных СУБД для использования в ОЬАР-подсистеме

1.3 Особенности приближенной обработки запросов в НТАР-системах

1.4 Исследование особенностей методов приближенной обработки запросов на основе сжимающих преобразований (синопсиса, свертки)

1.5 Обработка запросов онлайн-агрегирования в ОЬТР- хранилищах

1.6 Постановка задачи исследования

1.7 Выводы по главе

ГЛАВА 2. РАЗРАБОТКА МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ ПРИБЛИЖЕННОЙ ОБРАБОТКИ ЗАПРОСОВ В РЕЛЯЦИОННЫХ СИСТЕМАХ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

2.1 Выбор и обоснование метрики качества выборки

2.2 Формальное представление общей ошибки запроса с группированием

2.3 Подход к моделированию процесса обработки запросов с группированием

2.4 Выводы по главе

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМА ПРИБЛИЖЕННОЙ ОБРАБОТКИ КОНВЕЙЕРА ЗАПРОСОВ ПРОЦЕССОРОМ РЕЛЯЦИОННОЙ СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

3.1 Алгоритм определения объема случайной выборки по стратам в запросах с единственным атрибутом агрегирования и группирования

3.2 Алгоритм приближенной обработки конвейера запросов

3.3 Выводы по главе

ГЛАВА 4. РАЗРАБОТКА АРХИТЕКТУРЫ ПРОЦЕССОРА ЗАПРОСОВ СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ РЕЛЯЦИОННОГО ТИПА

4.1 Архитектура процессора запросов системы управления базами данных реляционного типа и структура программного обеспечения приближенной обработки конвейера запросов

4.2 Экспериментальная оценка приближенной обработки запросов

4.2.1 Точность приближенной обработки запросов

4.2.2 Оценка затрат процессорного времени при выполнении приближенной обработки запросов

4.2.3 Эксперимент по оптимизации пространства выборки с применением метрики качества выборки на основе бесконечной нормы

4.3 Экспериментальная оценка приближенной обработки конвейера запросов

4.3.1 Экспериментальный конвейер данных на наборе данных OpenAQ

4.3.2 Исследование точности результатов приближенной обработки конвейера запросов

4.3.3 Исследование величины доверительного интервала оценок

4.3.4 Исследование точности и уровня достоверности доверительного интервала оценок

4.4 Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ТЕРМИНОВ, СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение процесса приближенной обработки запросов в реляционных системах управления базами данных»

ВВЕДЕНИЕ

Актуальность темы. Использование современных методов машинного обучения, многофакторной обработки больших объемов данных, извлечения знаний, ориентированные на обработку сложных произвольных (ad hoc) запросов для решения задач аналитической обработки с низкой задержкой, предъявляют особые требования к архитектуре современных систем управления базами данным. На практике часто возникает ситуация, когда невозможно заранее определить подмножество отношений, участвующих в запросе. Это приводит к необходимости обработки не только отдельных запросов, но и конвейеров запросов, что существенно затрудняет решение задач оптимизации структуры хранилища. Направлением развития систем управления базами данных для решения подобных проблем является архитектура гибридных транзакционно-аналитических систем обработки данных (HTAP - hybrid transactional/analytical processing).

Одной из базовых функцией таких систем является функция приближенной обработки запросов (AQP - approximate query processing). Ее использование основано на гипотезе отсутствия необходимости получения точного результата обработки запросов для большинства data mining приложений. Подобный подход получения результатов обработки запросов с некоторой, некритичной для пользователя погрешностью, позволяет снизить временные задержки и сделать процесс обработки менее ресурсоемким. Этот подход применим, например, для запросов, результаты которых отображаются в приложениях визуализации данных в виде графиков и диаграмм. Применение методов AQP обеспечивает не только интерактивное время отклика при анализе массивных наборов данных, но и находит свое применение в обработке высокоскоростных потоков данных.

Существенный вклад в развитие исследуемой предметной области в части математического и программного обеспечения для подобных систем,

внесли Аббасов Э.М., Григорьев Ю.А., Ухаров А.О., Chaudhuri S., Brown P.G., Haas P.J., Xu B., Tirthapura S., Busch C.

Поскольку приближенная обработка запросов широко применяется на практике, существует тренд исследований, направленный на ее изучение в таких аспектах, как обеспечение точности результатов, получаемых в ходе обработки запроса. Одним из направлений в этой предметной области, наряду с применением методов сжимающих преобразований, является использование случайной выборки. Методы на ее основе применительно к обработке одиночных запросов демонстрируют значительное сокращение используемых ресурсов и времени отклика, обеспечивая при этом небольшую ошибку аппроксимации. Однако вопросы ее использования при обработке конвейера запросов являются малоисследованными.

Настоящее исследование посвящено вопросам оптимизации пространства случайной выборки применительно к конвейерным структурам запросов с целью получения результатов их выполнения с приемлемой точностью и за ограниченное время.

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

Тематика диссертации соответствует одному из основных научных направлений ФГКВОУ ВО «Академия Федеральной службы охраны Российской Федерации» - Повышение эффективности функционирования распределенных вычислительных систем.

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

Задачи исследования. Для достижения поставленной цели необходимо решить следующие задачи:

1. Провести анализ состояния исследований, связанных с проблемой повышения точности обработки конвейера запросов в реляционных системах управления базами данных на основе методов приближенной обработки.

2. Разработать математическое обеспечение для приближенной обработки конвейеров запросов в системах управления базами данных реляционного типа, обеспечивающее оптимизацию пространства случайной выборки с точки зрения оперативности и ресурсоемкости процесса обработки.

3. Разработать алгоритм приближенной обработки запросов с применением разработанного математического обеспечения в процессоре запросов реляционных систем управления базами данных.

4. Разработать архитектуру программного обеспечения процессора запросов системы управления базами данных, поддерживающую приближенную обработку конвейера запросов в хранилище данных с применением разработанного алгоритма.

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

Объект исследования - процессор запросов в системах управления базами данных реляционного типа.

Предмет исследования - процесс приближенной обработки конвейера запросов в процессоре запросов систем управления базами данных реляционного типа.

Методы исследования. В ходе решения поставленных в диссертации задач использовались методы теории баз данных, теории системного анализа,

теории множеств, теории вероятностей, математической статистики и планирования экспериментов.

Тематика работы соответствует следующим пунктам паспорта специальности 2.3.5. Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей (технические науки): п. 3 «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем»; п. 4 «Интеллектуальные системы машинного обучения, управления базами данных и знаний, инструментальные средства разработки цифровых продуктов».

Научная новизна работы. В диссертации получены следующие результаты, характеризующиеся научной новизной:

- математическое обеспечение приближенной обработки конвейера запросов в реляционных системах управления базами данных, отличающееся применением коэффициента вариации как метрики качества выборки, обеспечивающее получение равноточных оценок случайных величин из различных кластеров;

- алгоритм приближенной обработки конвейера запросов, отличающийся от известного наличием двухпроходной процедуры расчета требуемых статистических характеристик в цепочках запросов, обеспечивающий получение результатов выполнения конвейера запросов с оптимальным распределением пространства выборки;

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

- структура программного обеспечения приближенной обработки конвейера запросов, отличающаяся реализацией взаимодействия с модулем

сбора статистики системы управления базами данных и механизма кэширования и обеспечивающая повышение точности результатов выполненных запросов в рамках заданного временного ограничения.

Положения, выносимые на защиту:

1. Математическое обеспечение приближенной обработки запросов в реляционных системах управления базами данных обеспечивает повышение точности результатов, получаемых при приближенной обработки запросов;

2. Алгоритм приближенной обработки конвейера запросов процессором реляционной системы управления базами данных реализует разработанное в исследовании математическое обеспечение для оптимизации пространства выборки и обеспечивает получение результатов выполнения конвейера запросов с оптимальным распределением пространства выборки;

3. Архитектура процессора запросов системы управления базами данных реляционного типа обеспечивает снижение ресурсоемкости повторной обработки частных запросов в других конвейерах;

4. Структура программного обеспечения приближенной обработки конвейера запросов обеспечивает повышение точности результатов выполненных запросов в рамках заданных временных ограничений.

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

Практическая значимость исследования заключается в разработке средств математического и программного обеспечения приближенной обработки запросов в системах управления базами данных реляционного типа на основе теоретико-вероятностного подхода, обеспечивающих снижение задержки обработки запросов при заданном уровне точности результата обработки. На элементы разработанных программных средств получено свидетельство о государственной регистрации программы для электронной

вычислительной машины в реестре Федеральной службы по интеллектуальной собственности.

Результаты внедрения. Основные положения и результаты диссертационной работы реализованы в виде специального программного модуля для прототипа процессора запросов реляционной системы управления базами данных АО «Научно-исследовательский институт «Рубин» в рамках выполнения исследований по совершенствованию программного обеспечения, реализующего гибридную транзакционно-аналитическую обработку данных. Теоретические результаты работы используются в учебном процессе ФГКВОУ ВО Академия ФСО России в рамках дисциплины «Системы баз данных».

Апробация результатов диссертационного исследования. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: Modern informatization problems in simulation and social technologies MIP-2020'ES. Proceedings of the XXV-th International Open Science Conference (Yelm, WA, USA, 2020); Всероссийская межведомственная научно-технической конференция по теоретическим и прикладным проблемам развития и совершенствования автоматизированных систем управления и связи «НАУКА и АСУ 2021» (Москва, Зеленоград, 2021); Modern informatization problems in simulation and social technologies MIP-2022'AS. Proceedings of the XXVII-th International Open Science Conference (Yelm, WA, USA, 2022).

Публикации. По результатам диссертационного исследования опубликовано 9 печатных работ, в том числе 3 статьи в изданиях, рекомендованных ВАК РФ, патент на изобретение, свидетельство о государственной регистрации программы, а также статья в издании, индексируемом в Scopus. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично автором получены следующие результаты: [76] - математическое обеспечение приближенной обработки

запросов; [72] - алгоритм приближенной обработки запросов и конвейера запросов в реляционной системе управления базами данных;

[83] - архитектура процессора запросов с механизмом приближенной обработки в реляционной системе управления базами данных;

[84] - реализация специального программного обеспечения приближенной обработки конвейера запросов к хранилищам данных.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Работа изложена на 96 страницах машинописного текста, включая 37 рисунков, 3 таблиц и список литературы из 104 наименований.

ГЛАВА 1. ИССЛЕДОВАНИЕ СУЩЕСТВУЮЩИХ ПОДХОДОВ К ПРИБЛИЖЕННОЙ ОБРАБОТКЕ ЗАПРОСОВ В РЕЛЯЦИОННОЙ СИСТЕМЕ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

1.1 Анализ методов и технологий интеграции операционных баз данных и систем аналитической обработки информации

В настоящее время подавляющее большинство информационных сервисов потребительского и специального назначения так или иначе связаны с организацией хранения, обработкой и обеспечение доступа к массивам данных. К подобным сервисам можно отнести не только системы, обеспечивающие поиск и извлечение данных по определенным критериям, что характерно для предметных областей интернет-маркетинга, социальных сервисов, а также промышленных информационных систем, ориентированных на реализацию различного уровня бизнес-процессов, но также системы, связанные с решением задач многомерной аналитической обработки данных и/или семантического моделирования предметной области, поддерживаемой информационной системой.

Наиболее важными отличительными особенностями подобного рода информационных систем являются:

- их архитектурная распределенность, обеспечивающая решение задачи гибкого масштабирования вычислительных ресурсов системы и объемов ее хранилища данных;

- реализация обработки пользовательских запросов в масштабе времени близком к реальному;

- обеспечение поддержки возрастающих объемов неструктурированных данных за счет использования парадигмы NoSQL [1, 2, 3] в рамках таких моделей, как Key-Value [4, 5, 6], Family column Store [7, 8], Distributed FS [9, 10], а также комплексных подходов на их основе;

- решение на основе баз данных не только операционных задач (классический транзакционный подход к управлению информацией), но и их

аналитической обработки с цель агрегации данных, отражающих те или иные тенденции, требуемые потребителям данных.

На рисунке 1.1 представлена тенденция роста используемых в подобных системах неструктурированных данных в период с 2006 года по настоящее время. Из рисунка видно, что размещение в совокупных хранилищах современных информационных систем неструктурированных данных превалирует не только в объемах хранения (десятки тысяч экзабайт в сравнении с петабайтами хранимых структурированных данных), но также и в скорости их ежегодного прироста.

Рисунок 1.1 - Тенденция роста не структурированных данных, обрабатываемых информационными системами (аналитический отчет Gartner Analyst Group)

Очевидно, что в рамках задачи обработки потока пользовательских запросов в реальном масштабе времени следует учитывать специфику этих запросов. В общем случае их можно разделить на два крупных класса:

- реализация интенсивного потока запросов, требующих минимального времени отклика, при котором система работает со сравнительно небольшими по размерам транзакциями;

- реализация потока запросов, требующих, либо последующей после извлечения данных, их аналитической обработки, либо инкапсуляции извлекаемых данных в удобную для дальнейшей пользовательской обработки семантическую модель [11].

Традиционно существует практика деления информационных систем, поддерживающих каждый из классов запросов, на OLTP (Online Transaction Processing) и OLAP (Online Analytical Processing) системы [12, 13].

В обобщенном виде функции OLTP и OLAP-подсистем представлены на рисунке 1.2.

m - - L

и - -

Хранилище данных |—1

L-

Характеристики 01.ТР:

• Интенсивный поток транзакций

• Чувствительность к задержкам

• Маленький объем данных участвующих в транзакции

• Баланс между нагрузками чтение/запись или повышенная нагрузка на запись

Характеристики OLAP:

• Сравнительно низкая интенсивность потока транзакций

• Чувствительность к пропускной способности

• Большой объем данных участвующих в транзакции

• Повышенная нагрузка на чтение (исполнение низкоселективных запросов)

Рисунок 1.2 - Обобщенные характеристики OLTP и OLAP-подсистем

информационной системы

Очевидно, что OLTP-подсистема (в настоящее время более распространен термин Operational Database - операционная база данных [14]) реализуется в основном на основе СУБД реляционного типа, базы данных которых хранят сущности в отдельных таблицах, реализованных на основе предварительно нормализованной модели данных. Подобные системы также поддерживают традиционный набор требований ACID [15], предъявляемых к транзакционной системе. При этом их существенным недостатком является относительно низкая оперативность и/или своевременность обработки сложных многотабличных

запросов. В случае реализации подобных запросов, требования по обеспечению транзакционной целостности данных приводят к необходимости реализации множественных транзакций, что существенно увеличивает время обработки запроса. Решение этой проблемы, в общем случае, осуществляется с использованием модуля оптимизации запросов, на основе различных методов оптимизации [16, 17].

В OLAP-подсистеме для агрегированной (суммарной) обработки данные представляются в виде многомерных структур. Хранение подобных многомерных структур хранилище OLAP-подсистемы оптимизировано для операций выборки (SELECT). При этом такие операции выполняются обычно на над не нормализованной предварительно моделью данных с относительно невысокой скоростью. С точки зрения реализации такие операции состоят множества частных SQL-запросов, объединяемых в выражения с несколькими объединениями, группированием столбцов, агрегирующими подвыражениями и выборками. Обладая соответствующими достоинствами при обработке операционных запросов (OLTP-подсистема) и сложных многотабличных запросов, обеспечивающих последующую многофакторную обработку полученных данных (OLAP-подсистема) в большинстве случаев реализуются и эксплуатируются по-отдельности. Последовательность их использования основана на итерационном функционирования OLTP-подсистемы по поиску и извлечению требуемых данных и последующим функционированием OLAP-подсистемы, решающей задачу их аналитической обработки и предоставления пользователю в агрегированном по его критериям виде.

При этом данные из OLTP-хранилища поступают в OLAP-хранилище посредством конвейера ETL (ETL pipeline - Extract Transform Load, конвейер Извлечения Преобразования Загрузки) [18]. Исходя из определения, ETL обеспечивает создание конвейеров данных и одновременного выполнения преобразований над ними. То есть, строки данных преобразуются и загружаются в целевую таблицу еще до того, как все данные будут извлечены из источника данных. Конвейерная обработка подразумевает также то, что данные могут

проходить через две и более ветвей конвейера одновременно, что существенно ускоряет процессы извлечения, преобразования и загрузки.

Структурная схема процесса ETL представлена на рисунке 3.

Из рисунка 1.3 видно, что для реализации процесса ETL над данными извлеченными из OLTP подсистемы производится последовательность преобразований, в том числе направленных на очистку (data cleaning) и преобразования структуры (data wrangling). Этот процесс занимает время и расходует ресурсы как на стороне OLTP, так и на стороне OLAP-хранилища, прежде чем актуальные данные смогут быть включены в последующую аналитическую обработку.

Рисунок 1.3 - Структурная схема процесса ETL

Рассмотренная выше интеграция OLTP и OLAP-подсистем, основанная на процессе ETL, приводит к сложностям при организации информационной системы, в которой поступающие данные должны быть немедленно учтены в аналитической обработке всей информации, что особенно актуально, когда обрабатываемые данные описывают состояние некоторого нестационарного процесса (например, обширная сенсорная сеть беспилотных транспортных средств или процесс функционирования фондовой биржи), так как полезность получаемых моделей и знаний может быть сильно ограничена во времени.

Однако, в настоящее время, в связи с появлением новых вычислительных архитектур, в первую очередь облачных платформ, обеспечивающих реализацию вычислений в оперативной памяти (in-memory computing) [19] - минуя традиционные для центров обработки данных (ЦОД) системы хранения (СХД) на базе дисковых пространств, появилась возможность реализации логических структур обработки данных, объединяющих OLTP и OLAP-подсистемы. В [20, 21] подобные структуры именуются HTAP (Hybrid Transaction/Analytical Processing) или HOAP (Hybrid Operational/Analytical Processing). К достоинствам подобных гибридных структур стоит отнести:

- отсутствие необходимости в перемещении данных из операционных баз данных в хранилища данных для решения задачи их аналитической обработки. Хранение и обработка данных, как в рамках OLTP транзакций, так и решения задачи OLAP аналитики выполняется по технологии in-memory computing;

- транзакционные данные при их создании и/или модификации постоянно доступны для решения задачи их аналитической обработки в режиме реального времени;

- специалисты по аналитической обработке, эксплуатирующие OLAP-подсистему, в случае ее гибридной интеграции в HTAP структуру, могут быть уверены в актуальности получаемых из OLTP-подсистемы данных.

Показательным примером использования преимуществ HTAP-систем является получение телекоммуникационными провайдерами оперативной аналитики на основе базы клиентов, представленной операционной БД объемом в сотни терабайт [22].

Очевидно, что технически реализация HTAP-системы возможно на основе реализации методики интеграции существующих в организации OLTP и OLAP-подсистем. При этом крупные производители программного обеспечения обработки данных, а также провайдеры облачных платформ, поддерживающих вычисления in-memory, реализуют собственные проприетарные и открытые проекты подобных систем.

На рисунке 1.4 представлена реализация подобной HTAP-системы на базе проприетарных решений облачной платформы Microsoft Azure и реляционной СУБД Microsoft SQL Server [23, 24].

Как видно, в качестве операционных СУБД в этой реализации HTAP-системы может выступать, как классическая СУБД Microsoft SQL Server (или ее виртуализированные реализации), так и проприетарные расширения Microsoft Azure для таких проектов свободных реляционных СУБД, как MySQL и PostgreSQL. Необходимый для функционирования HTAP-системы протокол интеграции по функциям и данным реализован на уровне оркестрации, как на основе SQL Server Integration Services (интеграция по данным), так и Azure Data Factory (интеграция по функциям).

Клиентское ПО

• WebApps

• API Apps

• Logic Apps

OLTP-noACMcreMa

SQL Database SQL Server on VMs Azure Database for MySQL

Azure Database for PostgreSQL

OLAP-подсистема

• Azure Analysis Services

Подсистема аналитической обработки и отчетов

• Power 81

• SQL Server Reporting Services

Уровень оркестрации

• SQL Server integration Services

• Azure Data Factory

Рисунок 1.4 - Реализация OLTP и OLAP-подсистем на базе решений

Microsoft Azure

На рисунке 1.5 представлены сравнительные схемы процесса обработки SQL-запросов:

- в Microsoft SQL Server, ориентированном на работу с таблицами, хранимыми в дисковом СХД (рисунок 1.5 а);

- в гибридной HTAP реализации, использующей интерпретатор Transact-SQL (T-SQL) - процедурной реализации языка SQL компании Microsoft [25] (рисунок 1.5 а).

Из рисунка 1.5 а следует, что в случае использования дискового СХД:

- средство синтаксического анализа и модуль алгебризера (algebrizer) создают дерево запросов с логическими операторами на основе текста SQL запроса, отправленного пользователем;

- оптимизатор создает оптимизированный план этого запроса, содержащий физические операторы (например, соединения вложенных циклов). После оптимизации план может храниться в кэше планов;

- подсистема выполнения запросов обрабатывает интерпретацию плана запроса;

- для каждого оператора поиска в индексе, просмотра индекса и просмотра таблицы подсистема выполнения запрашивает у методов доступа строки из соответствующего индекса и табличных структур;

- методы доступа получают строки из индекса и страниц данных в буферном пуле, и по мере необходимости загружают страницы из диска в буферный пул.

Рисунок 1.5 - Сравнение этапов традиционной (а) и in-memory (б) обработки

запросов в Microsoft SQL Server

При использовании подсистемы in-memory computing (рисунок 1.5 б) в общем случае этапы обработки запроса остаются идентичными рассмотренным выше. Однако строки для оптимизированной для памяти таблицы при помощи

методов доступа получаются не из буферного пула, а извлекаются из структур данных непосредственно в памяти с помощью подсистемы in-memory OLTP.

На рисунке 1.6 представлены скрипты Transact-SQL используемые для случая работы с дисковым СХД (рисунок 5 а) и подсистемой in-memory OLTP (рисунок 5 б).

CREATE TABLE dbo.[Customer] (

CustomerlD nchar (5) NOT NULL PRIMARY KEY NONCLUSTERED,

ContactName nvarchar(30) NOT NULL ) WITH (MEMORY_OPTIMIZED=ON) GO

CREATE TABLE dbo.[Order] (

OrderlD int NOT NULL PRIMARY KEY NONCLUSTERED,

CustomerlD nchar (5) NOT NULL INDEX IX_CustomerlD HASH(CustomerlD) WITH (BUCKET_COUNT=100000),

OrderDate date NOT NULL INDEX IX_OrderDate HASH(OrderDate) WITH (BUCKET_COUNT=100000) ) WITH (MEMORY_OPTIMIZED=ON) GO

а)

SELECT o.OrderlD, c.* FROM dbo.[Customer] с INNER JOIN dbo.[Order] о ON c.CustomerlD = o.CustomerlD

б)

Рисунок 1.6 - Пример Transact-SQL скриптов традиционного (а) и in-memory (б)

этапов обработки запроса

Из рисунка видно, что использование подсистемы in-memory OLTP обеспечивает существенное сокращение табличных обращений и, как следствие, повышение оперативности обработки запроса.

В настоящее время вектор реализации крупномасштабных информационных систем, ориентированных, как на социальные сервисы, так и на поддержку крупных инфраструктур интернета вещей (IoT) смещается в сторону использования HTAP-систем (рисунок 1.7) - данные из [26].

Из рисунка видно, что в 2018 году на HTAP-системы приходилось только 15,7% от общего объема обрабатываемых данных, в то время как в 2022 году на рабочие нагрузки HTAP-систем приходится уже 26,9%.

2018

2022

20 69.3%

30.7% 15.7% 53.6%

OLAP НО АР OLTP

30.9% 26.9% 42.2%

69.1%

Рисунок 1.7 - Динамика использования HTAP-систем за период 2018-2022 гг

(аналитический отчет S&P Global)

1.2 Проблемы преобразования данных в операционных СУБД для использования в OLAP-подсистеме

Реализация HTAP-системы, как взаимодействующих независимо OLTP и OLAP-подсистем требует решения проблемы преобразования данных, извлекаемых из баз данных OLTL-подсистемы в виде традиционных результатов обработки SQL-запросов, в формат, обеспечивающий поддержку OLAP-подсистемой процесса многомерного анализа данных.

В общем случае это означает, что наборы данных, хранящиеся в операционной базе данных, должны быть преобразованы для использования конкретными операциями по добыче данных (data mining). Как представлено в [27] подготовка предварительно нормализованной БД, хранящейся в операционной базе данных реляционного типа, требует значительных временных ресурсов, поскольку в такой БД присутствует набор нормализованных таблиц, которые должны быть объединены и в дальнейшем преобразованы в уникальный для конкретной процедуры OLAP-подсистемы набор данных. В синтаксисе SQL присутствуют агрегирующие функции, но они обладают существенными ограничениями, поскольку возвращают только один столбец на агрегированную группу.

Список литературы диссертационного исследования кандидат наук Филимонов Алексей Валерьевич, 2023 год

СПИСОК ЛИТЕРАТУРЫ

1. Padhy, R. P. RDBMS to NoSQL: reviewing some nextgeneration non-relational Database's / R. P. Padhy, M. R. Patra, and S. C. Satapathy // Int. J. Adv. Eng. Sci. Technol., vol. 11, no. 1, 2011. pp. 15-30.

2. Li, Y. A performance comparison of SQL and NoSQL Databases / Y. Li, S. Manoharan // IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), 2013, pp. 15-19.

3. Khan, W. Predictive Performance Comparison Analysis of Relational & NoSQL Graph Databases / W. Khan, W. Shahzad // Int. J. Adv. Comput. Sci. Appl, vol. 8, 2017. pp. 523-530.

4. Siddiqa, A. A survey of big data management: Taxonomy and state-of-the-art // J. Netw. Comput. Appl., vol. 71, 2016. pp. 151-166.

5. Bazar, C. The transition from rdbms to nosql. a comparative analysis of three popular non-relational solutions: Cassandra, mongodb and couchbase / C. Bazar, C. S. Iosif // Database Syst. J., vol. 5, no. 2, 2014. pp. 49-59.

6. De Candia, G. Dynamo: Amazon's highly available key-value store / G. De Candia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, W. Vogels // In SOSP '07, 2007. pp. 205-220.

7. Иванова, Е.В. Методы параллельной обработки сверхбольших баз данных с использованием распределенных колоночных индексов / Е.В. Иванова, Л.Б. Соколинский // Программирование, № 3, 2017, 3-21 с.

8. Lemke C., Sattler K.-U., Faerber F., Zeier A. Speeding up queries in column stores: a case for compression / C. Lemke, K.U. Sattler, F. Faerber, A. Zeier // Proceedings of the 12th international conference on Data warehousing and knowledge discovery (DaWaK'10), 2010. pp. 117-129.

9. Howard, J. Scale and performance in a distributed file system. / J. Howard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayanan, R. Sidebotham, M. West. // ACM Transactions on Computer Systems, 6(1), 1988. pp. 51-81.

10. Isard, M. Distributed data-parallel programs from sequential building blocks / M. Isard, M. Budiu, Y. Yu, A. Birrell, Fetterly, D. Dryad // In EuroSys '07 (New York, NY, USA, 2007), ACM. 2007. pp. 59-72.

11. Kashlakov, I. A. Creating a Cloud Computing Service for Semantic Data Store Virtuoso Universal Server / I. A. Kashlakov, A. F. Tuzovsky, V. S. Morozov // IX Всероссийская научно-практическая конференция «Технологии Microsoft в теории и практике программирования», Томск, 2018, с. 32-38.

12. Conn. OLTP and OLAP Data Integration: A Review of Feasible Implementation Methods and Architectures for Real Time Data Analysis / Conn, S. Samuel // Information Systems Research, 12(1), 2009, pp. 83-102.

13. Brancheau, J. C. Information Architectures: Method and Practice / J. C. Brancheau, J. C. Wetherbe // Information Processing and Management, 22(6), 1986 pp. 453-464.

14. Mozafari, B. Performance and resource modeling in highly-concurrent oltp workloads. SIGMOD, 2013. pp. 301-312.

15. Das, S. Elastras: An elastic, scalable, and self-managing transactional database for the cloud. ACM TDS, 38(1):5:1-5:45, 2013.

16. Lungu, I., Tuning SQL queries for better performance in management infoemation systems using large set og data / I. Lungu, A. Bara // 5th RoEduNet International Conference, Universitatea Lucian Blaga, Sibiu, 2006.

17. El-Helw, A. Optimization of common table expressions in MPP database systems / A. El-Helw, V. Raghavan, Mohamed A. Solimanet // Proceedings of the VLDB Endowment - 2015. - Vol. 8, no. 12. - pp. 1704-1715.

18. Vassiliadis, P. A Survey of Extract-Transform-Load Technology // International Journal of Data Warehousing and Mining, 2009.

19. Verma, N. In-Memory Computing: Advances and Prospects // IEEE Solid-State Circuits Magazine, vol. 11, no. 3, 2019. pp. 43-55.

20. Kemper, A. HyPer - A Hybrid OLTP&OLAP Main Memory / A. Kemper, T. Neumann. // Database System Based on Virtual Memory Snapshots. In ICDE, 2011. pp. 195-206.

21. Kuznetsov, S. D. Real-time analytics, hybrid transactional analytical processing, inmemory data management, and non-volatile memory. / S. D. Kuznetsov, P. E. Velikhov, Fu. Qiang // Ivannikov Ispras Open Conference (ISPRAS), 2020, pp. 78-86.

22. Расширенная карта процессов оператора связи (eTOM), 2014 // Портал сетевых решений [Электронный ресурс]: Режим доступа: http : //www. nestor. minsk. by/sr/2008/06/sr80609. html.

23. Система управления базами данных Microsoft SQL Server. [Электронный ресурс]: Новые возможности SQL Server и платформы данных Microsoft. // Официальный интернет-портал корпорации Microsoft. - Режим доступа: https:// microsoft.com/ru-ru/server-cloud/products/sql-server/.

24. OLAP & BI tool to analyze Microsoft SQL Server, Azure and Access database. [Электронный ресурс]: // Режим доступа: https://www.assistmyteam.com/olap-bi-tool-to-analyze-microsoft-sql-server-azure-and-access-database/.

25. Фленов М. Е. Transact-SQL. - СПб.: БХВ-Петербург, 2006, 576 с.

26. Tshering, Y. IoT-based Platform with Big Data using Apache Kylin: Air Quality Monitoring System (AQMS) / Younten Tshering, Suyogya Ratna Tamrakar, Shubhangini Gontia, Smrity Baral. // World Journal of Research and Review (WJRR), Volume-13, Issue-3, September 2021, pp. 13-20.

27. Erlingsson, Ù. Rappor: Randomized aggregatable privacy-preserving ordinal response / Ù. Erlingsson, V. Pihur, A. Korolova. // In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, 2014, pp. 1054-1067.

28. Chen, Z. Fast and dynamic OLAP exploration using UDFs / Z. Chen, C. Ordonez, C. Garcia-Alvarado // In Proc. ACM SIGMOD Conference, 2009, pp. 1087-1090.

29. Arapinis, M. Sensitivity of counting queries / M. Arapinis, D. Figueira, M. Gaboardi. // In International Colloquium on Automata, Languages, and Programming (ICALP), 2016.

30. Morgenstein, J. Computer Based Management Information Systems Embodying Answer Accuracy as a User Parameter. // PhD thesis, U.C. Berkeley, 1980.

31. Garofalakis, M. Approximate Query Processing: Taming the TeraBytes: A Tutorial. / M. Garofalakis, P. Gibbons // VLDB, 2001.

32. Ioannidis, Y. Aprroximation in Database Systems. ICDT, 2003.

33. Mozafari, B. 2017. Approximate Query Engines pproximate Query Engines: Commercial Challenges and Research Opportunities. In Proceedings of the ACM International Conference on Management of Data (SIGMOD '17). ACM, New York, NY, USA, pp. 521-524.

34. Li, K. and Li, G. 2018. Approximate Query Processing: What is New and Where to Go?. Data Science and Engineering, (2018) 3: 379.

35. Kraska, T. 2017. Approximate Query Processing for Interactive Data Science. Proceedings of the 2017 ACM International Conference on Management of Data -SIGMOD '17.

36. Bernardino, P. Furtado, and H. Madeira. 2002. DWS-AQA: A Cost Effective Approach for Very Large Data Warehouses. In Proceeding International Database Engineering and Applications Symposium, IDEAS 2002, M. A. Nascimento, M. T. Ozsu, and O. R. Zaiane, editors, pp. 233-242. IEEE Computer Society.

37. Potti, N. and Patel, J. 2015. DAQ: A New Paradigm for Approximate Query Processing. Proceedings of the VLDB Endowment, 8(9), pp.898-909.

38. Park, Y., Mozafari, B., Sorenson, J. and Wang, J. 2018. VerdictDB. Proceedings of the 2018 International Conference on Management of Data - SIGMOD '18.

39. Lang, K. Stratified sampling meets machine learning / E. Liberty, K. Shmakov // In Proceedings of the 33rd International Conference on International Conference on Machine Learning. - 2016. - Vol. 48. - ICML'16. - pp. 2320-2329.

40. Lohr, S. L. Sampling: Design and Analysis // Duxbury Press. - 2009. - 2nd edition.

41. Гмурман, В. Е. Теория вероятностей и математическая статистика. Учеб. пособие для вузов. - Изд. 4-е, доп. - М.: Высш. школа, 1972.

42. Gemulla, R. Sampling time-based sliding windows in bounded space / W. Lehner // In Proc. SIGMOD. - 2008. - pp. 379-392.

43. Garofalakis, М. Wavelet-Based Approximation Techniques in Database Systems // IEEE Signal Processing Magazine. - 2006. - № 11. - pp. 54-59.

44. Acharya, S. Join synopses for approximate query answering / P. B. Gibbons, V. Poosala, S. Ramaswamy // In ACM SIGMOD Record. - 1999. - Vol. 28. - pp. 275286.

45. Ahmed, N. K. On sampling from massive graph streams / N. Duffield, T. L. Willke, R. A. Rossi // Proc. VLDB Endow. - 2017. - 10(11). - pp. 1430-1441.

46. Al-Kateb M. Stratified reservoir sampling over heterogeneous data streams / B. S. Lee // In Proc. SSDBM. - 2010. - pp. 621-639.

47. Григорьев, Ю. А. Обзор концепции многомерной модели данных в технологии OLAP / Ю. А. Григорьев, А. О. Ухаров // Проблемы построения и эксплуатации систем обработки информации и управления. Сб. статей. Вып. 4 / под ред. В.М. Черненького. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2006.

48. Wang, L. Spatial online sampling and aggregation / R. Christensen, F. Li, K. Yi // Proc. VLDB Endow. - 2015b. - № 9(3). - pp. 84-95.

49. Hentschel, B., Temporally-biased sampling for online model management / P. J. Haas, Y. Tian // In EDBT. -2018. - pp. 109-120.

50. Al-Kateb M. Adaptive stratified reservoir sampling over heterogeneous data streams / B. S. Lee // Information Systems. - 2014. - 39. - pp. 199-216.

51. Wu, W. Sampling-based query re-optimization / J. F. Naughton, and H. Singh // In Proceedings of International Conference on Management of Data. - SIGMOD '16. -2016. - pp. 1721-1736.

52. Jermaine, C. Scalable approximate query processing with the DBO engine / S. Arumugam, A. Pol, A. Dobra // In Proceedings of International Conference on Management of Data, SIGMOD'07. - 2007. pp. - 725-736.

53. Kandula, S. Quickr: Lazily approximating complex adhoc queries in bigdata clusters / A. Shanbhag, A. Vitorovic, M. Olma, R. Grandl, S. Chaudhuri, B. Ding // In SIGMOD. - 2016a. - pp. 631-646.

54. Hu, Y., Estimating aggregates in time-constrained approximate queries in oracle / S. Sundara, and J. Srinivasan // In Proceedings of the International Conference on Extending Database Technology. - EDBT '09. 2009. - pp/ 1104-1107.

55. Jacques-Silva, G. Leveraging sampling to reduce data warehouse resource consumption / D. Zhang // In Data @Scale, Boston. - 2018.

56. Chaudhuri, S. Overcoming limitations of sampling for aggregation queries / G. Das, M. Datar, R. Motwani, V. R. Narasayya // In ICDE. - 2001. - pp. 534-542.

57. Acharya, S. Congressional samples for approximate answering of group-by queries / P. B. Gibbons, V. Poosala // In Proceedings of International Conference on Management of Data. - SIGMOD '00. - 2000. - pp. 487-498.

58. Ding, B. Sample + seek: Approximating aggregates with distribution precision guarantee / S. Huang, S. Chaudhuri, K. Chakrabarti, C. Wang // In SIGMOD. - 2016. -pp. 679-694.

59. Rosch, P. Sample synopses for approximate answering of group-by queries / W. Lehner // In EDBT. - 2009. - pp. 403-414.

60. Nguyen, T. Stratified random sampling over streaming and stored data. / M. Shih, D. Srivastava, S. Tirthapura, and B. Xu // In Proceedings of the International Conference on Extending Database Technology, EDBT '19. - 2019. - pp. 25-36.

61. Neyman, J. On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection // Journal of the Royal Statistical Society. - 1934. - № 97(4). - 558-625.

62. Гнеденко, Б. В. Курс теории вероятностей: Учебник - Изд. 6-е, перераб. и доп.

- М.: Наука, 1988.

63. Jermaine, C. Online estimation for subset-based SQL queries / A. Dobra, A. Pol, S. Joshi / In Proceedings of the 31st International Conference on Very Large Data Bases, VLDB'05-2005. - pp. 745-756.

64. Cochran, W. G. Sampling Techniques // John Wiley & Sons. - 1977. - Third edition.

65. Babcock, B. Dynamic sample selection for approximate query processing / S. Chaudhuri, G. Das // In Proceedings of International Conference on Management of Data, SIGMOD'03. - 2003. - pp. 539-550.

66. Ganti, V. ICICLES: self-tuning samples for approximate query answering / M. Lee, R. Ramakrishnan // In VLDB. - 2000. - pp. 176-187.

67. Cormode, G., Synopses for massive data: Samples, histograms, wavelets, sketches / M. Garofalakis, P. J. Haas, C. Jermaine // Foundations and Trends in Databases. - 2011.

- 4(1-3). - pp. 1-294.

68. Tirthapura, S. Sketching asynchronous streams over a sliding window / B. Xu, C. Busch // In Proc. PODC. - 2006. - pp. 82-91.

69. Chaudhuri, S. Approximate query processing: No silver bullet / B. Ding, S. Kandula // In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data. -2017. - pp. 511-519.

70. Agarwal, S. Knowing when you're wrong: Building fast and reliable approximate quer processing systems / H. Milner, A. Kleiner, A. Talwalkar, M. Jordan, S. Madden, B. Mozafari, I. Stoica // In Proceedings of International Conference on Management of Data, SIGMOD'14. - 2014. - pp. 481-492.

71. Борчук, Л.Е. Математическая формализация глобального плана выполнения запросов реляционной СУБД / Л.Е. Борчук // Вестник ЧГУ. - Череповец, 2004. -С. 84-89.

72. Филимонов, А. В. Разработка алгоритма приближенной обработки конвейера запросов в реляционной системе управления базами данных / А. В. Филимонов //

Моделирование, оптимизация и информационные технологии. - 2022. - № 10 (3). Режим доступа : https://moitvivt.ru/ru/journal/article?id=1242.

73. Будникова, А. А. Ошибки в системах баз данных: теорема Брюера / Будникова А. А., Богданов И. В., Кумратова А. М. //Цифровизация экономики: направления, методы, инструменты. - 2019. - С. 290-292.

74. Agarwal, S. BlinkDB: Queries with bounded errors and bounded response times on very large data / B. Mozafari, A. Panda, H. Milner, S. Madden, I. Stoica // In Proc. EuroSys. - 2013. - pp. 29-42.

75. Григорьев, Ю. А. Использование вейвлет-преобразования для приближенной обработки многомерных данных. Информатика и системы управления /

A.О. Ухаров, А.Д. Плутенко. - 2008. - 15(1):3-13.

76. Громей, Д. Д., Оптимизация распределения пространства выборки для запросов с группированием в процессе их приближенной обработки. Системы управления и информационные технологии. / Д. Д. Громей, С. В. Козлов, А. В. Филимонов. -2022. - 89(3):48-54. - DOI: 10.36622/VSTU.2022.89.3.011.

77. Anderson, D. A highperformance algorithm for identifying frequent items in data streams / P. Bevan, K. Lang, E. Liberty, L. Rhodes, J. Thaler // In Proceedings of the 2017 Internet Measurement Conference, IMC '17. - 2017. - pp. 268-282.

78. Cao, Y. Data driven approximation with bounded resources / W. Fan // Proc. VLDB Endow. - 2017. - 10(9). - pp. 973-984.

79. Bowers, S. M. Query submission pipeline using linq / D. B. Wecker, C. D. Karkanias,

B. J. Smith. Braverman, V. Weighted sampling without replacement from data streams. / R. Ostrovsky, G. Vorsanger // Inf. Process. Lett. - 2015. - 115(12). - pp. 923-926.

80. Huang, W. Query pipeline / Y. Zhou, B. Yu. Indyk, P. Identifying representative trends in massive time series datasets using sketches / N. Koudas, S. Muthukrishnan // In proceedings of 26th International conference on Very Large Databases. - 2000. - pp. 363372.

81. Brown, P. G. Techniques for warehousing of sample data. / P. J. Haas // In Proceedings of the International Conference on Data Engineering. - 2006. - p. 6.

82. Al-wesabi, O. A. Hybrid Storage Management Method for Video-on-Demand Server. Emerging Trends in Intelligent Computing and Informatics. / N. Abdullah, P. Sumari // 1073:695-704. DOI: 10.1007/978-3-030-33582-3_65. - 2020.

83. Morkovin, S. V. Comparative analysis of metrics for estimating the introduced distortions in images when injection digital watermarks in the frequency spectrum / S. V. Morkovin, A. V. Filimonov, M. S. Rykshin, O. L. Tsvetkova // AIP Conference Proceedings. - 2021. - № 2402 (1) : 050013.

84. Свидетельство о государственной регистрации программы для ЭВМ № 2022618111. ProjectZero Server / С. В. Шекшуев, Д. Л. Жусов, М. А. Сазонов, А. В. Филимонов; заявители и правообладатели: С. В. Шекшуев, Д. Л. Жусов, М. А. Сазонов, А. В. Филимонов; опубл. 28.04.2022.

85. PostgreSQL 11 Documentation [электронный ресурс]. URL: https: //www.postgresql. org/files/documentation/pdf/11 /po stgresql -11-A4 .pdf

86. Козлов, С. В. Подходы к приближенной обработке аналитических запросов в реляционных системах управления базами данных. I-methods. / С. В. Козлов, А. А. Невров, И. П. Латышев, А. В. Филимонов. - 2021. - URL: http://intech-spc.com/wp-content/uploads/archive/2021/4/7-kozlov.pdf (дата обращения: 30.09.2022).

87. Ioannidis, Y. E. Balancing histogram optimality and practicality for query result size estimation / V. Poosala // In proceedings of ACM SIGMOD International conference on Management of Data. - 1995. - pp. 233-244.

88. Acharya, S. The aqua approximate query answering system / P. B. Gibbons, V. Poosala, S. Ramaswamy // In Proc. SIGMOD. - 1999. - pp. 574-576.

89. Kleiner, A. A general bootstrap performance diagnostic / A. Talwalkar, S. Agarwal, I. Stoica, M. I. Jordan // In Proc. of the int. conference on Knowledge discovery and data mining. - 2013. - pp. 419-427.

90. Rosch, P. Sample synopses for approximate answering of group-by queries / W. Lehner // In EDBT. - 2009. - pp. 403-414.

91. Zeng, K. The analytical bootstrap: A new method for fast error estimation in approximate query processing / S. Gao, B. Mozafari, C. Zaniolo // In Proceedings of International Conference on Management of Data. - 2014. - pp. 277-288.

92. Dekking, F. M. A Modern Introduction to Probability and Statistics: Understanding why and how / C. Kraaikamp, H. P. Lopuha'a, L. E. Meester // Springer Science & Business Media. -2005.

93. Nguyen, H. T. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks / M. T. Thai, T. N. Dinh // In Proceedings of International Conference on Management of Data. - 2016. - pp. 695-710.

94. Haas, P. J. Large-sample and deterministic confidence intervals for online aggregation // In proceedings of 9th International conference on Scientific and Statistical Database Management. - 1997.

95. Subotic, P. Automatic index selection for large-scale datalog computation / H. Jordan, L. Chang, A. Fekete, B. Scholz // PVLDB. - 2018. - Vol. 12(2). - pp. 141-153.

96. Peng, J. Aqp++: Connecting approximate query processing with aggregate precomputation for interactive analytics / D. Zhang, J. Wang, J. Pei // In SIGMOD. -2018. - pp. 1477-1492.

97. Olken, F. Maintenance of materialized views of sampling queries / D. Rotem // In proceedings of 8th IEEE International conference on Data Engineering. - 1992. - pp. 632-641.

98. Vitter, J. S. Approximate computation of multidimensional aggregates of sparse data using wavelets / M. Wang // In proceedings of ACM SIGMOD International conference on Management of Data. - 1999. - pp. 193-204.

99. Schenker, N. Qualms about bootstrap confidence intervals // Journal of the American Statistical Association. - 1985. - Vol.80 (390). - pp. 360-361.

100. Wu, S. Continuous sampling for online aggregation over multiple queries / B. C. Ooi, K.-L. Tan // In Proceedings of International Conference on Management of Data. -2010. - pp. 651-662.

101. Zhang, X. Sapprox: Enabling efficient and accurate approximations on sub-datasets with distribution-aware online sampling / J. Wang, J. Yin // Proc. VLDB Endow. - 2016. - № 10(3). - pp. 109-120.

102. Pfleiger, T. F. Distributed query engine pipeline method and system / A. E. Kimball, A. A. Desai Pol, A. Relational confidence bounds are easy with the bootstrap / C. Jermaine // In Proceedings of the 2005 ACM SIGMOD international conference on Management of data. -2005. - pp. 587-598.

103. Thusoo, A. Hive: A warehousing solution over a map-reduce framework / J. S. Sarma, N. Jain, Z. Shao, P. Chakka, S. Anthony, H. Liu, P. Wyckoff, R. Murthy // Proc. VLDB Endow (2009), Vol. 2(2). - pp. 1626-1629.

104. Haas, P. J. Data-stream sampling: Basic techniques and results // In Data Stream Management. -2016. - Springer. - pp. 13-44.