автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Алгоритмы, методы хранения, поиска и анализа временных рядов в промышленных СУБД

Введение.

1. Временной ряд и методы его анализа.

1.1. Временные ряды и их классификация. Основные определения.

1.2. Методы анализа временного ряда.

1.3. Общий метод ускорения поиска.

1.4. Применение индексов для задач поиска фрагментов ряда.

1.5. Методика оценки эффективности индекса при поиске фрагментов временного ряда.

1.6. Алгоритм поиска.,.

1.7. Прикладные области применения.

2. Выбор типа СУБД как ядра для системы управления временными рядами.

2.1. Проблемы современных СУ BP.

2.2. Основные требования к новым современным СУВР.

2.3. Сравнение специализированных и универсальных СУБД.

2.4. Темпоральные СУБД.

3. Интеграция методов работы с временными рядами в СУБД.

3.1. Способы организации хранения.

3.1.1. Использование реляционной модели.,.

3.1.2. Использование объектной модели.'.

3.1.3. Использование объектно-реляционной модели.

3.1.3.1. Проекты SEQ и PREDATOR.

3.1.3.2. Informix (Illustra) Time Series DataBlade.

3.1.4. Сравнение моделей.

3.2. Методы индексирования значений временного ряда.

3.2.1. ST-индекс.,.

3.2.2. ST+-undeKc.

3.2.3. IP-индекс.

3.2.4. Сравнение методов индексирования.

3.3. Методы описания календарей.

3.3.1. Понятие календаря и способы его описания.

3.3.2. Применение календарей в СУВР.

3.3:3. Реализация календарей в коммерческих СУВР.

3.3.4. Проблемы технической реализации календаря в СУВР.

3.3.5. Современные методы описания календарей.

3.3.6. Анализ методов описания календарей.

3.4. Методы описания запросов и функций.

3.4.1. Классические скользящие функции.

3.4.1.1. Использование скользящих функций в SQL операторах.

3.4.1.2. Методы оптимизации вычислений скользящих функций.

3.4.1.3. SQL стандарта 3 - функции SQL/OLAP.

3.4.2. Агрегирование по шкале времени.

3.5. Выводы.

4. Предлагаемая архитектура современной СУВР.

4.1. Общая архитектура СУВР.

4.2. Логическая и физические модели хранения временного ряда.

4.3. Методы индексирования.

4.4. Определение календаря временного ряда.

4.5. Язык описания функций и запросов.

4.6. Выводы.

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

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

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

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

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

• Неспособность эффективно обрабатывать большие объемы данных

• Закрытый формат хранения временных рядов

• Отсутствие интерфейсов для расширения методов поиска и хранения внутри временных рядов

• Трудность интеграции в корпоративные информационные системы (КИС)

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

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

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

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

Научные исследования по поиску решения данной проблемы ведутся в самых разных направлениях. В ходе этих исследований выделилась группа программных продуктов, называемых системами управления временными рядами (СУВР). СУВР обеспечивают хранение и обработку временных рядов [1].

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

• Поиск во временном ряду фрагментов, похожих на заданный шаблон

• Построение новых типов индексов и оценка их эффективности

• Создание языка запросов к СУВР

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

Таким образом, усилия большинства исследователей оказались в стороне от центральной проблемы построения полнофункциональной СУВР. В небольшой части исследовательских проектов предпринимались попытки создания законченного программного продукта [2, 3]. Однако практически все они также замыкались на какую-то одну проблему, будь то язык описания запросов или построение структуры данных для хранения временного ряда.

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

1. Анализ современных методов хранения, поиска и анализа временных рядов;

2. Формирование критериев выбора СУБД для ядра системы управления временными рядами;

3. Разработка методов интеграции технологий хранения, поиска и анализа временных рядов в СУБД;

4. Построение архитектуры перспективной СУВР.

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

4.6. Выводы

Предложенная модель СУВР позволяет решить большинство стоящих в настоящее время проблем перед системами хранения и обработки временных рядов. Построенная на описанных принципах СУВР позволит:

• эффективно обрабатывать большие объемы данных

• использовать открытый формат хранения временных рядов

• расширять методы поиска и анализа временных рядов на базе открытых интерфейсов

• прозрачно интегрировать СУВР в корпоративные информационные системы

Заключение

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

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

В работе проанализированы методы организации индексов, используемые для различных задач поиска по элементам временного ряда. В результате был предложен метод усовершенствования IP-индекса (раздел 3.2.3). Данный индекс предназначен для поиска во временном ряду моментов времени, когда наблюдаемая характеристика принимает заданные значения. Если характеристика принимает эти значения не в моменты наблюдения, а между ними, то классические методы индексирования, например на базе В+-деревьев, не могут быть использованы. Это вызвано тем, что элементы ряда не будут содержать искомых значений.

IP-индекс позволяет решить эту проблему. Но при использовании данного индекса возможен пропуск искомого значения. В работе предложен модифицированный вариант IP-индекса, который снижает вероятность такого пропуска (раздел 4.3).

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

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

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

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

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

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

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

Таким образом, основными результатами работы являются:

1. Анализ методов хранения и обработки временных рядов в результате которого были сформированы требования к:

• Физической и логической модели временного ряда

• Методам построения индексов

• Способу описания календаря временного ряда

• Языку запросов

2. Предложена физическая и логическая модели временного ряда;

3. Оптимизированы методы построения индексов;

4. Обобщена задача поиска во временном ряде фрагмента, похожего на заданный шаблон, предложены способы оценки эффективности применения индексов;

5. Разработан метод описания календарей временных рядов как иерархической структуры временных интервалов;

6. Построена модель перспективной системы хранения и анализа временных рядов.

1. W. Dreyer, A. Kotz Dittrich, D. Schmidt "Research Perspectives for Time Series Management Systems" SIGMOD Record, Vol. 23 No. 1,1994

2. W. Dreyer, A. Kotz Dittrich, D. Schmidt "Using CALANDA Time Series Management System" ACM SIGMOD, 1995

3. Praven Seshadri "Predator. Design and Implementation" Computer Science Department Cornell University, http://www.cs.cornell.edu/Info/Projects/PREDATOR/, 2000

4. С. А. Айвазян, В. С. Мхитарян «Прикладная статистика и основы эконометрики», стр. 778 Юнити 1998

5. Р. А. Шмойлова «Теория статистики», стр. 334-336, Москва, «Финансы и статистика», 1999

6. А. Эрлих «Технический анализ товарных и финансовых рынков» Москва, «Финансист», 2000

7. М. Лугачев «Методы социально-экономического прогнозирования», http: // www, dei. econ.msu.ru/books/pro gnoz/, 1996

8. D. Q. Goldin, P. C. Kanellakis "On Similarity Queries for Time-Series Data: Constraint Specification and Implementation" In 1st International Conference on the Principles and Practice of Constraint Programming, pages 137-153,1995

9. C. Faloutsos, M. Ranganathan, Y. Manolopoulos "Fast Subsequence Matching in Time-Series Databases" In Proc. of the ACM SIGMOD Conference on Management of Data, 1994

10. D. Raflei, A. Mendelzon "Similarity-Based Queries for Time Series Data" in Proc. of the ACM SIGMOD Conference on Management of Data, 1997

11. В. И. Решетников «Информационный поиск и z-структура» сборник «Математические вопросы задач оптимизации и управления», МГУ 1981

12. А. Н. Сотников "Псевдорелевантные векторы и их свойства» сборник «Математические вопросы задач оптимизации и управления», МГУ 1981

13. А. Н. Сотников, Е. Г. Трофимова «О некоторых свойствах мер сходства в задаче информационного поиска», сборник трудов ВМК МГУ «Системное программирование и вопросы оптимизации», МГУ 1987

14. A. Guttman "R-trees: a Dynamic Index Structure for Spatial Searching", In Proceeding ACM SIGMOD International Conference on Management of Data, Boston, MA, 1984, pp. 47-57

15. Dennis Shasha "Time Series in Finance: the array database approach", http://cs.nyu.edu/cs/faculty/shasha/index.html, Department of Computer Science New York University

16. Doug Beeferman "QPD: Query by Pitch Dynamic Indexing Tonal Music by Content", 15-829 Course Project, 1997

17. L. Lin and T. Risch, "Using a Sequencial in Terrain-aided Navigation" in Preceedings of 6th International Conference on Information and Knowledge Management, Las Vegas, Nevada, Nov. 1997

18. L. Lin, T. Risch, M. Skold, D. Badal, "Indexing Values of Time Sequences", in the Proceedings of 5th International Conference on Information and Knowledge Management, pp. 223-232, Rockville, Maryland, Nov. 1996

19. А. Ю. Прохоров «Проблемы организации систем хранения и анализа временных рядов в современных СУБД», тезисы докладов III международной выставки-конференции «Информационные технологии и телекоммуникации в образовании», Москва, 2001.

20. А. Ю. Прохоров «Временной ряд как объект хранения в СУБД», тезисы докладов конференции «Корпоративные СУБД» Москва, 2001

21. А. Ю. Прохоров «Использование ОРСУБД для хранения и анализа временных рядов», «Компьютер Пресс», №№6,7 Москва, 2001

22. TimeConsult "What are Temporal Databases?", http://www.timeconsult.com/TemporalData/TemporalDB.html 1998

23. С. S. Jensen "The Consensus Glossary of Temporal Database Concepts -February 1998 Version", 1998

24. К. Дейт «Введение в системы баз данных», Диалектика, Киев Москва 1998 (стр. 90)

25. М. Аткинсон, Ф. Бансилон, Д. ДеВитт, К. Диттрих, Д. Майер, С. Здоник «Манифест систем объектно-ориентированных баз данных», Системы Управления Базами Данных № 4/95 стр. 142-155

26. W. Dreyer, A. Kotz Dittrich, D. Schmidt "An Object-Oriented Data Model for a Time Series Management System" in the Proceedings of the 7th International Working Conference on Scientific and Statistical Database Management, 1994

27. P. Seshadri, M. Livny, R. Ramakrishnan "SEQ: The Design and Implementation of a Sequence Database System", in the Proceedings of the 22nd VLDB Conference, 199628. "Informix TimeSeries DataBlade. User's Guide. Version 3.1" Informix Software, 1998

28. А. Ю. Прохоров «Работа с временными рядами при помощи Informix TimeSeries DataBlade» «Технология клиент-сервер» №2, Москва, 2000

29. А. Ю. Прохоров «Хранение и анализ временных рядов при помощи Informix TimeSeries DataBlade» «Informix Magazine Russian Edition» №1, Москва, 2000

30. С. S. Perng, D. S. Parker "SQL/LPP: a Time Series Extension of SQL based on Limited Patience Patterns" ACM SIGMOD, 1999

31. А. Ю. Прохоров «Методы ускорения работы с большими базами данных» тезисы докладов XXXIX юбилейной научной конференции МФТИ, Москва, 1996

32. Г. М. Адельсон-Вельский, Е. М. Ландис, "Доклады Академии Наук СССР", 146 стр, 263-266, 196234. "Oracle8i Time Series. User's Guide. Release 8.1.5" Oracle Corporation1999

33. M. Soo, R. Snodgrass "Multiple Calendar Support for Conventionla Database Management Systems" In Proceedings of the Workshop on an Infrastructure for Temporal Databases, 1993

34. Rakesh Chandra, Arie Segev, Michael Stonebraker "Implementing Calendars and Temporal Rules in Next Generation Databases" In Proceedings of the Tenth International Conference on Data Engineering, pages 264-273,1994

35. J. F. Allen "Maintaining Knowledge about Temporal Intervals" In R. Brachman and H. Levesque editors, Readings in Knowledge Representation, pages 509521. Morgan Kaufman Publishers, 1985

36. B. Leban, D. McDonald, D. Frster "A Representation for Collections of Temporal Intervals" In Proceedings of the AAAI-1986 5th International Conference on Artificial Intelligence, pages 367-371, 1986

37. R. Bliujute, S. Saltenis, G. Slivinskas, C. S. Jensen "Developing a DataBlade for a New Index" A TimeCenter Technical Report, 1998

38. Пол Браун «Воплощение идей SQL-99 в ведущих объектно-реляционных серверах баз данных. Реализация идей SQL-99 в СУБД Informix» "Открытые системы» №№7-8, 1999