Software & Systems

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

Реляционные СУБД используют табличную модель структурного представления данных.   В класс нереляционных СУБД входят модели представления данных с отличными от реляционных возможностями. Например, документная иерархическая форма хранения позволяет сразу получить всю нужную информацию об объекте в целом, а для реляционной модели необходимо сделать, как минимум, несколько запросов, чтобы собрать все данные из различных таблиц в требуемый формат. Графовые   модели хранят в себе полную картину взаимосвязи различных сущностей и позволяют опе-  ративно извлекать запрашиваемую информацию. Скорость доступа обеспечивается за счет хранения не только узлов, но и отношений между ними, которые не вычисляются, как в   реляционных моделях. В то же время это приводит к разрастанию БД на дисковом пространстве, что не всегда подходит для систем реального времени (РВ) (например, в случае интеллектуальных систем (ИС) РВ типа систем поддержки принятия решений) [1, 2].

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

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

Отдельная задача связана с широко используемыми иерархическими данными. В случае использования БД реляционного типа хранение структуры вида <родитель>,<наследник> в отдельных таблицах приводит к расходованию дополнительной памяти и увеличению нагрузки на ядро СУБД при работе с такими данными. К меньшим затратам ресурсов может привести организация хранения родителей и наследников в единой таблице с выделением отдельных полей-идентификаторов для указания связи. В случае применения нереляционных моделей иерархические структуры в виде JSON-документов или графов для решения поставленной задачи будут более простыми и наглядными.

Новым и активно развиваемым в настоящее время подходом к хранению структурированной информации, особенно применительно к ИС РВ, является смешанный (гетерогенный) способ хранения данных. Данный способ применяется в мультимодельных СУБД, примерами которых могут служить как реляционная СУБД MS SQL Server, поддерживающая табличные и в определенной степени графовые модели данных, так и нереляционые СУБД TigerGraph и Neo4j, оперирующие графовыми и документными структурами данных [3, 4].

В связи с этим возникает задача унификации модели представления данных и разработки специализированного ПО для преобразования данных из одного формата представления в другой. Возможности решения этой задачи и посвящена данная работа, продолжающая и развивающая исследования и разработки авторов, представленные в [1, 2, 4].

Построение графовой темпоральной   модели данных

Модели для представления (хранения) и обработки темпоральных данных, основанных на РВ, можно разделить на три категории: темпоральные модели с меткой длительности, темпоральные модели на основе моментальных снимков и темпоральные модели на основе интервалов. В ИС РВ во время работы фиксируются и анализируются не только интервальные, но и моментальные события. Причем метка времени является атрибутом каждого события.

Предлагается графовая модель представления данных, включающая в себя сущности и временные (темпоральные) отношения в виде узлов графовой БД [1, 5]. Данная модель может быть использована для представления как мгновенных (моментных), так и интервальных событий (отличие интервальных событий от мгновенных заключается в наличии времени начала и времени окончания, то есть длительности; мгновенное событие можно интерпретировать как интервал нулевой длительности с совпадающими временами начала и конца).

С развитием вычислительных систем и технологий конструирования ИС и ИС РВ темпоральные данные стали неотъемлемой частью большинства реальных задач для различных предметных/проблемных областей: образование, здравоохранение и медицина, природные явления, управление техническими и организационными системами и т.д.

Приведем некоторые примеры темпоральных запросов (запросов к темпоральным данным):

-      в каком учебном заведении учился абитуриент до подачи заявления в аспирантуру НИУ «МЭИ» в 2022 году?

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

-      какими природными явлениями сопровождалось горение торфяников в 2010 году?

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

Графовые БД (и соответствующие СУБД) становятся все более популярными для различ-  ных видов приложений, таких как социальные сети (ВКонтакте, FaceBook, Twitter), хранение и анализ сетевых данных (например, онтологические модели, многомерные кубы данных OLAP) [6]. Построение графовой БД основано на формальных свойствах графов. В графовой БД сущности-объекты данных представляются в виде узлов. Взаимосвязь между ними обеспечивается переходами-ребрами. Как узлы, так и ребра могут иметь свои уникальные свойства или атрибуты, содержащие их характеристики (рис. 1). Благодаря этим свойствам графовые БД могут поддерживать темпоральные данные.

При построении графа на плоскости используются понятия смежности и инцидентности. В OLAP-структуре пространственные данные (гиперкубы данных) представляются как пространственные N-мерные объекты, состоящие из точек, линий, областей, срезов, поверхностей и объемов данных более высоких измерений. Относительно организации извлечения данных в подобных структурах заметим, что в отличие от структур данных поиска по одному ключу пространственные структуры спроектированы таким образом, чтобы обеспечить высокую производительность. Примером многомерного темпорального запроса может служить запрос на поиск университета поближе к дому абитуриента как с точки зрения расстояния, так и времени в пути [5, 6].

Для решения подобных задач большинство доступных представлений точечных данных являются вариантами метода разбиения на блоки, который применим на структурах данных, основанных на пространственном представлении [7]. В процессе обработки данных пространственное представление включает в себя разбиение пространства, из которого из-  влекаются данные, на области, называемые сегментами. Возникает задача масштабирования с целью адекватного разбиения. Одним из вариантов является разбиение всей области на фрагменты фиксированного размера, разбиение объектов, попадающих на стыки областей, присвоение каждому объекту индекса квадрата, в который он попал. Далее выполняются сортировка исходных данных и извлечение нужных объектов. Данный вариант не является эффективным для ИС РВ, так как, во-первых, необходима привязка к определенному уровню масштаба разделения, а, во-вторых, из-за существенного перебора уже на этапе разбиения есть вероятность возникновения комбинаторного взрыва. Альтернативным вариантом может служить подход с использованием графов (деревьев): Kd-, R- и 𝑅+ деревьев [8, 9]. Такие древовидные структуры используются для организации наборов произвольных пространственных объектов и обладают лучшей масштабируемостью. Каждый из объектов узла дерева выделяется при этом в отдельный ограниченный прямоугольник. Эффективность соответствующих алгоритмов извлечения данных достигается за счет минимизации пустого пространства между объектами, а также площади перекрытия областей узлов (на примере R-дерева, рис. 2) [8, 9].

Темпоральная графовая модель   на основе декартовой логики

Простой граф G(V, E) по определению является совокупностью двух множеств – непу-  стого множества вершин V и множества (может быть и пустым) ребер Е - упорядоченных или неупорядоченных пар элементов множества V´V. Граф G может быть расширен до темпорального Gt(V, E, T*) с помощью введения темпорального дополнения T*, включающего в себя временные (темпоральные) метки как узлов v(t) ∈ V, так и ребер e(t) ∈ E,  t∈ T* [5].

В классическом (одномерном) представлении темпоральный интервал характеризует   событие с точки зрения его длительности, которая является частью временной оси. В многомерном представлении темпоральный интервал может быть в виде некоторой ограниченной N-мерной области, в пределах которой происходило событие (рис. 3). В трехмерном случае, например, этой областью может служить параллелепипед. Области событий могут быть полностью вложенными, частично пересекаться или находиться в некоторой близкой области (в контексте отношений интервальной логики Аллена).

На данном темпоральном двумерном срезе ось абсцисс отображает время начала события, а ось ординат - время его окончания. В общем случае в выделенную в данном случае треугольную область попадут все события, происходящие с исследуемым объектом на интервале [t1, t1']. Так как значение атрибута времени начала события по умолчанию не превышает значение атрибута времени его окончания, на графике можно выделить диагональ как отдельную область, куда будут попадать только точечные (моментальные) события, в которых время начала и конца совпадает. Полное представление отдельного процесса в качестве кортежа событий, происходивших в разные промежутки (интервалы, в том числе и нечеткие) времени, позволит выявить, какие события шли последовательно друг за другом, происходили одновременно (параллельно), были завершены в один и тот же момент времени и т.д. [1, 4].

Обработку древовидного графа предлагается выполнять с помощью следующего алгоритма:

Пока текущий узел v(t) ∈ V не является конечным.

    Определить соседние узлы v*(t):

         Если значения val(v*(t)) ∈ области поиска S:

                   Добавить v*(t) к результатам поиска

        Иначе:

                  Расширить области v*(t) и выбрать минимально удаленный узел с минимальным расширением области до пересечения.

В качестве примера к рисунку 3 можно привести абстрактного студента, который в промежуток времени [t1, t1'] обучался в вузе и на зачетной неделе в некоторый день смог сдать два зачета по разным дисциплинам соответственно на интервалах [t2, t2'] и [t3, t3']. Заметим, что верхние границы событий t2' и t3' совпадают, так как учебный день (и время приема зачетов) ограничен.

Отметим также, что расширение данной (бинарной) модели позволяет исследовать комплексно ситуацию получения зачетов не только этим студентом, но и в учебной группе или на курсе в целом. Можно формировать и более сложные запросы, например, «Какие студенты обучались в период с 2018 г. по 2021 г.?» или «Какие студенты и по каким дисциплинам получили зачеты с отставанием от учебного графика?» и т.п.

Построение темпоральной БД   и анализ запросов

Для организации тестирования темпоральной БД были смоделированы четыре выборки, представляющие учебный процесс в рамках некоторого университета. Выборки содержали информацию о 1 000, 2 000, 5 000, 10 000 студентов разных курсов, обучавшихся на различных учебных направлениях, по 150 дисциплинам в совокупности. В качестве темпоральных атрибутов были выбраны события, характеризующие процесс обучения в целом, а также атрибуты, характеризующие освоение учебного графика для каждого отдельного студента. Временной интервал событий был ограничен четырьмя годами.

При оценке эффективности обработки темпоральных данных (формата дат) дополнительно использована функция datetime [9, 10].

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

Таблица 1

Пример сравнения темпоральных запросов

Table 1

An example of temporal query comparison

На рисунке 4 представлен фрагмент результата выполнения запросов в программной среде Neo4j Desktop. Отметим, что Neo4j позволяет автоматически выводить не только отдельные узлы сущностей, но и связи между ними.

По данному примеру можно также сделать вывод, что студенты Andrey и Sergey были знакомы (связаны друг с другом) и во время учебы. А построенная темпоральная модель позволяет не только получать отдельные сущности/события (узлы) графа, но и выявлять зависимости между ними. В числе важных критериев качества выполнения запроса полный и всесторонний анализ данных и выявление зависимостей.

Таблица 2 демонстрирует пример запроса интервала. В качестве примера (рис. 5) были запрошены студенты, которые обучались в период с 2018 по 2020 гг. и получили зачет по информатике вовремя.

Таблица 2

Пример сравнения темпоральных запросов интервалов

Table 2

An example of comparing temporal interval queries

Система Neo4j Desktop позволяет не только использовать встроенные средства СУБД, но и проектировать свои дополнительные программные расширения и процедуры.

Оценка эффективности построенной модели представлена на рисунке 6.

Эффективность разработанного алгоритма обхода графа (R-дерева) оценивается величиной O(log(n)), а алгоритм расширения области имеет линейную оценку. Алгоритм позволяет минимизировать пространство поиска и не обрабатывать поддеревья из соседних вершин графа, а также выявлять наиболее близкие по времени сущности (события).

Заключение

В статье рассмотрена проблема хранения и эффективной организации доступа к большим объемам данных. С целью повышения масштабируемости многомерная темпоральная OLAP-структура была представлена моделью в виде древовидного графа - темпорального R-дерева на основе темпоральной модели с бинарной системой координат. Предложен алгоритм обработки данных на основе этой модели. Сравнительный анализ показал повышение эффективности обработки данных с применением разработанного алгоритма в 1,5–2 раза по сравнению с базовой структурой (моделью) представления и обработки древовидных данных в СУБД Neo4j.

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

Работа выполнена при финансовой поддержке РФФИ (проект № 20-07-00498 А).

Литература

1.     Еремеев А.П., Панявин Н.А. О реализации нечеткой темпоральной модели данных на основе нереляционной базы данных // Тр. конгресса по интеллектуальным системам и информационным технологиям «IS&IT-2021». 2021. С. 261–269.

2.     Eremeev A.P., Poliushkin I.A., Paniavin N.A., Sergeev M.D., Petrov V.S., Marenkov M.A. Prototype of intelligent real-time decision support system based on anytime algorithms and NO-SQL database. Proc. III Int. Youth Conf. REEPE, 2021, рр. 1–6. DOI: 10.1109/REEPE51337.2021.9388053.

3.     Azzini A., Ceravolo P., Colella M. Performances of OLAP operations in graph and relational databases. Proc. Int. Conf. KMO, 2019, pp. 282–293.

4.     Еремеев А.П., Еремеев А.А. Реализация темпоральной базы данных для интеллектуальных систем реального времени // Тр. конгресса по интеллектуальным системам и информационным технологиям “IS&IT’17”. 2017. Т. 1. С. 205–212.

5.     Debrouvier A., Parodi E., Perazzo M., Soliani V., Vaisman A. A model and query language for temporal graph databases. The VLDB J., 2021, vol. 30, no. 5, pp. 825–858. DOI: 10.1007/s00778-021-00675-4.

6.     Needham M., Hodler A.E. Graph Algorithms: Practical Examples in Apache Spark and Neo4j. CA, O'Reilly Media Publ., 2019, 239 p.

7.     Lerer A., Wu L., Shen J. et al. Pytorch-biggraph: A large scale graph embedding system. Proc. II SysML Conf., ArXiv, 2019, pp. 1–12. URL: https://arxiv.org/pdf/1903.12287.pdf (дата обращения: 10.08.2022).

8.     Doraiswamy H., Vo H.T., Silva C.T., Freire J. A GPU-based index to support interactive spatio-temporal queries over historical data. Proc. IEEE XXXII ICDE, 2016, pp. 1086–1097. DOI: 10.1109/ICDE.2016.  7498315.

9.     Nathan V., Ding J., Alizadeh M., Kraska T. Learning multi-dimensional indexes. Proc. ACM SIGMOD Int. Conf. on Management of Data, 2020, pp. 985–1000.

10. Baton J., Van Bruggen R. Learning Neo4j 3. x: Effective Data Modeling, Performance Tuning and Data Visualization Techniques in Neo4j. Packt Publishing Ltd, 2017, 316 p.

References

1. Eremeev A.P., Paniavin N.A. On the implementation of a fuzzy temporal data model based on a non-relational database. Proc. Congress IS&IT'21, 2021, pp. 261–269 (in Russ.).
2. Eremeev A.P., Poliushkin I.A., Paniavin N.A., Sergeev M.D., Petrov V.S., Marenkov M.A. Prototype of intelligent real-time decision support system based on anytime algorithms and NO-SQL database. Proc. III Int. Youth Conf. REEPE, 2021, рр. 1–6. DOI: 10.1109/REEPE51337.2021.9388053.
3. Azzini A., Ceravolo P., Colella M. Performances of OLAP operations in graph and relational databases. Proc. Int. Conf. KMO, 2019, pp. 282–293.
4. Eremeev A.P., Eremeev A.A. Implementation of a temporal database for intelligent real-time systems. Proc. Congress IS&IT'17, 2017, vol. 1, pp. 205–212 (in Russ.).
5. Debrouvier A., Parodi E., Perazzo M., Soliani V., Vaisman A. A model and query language for temporal graph databases. The VLDB J., 2021, vol. 30, no. 5, pp. 825–858. DOI: 10.1007/s00778-021-00675-4.
6. Needham M., Hodler A.E. Graph Algorithms: Practical Examples in Apache Spark and Neo4j. CA, O'Reilly Media Publ., 2019, 239 p.
7. Lerer A., Wu L., Shen J. et al. Pytorch-biggraph: A large scale graph embedding system. Proc. II SysML Conf., ArXiv, 2019, pp. 1–12. Available at: https://arxiv.org/pdf/1903.12287.pdf (accessed August 10, 2022).
8. Doraiswamy H., Vo H.T., Silva C.T., Freire J. A GPU-based index to support interactive spatio-temporal queries over historical data. Proc. IEEE XXXII ICDE, 2016, pp. 1086–1097. DOI: 10.1109/ICDE.2016.
   7498315.
9. Nathan V., Ding J., Alizadeh M., Kraska T. Learning multi-dimensional indexes. Proc. ACM SIGMOD Int. Conf. on Management of Data, 2020, pp. 985–1000.
10. Baton J., Van Bruggen R. Learning Neo4j 3. x: Effective Data Modeling, Performance Tuning and Data Visualization Techniques in Neo4j. Packt Publishing Ltd, 2017, 316 p.