Содержание к диссертации
Введение
1. Проблемы исследования и разработки специального математического и программного обеспечения минимизации запросов для распределения виртуальной пропускной способности вероятностных баз данных .10
1.1. Вероятностный вывод в управлении данными 10
1.2. Пути создания информационного обеспечения для распределения виртуальной пропускной способности вероятностных баз данных с учетом версионности транзакций 19
1.3. Методы редактирования структуры таблиц реляционных баз данных 21
1.4. Постановка задач работы 28
2. Подход к управлению вероятностными базами данных на основе диссоциации запросов и коэффициента распространения 37
2.1. Определения, теоретические результаты в области диссоциации запросов вероятностных баз данных 37
2.2. Диссоциация и распространение как основные инструменты исследования 41
2.3. Алгоритмизация генерации минимальных планов запросов в вероятностных базах данных и численные оценки надежности 50
2.4. Оптимизация схем одиночных и множественных запросов в вероятностных базах данных 60
2.5. Выводы 73
3. Экспериментальная оценка эффективности методов минимизации самосоединяющихся конъюнктивных запросов для распределения виртуальной пропускной способности вероятностных баз данных 80
3.1. Верификация и оценка эффективности методов минимизации самосоединяющихся конъюнктивных запросов 80
3.2. Результаты вычислительных экспериментов 85
3.3. Эксперименты по ранжированию 90
3.4. Эвристические алгоритмы для распределения виртуальной пропускной способности вероятностных баз данных 99
3.5. Выводы 116
4. Разработка архитектуры специализированных средств управления вер сионностью структуры базы данных 121
4.1. Особенности специального контроля информационного обеспечения распределенных автоматизированных систем обработки информации 121
4.2. Проектирование архитектуры системы для обновления структуры базы данных 126
4.3. Алгоритмы функционирования программных модулей. Интерфейсы 133
4.4. Функциональные модули для обновления версий структуры базы данных 140
4.5. Выводы 154
Основные результаты работы 156
Список использованных источников
- Пути создания информационного обеспечения для распределения виртуальной пропускной способности вероятностных баз данных с учетом версионности транзакций
- Диссоциация и распространение как основные инструменты исследования
- Результаты вычислительных экспериментов
- Проектирование архитектуры системы для обновления структуры базы данных
Введение к работе
Актуальность темы
Вероятностный вывод применительно к большим пакетам данных становится центральной проблемой управления данными. Современные большие базы знаний, такие как Nell, DeepDive, Yago или Knowledge Vault компании Google имеют большое количество неопределенных кортежей. Пакеты данных с потерянными значениями часто считаются «выполненными» при использовании вывода в графических моделях или современных методах факторизации матриц, которые в конечном счете приводят к большой вероятностной базе данных. Пакеты информации, которые используют краудсорсинг, также не всегда полностью определены. Вероятностные базы данных также были применены в бутстрепинге над образцами данных.
Однако вероятностный вывод является NP-полным относительно размера базы данных, даже для некоторых очень простых запросов. Современные механизмы логического вывода используют методы на основе выборки, или основаны на варианте алгоритма Дэвиса–Патнема–Логемана–Лавленда для расчета взвешенной модели. Генерация выборки по схеме Гиббса может быть значительно улучшена применением некоторых классических методов условной оптимизации. В то время, как оба подхода задействуют методы условной оптимизации, они основываются на главной цели метода вероятностного вывода, и действуют в экспоненциальном времени или требуют много итераций до достижения сходимости. Предполагается право на существование другого подхода для оценки запроса в вероятностных базах данных, в котором каждый запрос полностью оценивается в ядре базы данных и вероятностный вывод может быть сведен к стандартной проблеме оценки запроса на подмножествах.
Информационное обеспечение автоматизированных систем обработки оперативной информации для фирм, имеющих территориально распределенные филиалы, требует специального контроля. Периодически возникает задача проведения глобальной модификации структуры таблиц базы данных в связи с изменением используемых приложений по обработке данных. Для нормального жизненного цикла информационной системы и базы данных необходима программная система версионного обновления структуры таблиц базы данных.
Таким образом, актуальной является задача создания математического описания функции оценки распространения для ранжирования результатов запроса по вероятностным базам данных, а также разработка и практическое применение алгоритмического и программного обеспечения динамического распределения пропускной способности элементов распределенной СУБД, основанный на оценке распределения вариации пропускной способности, определенной предшествующим распределением, специализированной программы для версионного обновления структуры таблиц базы данных в условиях вероятностных отношений.
Работа выполнена в ФГБОУ ВО «Воронежский государственный технический университет» в рамках научного направления «Вычислительные комплексы и проблемно-ориентированные системы управления».
Цель работы заключается в разработке математического и программного обеспечения оценки распространения для ранжирования результатов запроса по вероятностным базам данных, а также динамического распределения пропускной способности элементов распределенной СУБД, основанного на оценке распределения вариации пропускной способности.
Для достижения поставленной цели в диссертационной работе сформулированы следующие задачи:
ввести и обосновать новую функцию оценки распространения для ранжирования результатов запроса по вероятностным базам данных;
разработать техники оптимизации мультизапроса, ориентированного на конкретный набор данных, которые значительно ускоряют время, требуемое для оценки коэффициента распространения;
предложить эвристический алгоритм для динамического распределения пропускной способности элементов распределенной СУБД;
осуществить проектирование и разработку специализированной программы для версионного обновления структуры таблиц базы данных в условиях вероятностных отношений;
разработать программную реализацию автоматической модификации структуры таблиц в соответствии с sql-скриптами для корректной поддержки версионности.
Методы исследования. В качестве теоретической и методологической основы диссертационного исследования использованы методы математического моделирования, оптимизации, теории вероятностей и математической статистики, технологии объектно-ориентированного программирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.11: п. 4 «Системы управления базами данных и знаний»; п.9 «Модели, методы, алгоритмы и программная инфраструктура для организации глобально распределенной обработки данных».
Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:
новый коэффициент (функция оценки распространения) для ранжирования результатов запроса по вероятностным базам данных, отличающийся использованием основанных на смысле и принципах теории диссоциации семантиках и позволяющий дать оценку в стандартной реляционной базе данных для любого типа самосоединяющихся конъюнктивных запросов;
обобщение оценки распространения для графов и гиперграфов, отличающееся использованием двух оценочных функций - надежность (является NP-полной задачей) и распространение (с полиномиальной сложностью), обеспечивающее ранжирование линейных запросов до и после диссоциации;
техники оптимизации мультизапроса, ориентированного на конкретный набор данных, основанные на интеграции множества планов в единственный план запроса, который далее рекурсивно упрощается при наличии функциональных зависимостей или подмножества детерминированных отношений, которые значительно ускоряют время, требуемое для оценки коэффициента распространения;
эвристический алгоритм динамического распределения пропускной способности элементов распределенной СУБД, основанный на оценке распределения вариации пропускной способности, определенной предшествующим распределением обеспечивающий не худшее по сравнению со статическим качество распределения;
структура программного обеспечения, отличающаяся версионным обновлением структуры таблиц базы данных в условиях вероятностных отношений и позволяющая автоматически модифицировать структуру таблиц в соответствии с sql-скриптами.
Практическая значимость заключается в программной реализации системы версионного обновления структуры таблиц базы данных в условиях вероятностных отношений с применением СУБД Microsoft SQL Server 2012, которая обеспечивает пользователей гибким инструментом для автоматической модификации структуры таблиц в соответствии с sql-скриптами. На элементы программных средств получено свидетельство о государственной регистрации.
Реализация и внедрение результатов работы. Результаты исследований используются в системе управления информационной системой университета (Технологический университет, г. Хо Ши Мин, г.Ханой, Вьетнам) для обеспечения устойчивости и актуальности распределенной базы данных.
Основные результаты работы внедрены в учебный процесс Воронежского государственного технического университета в рамках дисциплин: «Вычислительные машины, системы и сети», «Информационные сети и телекоммуникационные технологии», при выполнении курсового и дипломного проектирования.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: XII Международной научно-практической конференции «Современные инструментальные системы, информационные технологии и инновации» (Курск, 2015), Международной научно-практической конференции «Advanced models and technologies in computer networks» (Yelm, WA, USA, 2015), XXI Международной открытой научной конференции «Modern informatization problems in simulation and social technolo-gies» (Yelm, WA, USA, January 2016), Международной летней и зимней научных школах «Парадигма» (Варна, Болгария, 2015, 2016), а также на конференциях профессорско-преподавательского состава Воронежского государственного технического университета (Воронеж, 2014-2016).
Публикации. По теме диссертационного исследования опубликовано 14 печатных работ, из них 4 статьи в изданиях, рекомендованных ВАК РФ, одно
свидетельство о регистрации программы для ЭВМ, 9 статей в журналах и материалах Международных и Всероссийских конференций и форумов. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: коэффициент распространения для ранжирования результатов запроса по вероятностным базам данных на основанных на смысле и принципах теории диссоциации запроса семантиках [2, 6, 10]; техники оптимизации мультизапроса, ориентированного на конкретный набор данных, которые значительно ускоряют время, требуемое для оценки коэффициента распространения, и основанные на интеграции множества планов в единственный план запроса [7, 9, 13]; эвристический алгоритм для динамического распределения пропускной способности элементов распределенной СУБД, основанный на оценке распределения вариации пропускной способности, определенной предшествующим распределением [3, 8, 11]; проектирование и разработка специализированных инструментов для версионного обновления структуры таблиц базы данных в условиях вероятностных отношений [5, 12, 14].
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав с заключением и выводами. Работа содержит 156 страниц. Список использованной литературы включает 148 наименований.
Пути создания информационного обеспечения для распределения виртуальной пропускной способности вероятностных баз данных с учетом версионности транзакций
Информационное обеспечение автоматизированных систем обработки оперативной информации для фирм, имеющих территориально распределенные филиалы, требует специального контроля. Как правило, многочисленные филиалы оказывают одинаковый набор услуг и для обработки возникающей оперативной информации требуются аналогичные автоматизированные информационные системы. Периодически возникает задача проведения модификации структуры таблиц базы данных в связи с изменением используемых приложений по обработке данных. Эти работы должны быть проведены во всех филиалах фирмы, имеющих локальные базы данных и реализующие одинаковые схемы обработки данных.
Создание специализированной программы для обновления структуры базы данных является важной и актуальной задачей, обеспечивающей оперативное, одинаковое и правильное обновление локальных баз данных в филиалах фирмы.
В простом случае, когда разработчик имеет дело с одной изменяющейся базой данных, процесс обновления выглядит просто – делаются необходимые изменения в структуре данных вручную либо с помощью sql-скрипта. Описанная ситуация встречается редко, чаще количество клиентов и соответствующих для них информационных систем, построенных на основе базы данных, исчисляется сотнями. Таким образом, для нормального жизненного цикла информационной системы и базы данных необходима программная система версионного обновления структуры таблиц базы данных.
При выполнении версионной модификации структуры базы данных необходимо учитывать следующие основные требования: - единоразовое выполнение каждого изменения (SQL-запроса); - строго предустановленный порядок изменений; - обновление с любой версии базы данных до последней версии, или при необходимости до промежуточной; - возможность с нуля создавать базу данных со структурой самой последней версии (является важным требованием, так как это необходимо как в процессе разработки и тестирования, так и при развертывании нового рабочего объекта); - обеспечение сохранности данных в момент миграции; - обеспечение отката версии базы данных на исходную позицию при возникновении ошибок во время миграции; - простота инструмента миграции. Выполнение всех вышеуказанных требований невозможно вне рамок специализированной программной системы, которая должна автоматизировать выполнение всех представленных требований. Реализация модификации структуры базы данных также должна быть доступна человеку, не имеющему специального технического образования. Для достижения цели необходимо решить следующие задачи: - определение типовых задач по обновлению структуры таблиц и базы данных; - разработка алгоритма подключения к базе данных; - выбор СУБД и средств для разработки специализированного приложения по модификации структуры данных; - проектирование и разработка пользовательского интерфейса; - разработка принципов безопасного обновления структуры базы данных; - реализация обновления базы данных в фоновом режиме; - опытная эксплуатация программного комплекса на действующих объектах.
Созданная система позволит персоналу, не имеющему специального технического образования, оперативно и правильно выполнять работы по версионной миграции баз данных.
Диссоциация и распространение как основные инструменты исследования
До сих пор [2.20, 2.21] для того, чтобы вычислить коэффициент распространения запроса q, нужно было разгруппировать его таблицы и вычислить несколько диссоциированных безопасных запросов q. На самом деле не будем применять просто диссоциацию запроса (Определение 2.4), потому что часть диссоциации таблицы (Определение 2.6) вычисляет несколько декартовых произведений. Второй технический результат – это глубокая связь между безопасными диссоциациями и планами запроса, который позволяет выполнять диссоциацию эффективно.
Теорема 2.2. Безопасная диссоциация. Пусть q будет конъюнктивным запросом без самосоединений. Существует изоморфизм между безопасными диссоциациями запроса q и планов P для запроса q. Кроме того, надежность диссоциированного запроса равна коэффициенту соответствующего плана: r(q)=score(P).
Рассмотрим безопасную диссоциацию q и обозначим соответствующий уникальный безопасный план P. Этот план использует диссоциированные отношения, следовательно, каждая диссоциация Riy i (xi,yi) имеет некоторые лишние переменные yi. Исключим все переменные yi из отношений и из всех операторов, которые их используют: это преобразует P в регулярный, общий, небезопасный план для запроса q. С другой стороны, рассмотрим любой план P для запроса q. Определим его соответствующую безопасную диссоциацию следующим образом: пусть для каждого оператора соединения @p [P1,...,Pk ] его переменные JVar будут объединением главных переменных всех подпланов: JVar =LjjHVar(Pj). Добавим к yt отсутствующие переменные JVar \HVar(Pj) для каждого отношения Ru происходящего в Pj. Например, рассмотрим нижнее соединение в плане запроса 5 на рис. 2.2: Qp[R(x),T(x,y),U(y)] Здесь JVar={x,y} и соответствующая безопасная диссоциация этого подплана может быть выражена так: q(x, у): -R(x, у), Т(х, у), U(x, у).
Завершенный булев запрос q(5) показан на вершине плана запроса 5. В то время как существует однозначное соответствие между безопасными диссоциациями и планами запроса, безопасные диссоциации не соответствуют планам.
В [2.21] исследовано, как пространственные семантики небезопасного плана Р отличаются от истинной надежности: score(P) r(q). Поскольку показано, что score(P)= r(qA) для некоторых диссоциаций А, получаем:
Вывод. Планы выполнения запроса как верхние границы. Пусть Р будет любым планом для запроса q, тогда P r(q).
Это означает, что любой план выполнения запроса (Определение 2.2) всегда дает верхнюю границу фактической надежности запроса r(q). Это общее свойство планов запроса было только ранее упомянуто в [2.26], но никогда не доказывалось.
Таким образом, утверждение 2.2 дает более эффективный метод для вычисления коэффициента распространения r(q) запроса: повтор запроса по всем планам Р, вычисление их коэффициентов, и сохранение минимального показателя minP[score(P)]. Каждый план Р оценивается на исходной базе данных без необходимости диссоциации входных таблиц. Однако, этот подход неэффективен, так как он вычисляет некоторые избыточные планы: например, на рис. 1.1 планы 5, 6, 7 являются избыточными, так как все они больше плана 3 в частичном порядке диссоциаций. План 3 доминирует над планами 5, 6 и 7. Таким образом, это является достаточным для оценки только минимальных планов запроса, т.е. тех, для которых соответствующая диссоциация является минимальной среди всех безопасных диссоциаций: это планы 3 и 4. Пример 2.5. Планы запроса. В Примере 2.4 запрос q: -R(x),S(x),T(x,y),U(y) имеет 8 диссоциаций (Рис. 2.2а). Среди них 5 являются безопасными, и Рис. 1.1 показывает их соответствующие планы запроса. Две диссоциации q(3) и q(4) являются безопасными и минимальными и их соответствующие планы запроса через оригинальную базу данных выглядят следующим образом: P(3) = pp- x @p [R(x),S(x),pp- x @p [T(x,y),U(y)]] P(4) = p-p y @p [U(y),pp- x @p [R(x),S(x),T(x,y)]]
Коэффициент распространения, таким образом, является минимумом множества двух минимальных планов: p(q)=mini=3…4[score(P(i))]..
Назовем переменную x основной переменной плана запроса P и запишем это как xRVar(P), если x проецируется на последнем операторе P = pp- xP и xX. Будем считать запрос связанным, если все подцели соединены конкретными переменными EVar(q). Для связанного запроса q запишем TopSets(q) для множества минимальных подмножеств конкретных переменных, чье удаление разобщает запрос, в виде Алгоритма 2.1 (рис. 2.3). Алгоритм 2.1 генерирует все минимальные планы запроса для данного запроса q.
Результаты вычислительных экспериментов
Проектирование архитектуры системы для обновления структуры базы данных
Рассматриваются вероятностные базы данных (probabilistic databases - PDBs), где каждый кортеж имеет независимую вероятность p(e)[0,1]. D - пример базы данных, т.е. набор кортежей и их вероятностей. Выделяем жирным шрифтом (х) обозначения наборов или кортежей, [k] -обозначение набора {1,…,k}, и x[i,j] - короткая форма для (xi,..,xj). Считаем, что окружение генерируется независимым включением каждого кортежа t в него с вероятностью p(t). Таким образом, база данных D кортеже-независимая. Рассматриваем самосоединяющиеся свободные конъюнктивные запросы q(x):-g1,...,gm, где g1,...,gm - относительные атомы, также называемые подцелью, на словаре R1,…,Rm. Это обозначение по сути аббревиатура функции первого порядка q(x) = $x1 ... $xk (g1...gm), где х1,…,хk - связанные переменные и х - свободные переменные в выражении. «Самосоединяющиеся свободные конъюнктивные запросы» означает тот факт, что каждая подцель gi отсылает к различным отношениям Ri.
Обозначаем через Var(q) набор всех переменных, HVar(q) - набор главных переменных x, и EVar(q) набор неглавных или относящихся к существованию запроса q переменных. Для булевого запроса: HVar(q) = 0 и Var(q) = EVar(q).
Обозначаем через Var(gi) переменные в подцели gi, и А - активный домен базы данных D.
Задача вероятностной оценки запроса состоит в вычислении величины P[q], которая является вероятностью того, что запрос верен в случайно выбранном окружении, и которую назовем надежностью запроса r(q).
Нас интересует качество и эффективность диссоциации в сравнении с точным вероятностным выводом, моделированием по методу Монте-Карло (MC) и стандартной детерминированной оценкой запроса (детерминированный запрос SQL). Наши эксперименты изучают следующие вопросы: Насколько наши три оптимизации могут улучшить диссоциацию? Насколько быстрее диссоциация по сравнению с точным вероятностным выводом, MC и детерминированной оценкой запроса? Насколько ранжирование из диссоциации лучше по сравнению с MC и ранжирование размером линейной передачи? Какие параметры определяют качество ранжирования для каждого из этих трех методов?
Качество ранжирования (Ranking quality). Мы используем величину средней точности MAP (mean average precision) для оценки качества ранжирования метода посредством его сравнения с ранжированием из точного вероятностного вывода как реальной ситуации (GT). MAP компенсирует ранжирования, которые помещают соответствующие элементы раньше. Самое лучше возможное значение равняется 1, самое худшее возможное 0. Средняя точность (Average Precision) при 10 P@k (AP@10) определяется как AP@10= k=1 , где P@k является точностью n при k возвращенных ответах. Усреднение по нескольким ранжированиям приводит к MAP. Используем для вычисления средней точности при наличии связей вариант аналитического метода, предложенный в [3.18] и который эквивалентен вычислению MAP по всем доступным полным порядкам частичного порядка, заданного оценками.
Точный вероятностный вывод. Каждый раз, когда возможно, мы вычисляем ранжирование GT-инструментом под названием SampleSearch [3.20, 3.21], который также служит для оценки затрат точного вероятностного вывода. Детали метода оценки вероятности отказа DNF (Data Not Found) с SampleSearch описаны в [3.19].
Метод Монте-Карло (MC) (Monte Carlo (MC)). Мы оцениваем моделирования MC для различного количества образцов/выборок и пишем MC (x) для x образцов. Например, AP для MC (10k) является результатом выборки отдельных коэффициентов/оценок кортежа 10000 раз от их линейных передач и затем оценки AP однократно по выбранным коэффициентам. Оценки MAP вместе со стандартными отклонениями являются, таким образом, средним числом по нескольким повторениям.
Ранжирование размером линейной передачи (Ranking by lineage size). Чтобы оценить потенциал невероятностных методов для ранжирования ответов, мы также оцениваем кортежи ответа, уменьшая размер их линейных передач, т.е. количество разделов. Наглядно, больший размер линейной передачи должен показать, что кортеж ответа имеет больше «поддержки» и должен таким образом быть более важным. Предположение 3.1. Используем генератор данных TPC-H DBGEN [3.23] для генерации базы данных размером 1GB, к которой можно добавить столбец P для каждой таблицы и сохранить ее в PostgreSQL 9.2 [3.22]. Добавляем к каждому кортежу i случайную вероятность pi , выбранную из интервала [0,р/тах] и в результате получаем ожидаемую среднюю входную вероятность awg[pi]=pimax/2. Используя базы данных с avg[p,] 0.5, можно избежать вероятности ответа близкие к 1 для запросов с большими линейными передачами.