Аналитическая обработка кэшированных данных

Размещено на http://www.allbest.ru/

УДК 004.652

Федеральное государственное бюджетное учреждение науки Институт математики им. С.Л. Соболева

Аналитическая обработка кэшированных данных

С.В. Мосин

С.В. Зыкин

Многие современные решения в области анализа больших объемов данных используют технологии аналитической обработки данных (Online Analytical Processing), сформировавшиеся еще в начале 90-х годов [1]. За последнее время в этой области было получено большое количество фундаментальных [2, 3, 4] и практических результатов [5, 6, 7].

В области теоретических исследований ситуация складывается следующим образом. Огромное число публикаций посвящено проблеме построения оптимального плана запроса на основе формальных правил, в которых не используются области определения предикатов в SQL-операторах (логическая оптимизация) либо эти области учитываются при вычислении статистических оценок для оптимизации физического доступа к базе данных. Близкими по методам решения являются задачи выполнения запросов на потоках данных [9, 10], однако различные, по сравнению с настоящей работой, цели приводят к различным результатам. Наиболее близка к рассматриваемой проблеме работа [11]. В ней рассматриваются конъюнктивные запросы над доменами данных с предикатами в виде арифметических сравнений и представлены алгоритмы вычисления запросов с использованием существующих представлений. В настоящей работе рассматривается специальный вид универсального реляционного запроса над отношениями базы даных, а не над отдельными доменами. Хотя цели в обеих работах совпадают, результаты различны по указанной причине. В частности, в настоящей работе нет необходимости разрабатывать алгоритмы выборки данных из промежуточных представлений, так как их замещает реляционная алгебра.

Существует ряд работ, в которых рассматривается проблема оптимизации запросов к хранилищам данных, имеющих концептуальное многомерное представлние, с использованием динамически формируемых представлений. При этом существуют два основных подхода для резервирования результатов запросов: статический [12-14] и динамический [15-19]. Первый базируется на использовании набора фиксированных запросов, во втором же предполагается динамический выбор результатов запросов для резерврвния на основе статистики появления а также вычислительной стоимости выполнения запросов. В качестве источника данных используются хранилища данных, либо реляционная база данных, преобразованная к иерархическому виду. При этом, рассматриваются специальные запросы манипулирования многомерными данными. В этой статье рассматривается технология раздельного формирования размерностей представления данных, необходимого для текущего анализа. Поэтому интерес представляют стандартные SQL запросы к базе данных и промежуточным представлениям. Результирующее представление может быть затем обработано специальными запросами манипулирования многомерными данными.

Цели и задачи исследования

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

Поставленная проблема связана с областью оптимизации запросов, поскольку нацелена на сокращение объема передаваемых данных с сервера базы данных. Зарезервированные данные активно используется в системах управления базами данных (СУБД). Но в большинстве случаев это касается повторного использования данных, записанных в кеш, без предварительного анализа содержимого на предмет возможности частичного или комбинированного использования. Работа СУБД ограничивается тем, что при выполнении очередного запроса блоки данных не запрашиваются с внешних устройств, если они есть в кеше, т. е. анализируются номера блоков, а не их содержимое.

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

Методы исследования

Основным методом исследования данной работы является анализ запросов к реляционной базе данных. Главными чертами предлагаемого анализа являются:

1. Использование семантики данных

2. Аналитическая проверка возможности использования кэша

3. Аналитическое определение недостающих данных

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

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

Полученные результаты

Сохраненные промежуточные представления данных обозначим =, , , ,

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

Целевое выражение, которое надо будет получить из представлений , запишем в виде:

Рассмотрим проблему формирования представления данных из существующих промежуточных представлений .

Теорема 1: , если:

а)

б)

в) .

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

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

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

Теорема 2: , если:

а)

б)

в)

г) .

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

Утверждение: Пусть - результат естественного соединения некоторых отношений. Пусть также . Тогда .

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

Теорема 3: , где , если:

а)

б)

в) .

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

Теорема 4: , где если:

а) ,

б)

в)

г) .

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