Введение к работе
Актуальность темы. Базы данных играют значительную роль в выполнении задач хранения и обработки накопленной информации. Эти технологии развиваются уже порядка полувека и претерпели большое количество изменений. Перед многими организациями стоит серьезная проблема обработки и анализа данных с требованием минимальной задержки по времени. Сам факт наличия доступа к большим объемам информации не гарантирует возможности делать какие-либо выводы о закономерностях, скрытых в данных. Для решения этой задачи нужны особые методы представления и обработки информации.
Самым распространенным подходом к решению этой проблемы в настоящее время является технология оперативной аналитической обработки данных OLAP (online analytical processing). В основе этой технологии лежит построение многомерного (гиперкубического) представления данных. Выделяют 3 основных типа технологии OLAP по способу организации базы данных, лежащей в основе многомерной модели данных: Relational OLAP (ROLAP), Multidimensional OLAP (MOLAP), Hybrid OLAP (HOLAP).
Подход ROLAP базируется на использовании исходной реляционной СУБД на всем этапе формирования и хранения многомерной модели данных. Существенным недостатком такого подхода является ограничения на схему БД: она должна быть в форме «звезды» или «снежинки», что нарушает принцип независимости данных.
Многомерное представление данных, сформированное по технологии MOLAP, постоянно хранится и обновляется периодически из исходной базы данных. Преимуществом такого подхода является минимальный отклик системы на запросы пользователя, так как гиперкубическое представление оптимизировано специально для выполнения таких запросов. Очевидный недостаток заключается в дублировании данных. Информация должна храниться как в исходной базе данных, так и в многомерном представлении.
Наконец, технология HOLAP пытается совместить лучшие показатели из двух предыдущих подходов. Данные хранятся в исходных таблицах, а заранее просчитанные агрегированные величины записываются в многомерные таблицы. Преимущество заключается в достижении более высоких средних показателей скорости выполнения запросов, по сравнению с ROLAP, и меньшим объемом дублированных данных. Недостатками, соответственно, является на-3
личие, пусть и меньшего чем в MOLAP, дублирования данных, а также более низкая средняя скорость выполнения запросов по сравнению с MOLAP.
Общим недостатком перечисленных подходов является отсутствие автоматизации процесса построения гиперкубического представления данных. Пользователю необходимо вручную осуществлять задание размерностей и мер гиперкуба, а также ограничений на размерности, что требует привлечения специалиста по OLAP. Этот процесс необходимо осуществлять каждый раз при формировании нового гиперкуба, что во многом определяет ограниченность использования технологии оперативной аналитической обработки данных.
В соответствие с этим актуальной является задача разработки автоматизированной системы формирования гиперкубического представления данных из исходного реляционного представления, позволяющей строить итоговое представление сминимальным участием пользователя. Данная система также должна использовать сохраненные в процессе формирования гиперкубов данные для выполнения построений следующих гиперкубов и проведения операций над данными.
Целью данной работы является разработка методов и алгоритмов формирования многомерного представления данных из реляционного представления при наложении логических ограничений на размерности и при использовании сохраненных данных. Для достижения этой цели были выполнены следующие задачи:
-
Исследовать и обосновать признаки выполнения свойства соединения без потерь информации для оптимизации алгоритма формирования контекстов.
-
Разработать способ формирования «Таблицы Соединений», осуществляющий построение, начиная с наименьших комбинаций отношений контекста и обосновать эквивалентность с существующим методом.
-
Разработать и обосновать методы аналитического определения возможности использования сохраненных данных.
-
Разработать алгоритмы использования сохраненных данных при формировании многомерных данных, а также при анализе данных.
-
Реализовать программное обеспечение, формирующее многомерное представление из исходного реляционного представления с использованием сохраненных данных.
-
Провести вычислительные эксперименты, подтверждающие эффективность предложенных подходов.
Научная новизна заключается в исследовании подходов к аналитическому сравнению областей истинности логических ограничений, разработке новых методов и оптимизированных алгоритмов формирования многомерных данных, разработке программного обеспечения для преобразования реляционной базы данных к многомерному представлению.
Теоретическая значимость. Исследованы свойства и методы сравнения областей истинности логических ограничений на основе логики предикатов и реляционной алгебры. Данные результаты могут быть использованы в дальнейшем при исследовании свойств логических формул реляционной алгебры и для усовершенствования систем хранения и анализа накопленной информации.
Практическая значимость заключается в разработке программного обеспечения, формирующего гиперкубическое представление из исходного реляционного представления. Данная система реализует теоретические принципы сравнения областей истинности логических формул при использовании сохраненных данных с целью снижения объема передаваемой информации и увеличения скорости работы. Проведено сравнение данной программы с существующими аналогами и выявлены сильные и слабые стороны всех систем.
Mетодология и методы исследования. Работа была выполнена с использованием методов межмодельных коммутативных преобразований, теории проектирования реляционных баз данных, логики предикатов, реляционной алгебры.
Степень достоверности результатов. Достоверность научных результатов, полученных в работе, подтверждается строгими математическими доказательствами. Теоретические построения подтверждены экспериментами, проведенными в соответствии с общепринятыми методиками.
Результаты работы могут быть использованы в научных исследованиях в области баз данных, а также при разработке прикладных программ, ставящих задачи переиспользования результатов реляционных запросов.
Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:
-
XVI Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (RCDL), 13 – 16 октября 2014 г., Дубна
-
VI Международная молодежная научно-практическая конференция с элементами научной школы «Прикладная математика и фундаментальная информатика» (ПМиФИ), 23 – 30 апреля 2015 г., Омск
-
Международная IEEE Сибирская конференция по управлению и связи (SIBCON), 21 – 23 мая 2015 г., Омск
-
VI Всероссийская научно-техническая конференция «Россия молодая- передовые технологии впромышленность!», 10 –11 ноября 2015 г., Омск
Публикации. Основные результаты по теме диссертации изложены в 9 печатных изданиях, 4 из которых изданы в журналах, рекомендованных ВАК, 2 – в изданиях, индексированных в Scopus и Web of Science. В рамках выполнения диссертационной работы получено одно свидетельство Роспатента об официальной регистрации программ для ЭВМ и баз данных. В работе [] Зыкину С.В. принадлежит постановка задачи, Полуянову А.Н. – исследование свойства существующего соединения, Мосину С.В.– исследование методов построения многомерных данных (стр. 401-407); в работе [] Зыкину С.В. принадлежит постановка задачи, Полуянову А.Н. – разработка алгоритма проверки свойства существующего соединения, Мосину С.В. – разработка алгоритмов построения многомерных данных (стр. 976-985); в работе [] Зыкину С.В. принадлежит постановка задачи, Полуянову А.Н. – доказательство достаточности условия существующего соединения, Мосину С.В. – анализ алгоритмов построения многомерных данных (стр. 122-128); в работах [, , ] Зыкину С.В. принадлежит постановка задачи, Мосину С.В. – все полученные результаты.
Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации 111 страниц текста. Список литературы содержит 109 наименований.