Содержание к диссертации
Введение
1. Специфика хранилищ данных, содержащих хронологическую информацию. анализ применимости существующих моделей данных для них 14
1.1. Обобщенная структура хранилища данных. Особенности хранилищ данных, содержащих хронологическую информацию 14
1.2. Реляционная модель данных 19
1.2.1. Структурные элементы модели 19
1.2.2. Реляционная алгебра 20
1.2.3. Преимущества и недостатки реляционной модели 24
1.3. Объектные модели данных 30
1.3.1. Объектно-ориентированная модель данных 30
1.3.2. Объектно-реляционная модель данных 33
1.4. Модели данных для временной информации 35
1.4.1. Специфика временной информации 3 6
1.4.1.1. Проблема представления времени 3 6
1.4.1.2. Манипулирование временными данными 38
1.4.1.3. Методы эффективного исполнения запросов к временным данным 40
1.4.2. Представление временной информации в реляционной модели данных 41
1.4.3. Хронологические последовательности как особый тип временной информации 42
1.4.3.1. Поддержка возможности восстановления отсутствующих данных 43
1.4.3.2. Поддержка различных размерностей времени 47
1.4.3.3. Поддержка запросов, учитывающих хронологическую упорядоченных данных 49
1.4.3.4. Применимость коммерческих СУБД для организации хранилищ данных, содержащих хронологические последовательности 50
Выводы 51
2. Хронологическая модель данных 53
2.1. Структуры данных 55
2.1.1. Хронологическая последовательность 5 5
2.1.2. Размерность времени и метка времени 56
2.1.3. Сравнимость размерностей и сравнение меток времени 59
2.2. Принципы построения языка описания данных 61
2.2.1. Шкала времени и описание меток времени по шкале 62
2.2.2. Описание множеств меток времени одной размерности (календарей) 66
2.2.3. Описание размерностей времени 70
2.2.4. Описание структуры хранилища данных 78
2.3. Алгебра хронологических последовательностей 83
2.3.1. Аналоги реляционных операций 83
2.3.2. Дополнительные операции 85
2.4. Язык манипулирования данными 95
2.4.1. Синтаксис оператора извлечения данных 97
2.4.2. Преимущества разработанного языка манипулирования данными 100
Выводы 103
3. Принципы физической организации данных и эффективного выполнения операций манипулирования данными 104
3.1. Физическая организация данных для быстрого поиска информации с учетом интерполяции (ІСВ-индекс) 105
3.1.1. Обоснование неадекватности традиционных вторичных индексов 107
3.1.2. Исследование IP-индекса и анализ его применимости 111
3.1.3. Построение 1СВ-индекса 117
3.1.4. Алгоритм и сложность вставки в ІСВ-индекс 139
3.1.5. Алгоритм и сложность выборки по 1СВ-индексу 148
3.2. Алгоритмы преобразования меток времени к заданным размерностям 159
3.2.1. Свойства операторов, используемых для описания размерностей времени 160
3.2.2. Преобразование меток времени в случае, когда одна размерность напрямую задана через другую 162
3.2.3. Отношение агрегирования на множестве размерностей времени и его свойства 166
3.2.4. Преобразование меток времени в общем случае 168
Выводы 173
4. Система архивации параметров технологических процессов 174
4.1. Назначение системы и требования к ней 174
4.2. Архитектура и реализация системы 175
4.2.1. Ядро системы 177
4.2.2. Модуль настройки 183
4.3. Результаты практического применения системы на Жигулевской ГЭС (г. Жигулевск) 184
4.3.1. Сокращение размера запросов 187
4.3.2. Скорость выборки данных с учетом интерполяции с использованием ICB-индексов и объем, занимаемый индексами 194
Выводы 197
Заключение 198
Список использованных источников 200
- Поддержка возможности восстановления отсутствующих данных
- Описание множеств меток времени одной размерности (календарей)
- Преобразование меток времени в случае, когда одна размерность напрямую задана через другую
- Скорость выборки данных с учетом интерполяции с использованием ICB-индексов и объем, занимаемый индексами
Введение к работе
Актуальность темы диссертационной работы. Базы данных (БД) уже несколько десятилетий повсеместно используются на самых различных предприятиях. В настоящее время постоянно растет интерес к проблемам хранения в БД исторических данных, что вызвано необходимостью принятия решений на основе не только текущей информации, но и информации за предыдущие периоды работы предприятия [37]. Поэтому все большее распространение получают особые БД - так называемые хранилища данных (ХД). ХД - это "предметно-ориентированная, содержащая исторические данные, неразрушаемая совокупность данных, предназначенная для поддержки принятия управленческих решений" [67]. Характерными особенностями ХД являются:
интеграция всех видов данных о предприятии;
хранение истории данных;
агрегирование данных для представления в виде отчетов;
большой объем данных: 50 - 500 Пб.
Для ряда предприятий (например, для промышленных и медицинских предприятий, для бирж, для научно-технических центров и т.д.), кроме хранения данных о предприятии в целом, характерны сбор и хранение измерительной и отчетной информации и протоколов различных событий (действия операторов, технологические и аварийные события и др). Эта информация хранится в виде хронологических последовательностей (ХП). Хранилища данных, содержащие ХП, имеют свою специфику.
Во-первых, для них необходима возможность восстановления отсутствующих данных (например, с помощью интерполяции); восстановленная информация должна учитываться в операциях манипулирования данными.
Во-вторых, метки времени различных ХП могут иметь различные специфические размерности (например, производственные размерности, такие как "рабочая смена" или "двухчасовка"). При этом зачастую возникает необходимость перехода от одной размерности к другой (например, для формирования сводок за различные отчетные периоды), а также выполнения операций над несколькими ХП в условиях, когда каждая из них имеет метки времени различных размерностей.
В-третьих, необходима возможность формулировки запросов, учитывающих хронологическую упорядоченность данных.
В настоящее время в практике построения хранилищ данных доминирует реляционная модель данных. Однако ни одна из перечисленных особенностей хранилищ данных, содержащих хронологические последовательности, не может быть полноценно учтена при ее использовании [32, 91, 108, 116, 119]. Безусловно, ХП пред ставима в реляционной модели. Однако операторы реляционной модели предназначены лишь для манипулирования данными, явно присутствующими в БД, поэтому запрос, учитывающий данные, восстановимые с помощью интерполяции, сформулировать невозможно. Методы эффективного доступа, разработанные для реляционной модели, позволяют осуществлять поиск лишь среди явно хранящейся в БД информации, не учитывая интерполяцию. В реляционной модели отсутствует возможность описания пользовательских размерностей времени и логика их преобразования, и, как следствие, крайне затруднена формулировка запросов, требующих перехода из одной размерности времени в другую. И, наконец, запросы, учитывающие упорядоченность, невозможны в реляционной модели, основной структурный элемент которой - неупорядоченное множество кортежей.
В результате, попытки реализовать логику работы с хронологическими последовательностями на основе реляционной модели данных зачастую приводят к тому, что хранилище данных используется только для хранения информации, а большая часть логики манипулирования данными реализуется в прикладной программе [20, 107]. В результате стоимость прикладного программного обеспечения неоправданно повышается (примерами такого программного обеспечения могут служить специализированные промышленные системы, предназначенные для хранения и обработки хронологических последовательностей, такие как Industrial SQL Server [113], PI Data Storage [123] и др). Именно, поэтому на симпозиуме, посвященном обсуждению перспективных направлений исследований в области баз данных на ближайшие 10 лет, прошедшем в 1998 году в Асиломаре, одной из актуальных проблем была признана "поддержка логики приложений в среде базы данных" [3].
Следовательно, актуальной задачей является разработка модели данных, учитывающей специфику хранилищ данных, содержащих хронологическую информацию, а также языков и методов эффективного манипулирования для хронологической информации.
Краткий анализ существующих моделей данных и обоснование выбранного подхода к решению проблемы. В настоящее время альтернативой реляционной модели данных являются объектные (объектно-ориентированная и объектно-реляционная) модели данных (иерархическая и сетевая модели не рассматриваются в связи с тем, что они морально устарели и были полностью вытеснены реляционной моделью [9]). Однако применение этих моделей для построения хранилищ данных, содержащих хронологическую информацию, не решает проблемы учета их специфики, как минимум по двум причинам:
• объектные модели данных не являются моделями данных в полном смысле этого слова, а являются лишь способами разработки моделей данных, т.к. они не предоставляют структур данных и операций для манипулирования ими, а лишь описывают идеологию (инкапсуляция, наследование, полиморфизм [5]), согласно которой эти структуры данных и операции должны разрабатываться (в то время, как данная работа посвящена именно разработке структур данных для представления хронологических последовательностей и размерностей времени, операций для манипулирования ими, и методов эффективного исполнения этих операций);
хранилищам данных свойственна интеграция реляционных данных и хронологических последовательностей, с возможностью использования данных разной природы в рамках одного запроса, что невозможно (или, как минимум, неудобно), если хронологические последовательности будут представлены в рамках объектной модели данных.
В связи с вышесказанным, отказ от реляционной модели был признан нецелесообразным, и было принято решение о разработке модели данных, предназначенной для хранилищ данных, содержащих хронологическую информацию, на основе реляционной модели.
Существует целый ряд научных работ, посвященных разработке моделей и методов доступа для исторических данных (см. библиографии [97, 100]). Данным вопросом занимались ученые К.Дж. Дейт, Р.Т. Снодграсс, Дж. Клиффорд, К.С. Дженсен, А. Сиджев, Н.А. Лоренцос и др., а также российские ученые Л.А. Калиниченко, Б.А. Новиков, М.Г. Манукян. Однако большинство исследований в этой области ограничивалось разработкой операций над историческими данными, основанных на операторах над интервалами и множествами интервалов времени, и методов исполнения таких операций. При этом оставались плохо проработанными проблемы, связанные с данными, организованными в виде хронологических последовательностей -формулировка и исполнение запросов, учитывающих данные, восстановимые с помощью интерполяции, а также запросов, использующих специфические размерности времени и хронологическую упорядоченность данных.
В то же время задача хранения и предварительной обработки хронологических последовательностей в базах данных признается актуальной для экономических приложений [14, 60, 119], автоматизированных систем управления технологическими процессами (АСУТП) [28, 48, 49, 114], автоматизированных систем научных исследований (АСНИ) [11, 86, 115] др. Поэтому существует большое число научных работ, в которых, хотя и не предлагаются решения всех проблем хранилищ данных, содержащих хронологическую информацию, но рассматриваются подходы к решению некоторых из них.
Так, проблема формулировки и эффективного исполнения запросов на выборку данных с учетом интерполяции рассматривалась в работах [7, 14, 17, 34, 45, 52, 64, 65, 70, 73, 74, 79, 92, 93], ей занимались ученые Дж. Клиффорд, Л. Лин, Т. Риш, М.Р. Когаловский, А.И. Гуляев и др. Однако лишь Л. Лин, Т. Риш в работах [73, 74] предлагают способ физической организации данных (ІР-индекс), предназначенный для эффективного поиска данных с учетом интерполяции и исключающий - необходимость полного просмотра хронологической последовательности. Однако, как показывается в данной диссертационной работе, ІР-индекс для многих реальных хронологических последовательностей имеет неадекватно большой объем, что делает его практически непригодным для ряда задач. Тем не менее, в диссертационной работе был принят подход, используемый при построении IP-индекса, на базе которого была разработана новая индексная структура, лишена описанного недостатка.
Целый ряд работ ученых К. Беттини, К.С. Ванга, С. Джажодии, К.Е. Дайрсона и др. посвящен проблеме описания специализированных размерностей времени в БД и использования этих размерностей при формулировке запросов [43, 44, 46, 62, 71, 81, 82, 102]. Однако средства описания размерностей времени, предлагаемые в перечисленных работах, ориентированы в основном на экономические приложения, и не позволяют описывать некоторые размерности времени (такие, как "смена"), свойственные промышленным предприятиям. Наиболее перспективной среди перечисленных работ, на наш взгляд является работа [82], основанная на строгой формализации понятия размерности и прелагающая набор алгебраических операций для создания новых размерностей времени на базе существующих. Подход к описанию размерностей времени, используемый в данной диссертационной работе, базируется на работе [82], устраняя присущие ей недостатки.
Проблема формулировки запросов, использующих хронологическую упорядоченность данных, оказалась наиболее подробно изученной из всех проблем манипулирования хронологическими данными. Она рассматривается в работах [14, 53, 59, 70, 88, 89, 92, 93, 94, 95, 118]; наибольший вклад внесли П. Сешадри и Р. Рамакришнан. В данной диссертационной работе анализируются преимущества и недостатки этих работ, и выбирается подход, наиболее перспективный с точки зрения решения проблем рассматриваемых хранилищ данных.
Таким образом, было принято решение строить модель данных для хранилищ данных, содержащих хронологические последовательности, взяв за основу реляционную модель, и используя наиболее перспективные из существующих подходов к описанию размерностей времени в БД и к формулировке и исполнению запросов, использующих интерполяцию и хронологическую упорядоченность данных, развивая эти подходы.
Цели и задачи исследования. Целью исследования является разработка модели данных, языков и методов манипулирования для хронологической информации в хранилищах данных.
Задачами исследования при этом являются:
Анализ существующих моделей данных и методов доступа к данным; оценка их применимости для хронологической информации.
Разработка структур данных и набора операций для манипулирования ими, позволяющих формулировать запросы, использующие интерполяцию, специализированные размерности времени и хронологическую упорядоченность.
Разработка принципов построения языка описания данных и языка манипулирования данными.
Разработка методов физической организации данных и эффективного выполнения операторов манипулирования данными.
Создание программного комплекса на основе разработанных модели и методов.
6. Анализ результатов применения разработанного программного комплекса для построения ХД реально действующего предприятия.
Структура и краткое содержание диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников, справочно-сопроводительных материалов и приложений.
В первой главе рассматривается типичная структура ХД, анализируются виды информации, содержащейся в ХД, и типичные запросы к ней, приводится их классификация. Производится анализ реляционной, объектно-ориентированной, объектно-реляционной и различных временных моделей данных с точки зрения их применимости для построения ХД, содержащих хронологическую информацию. В результате делается вывод о необходимости построения новой модели данных, основанной на реляционной. Затем в работе анализируются существующие разработки в области БД, посвященные проблемам формулировки и эффективного выполнения запросов при наличии интерполяции, проблеме описания пользовательских размерностей времени и проблеме формулировки запросов к упорядоченным данным. Выявляются недостатки существующих подходов, и определяются наиболее перспективные из них для построения собственной модели.
Во второй главе описывается разработанная хронологическая модель данных. Хронологическая модель данных - это 1) структуры данных для представления хронологических последовательностей, меток и размерностей времени; 2) алгебра хронологических последовательностей, предназначенная для манипулирования данными. Вводится формальное определение хронологической последовательности, размерности времени и метки времени, а также понятие сравнимости размерностей времени и операции сравнения меток времени. Рассматриваются принципы построения языка описания данных хронологической модели, предназначенного для описания меток времени, множеств меток времени, размерностей времени, а также для описания структуры хранилища данных. Затем рассматривается алгебра хронологических последовательностей. В ее основу положена реляционная алгебра, дополненная операциями, предназначенными для учета специфики хронологических последовательностей. На базе алгебры хронологических последовательностей построен язык манипулирования данными хронологической модели, также рассматриваемый во второй главе.
В третьей главе описываются принципы физической организации данных и методы эффективного выполнения операторов манипулирования данными хронологической модели. Особое внимание уделяется эффективной выборке данных с учетом интерполяции, для поддержки которой разработана специальная физическая организация данных - ICB-индекс. Анализируется эффективность выборки с использованием ICB-индекса, занимаемый им объем и время вставки данных. Производится сравнение с существующими индексными структурами. Также в третьей главе описываются алгоритмы преобразования меток времени к произвольной размерности. Такое преобразование требуется для выполнения некоторых операторов хронологической модели, для представления меток времени по различным шкалам, сравнения меток времени и т.д.
В четвертой главе рассматривается система архивации параметров технологических процессов (САПТП), построенная на базе разработанной модели и методов. Анализируются практические результаты применения САПТП для построения хранилища данных Жигулевской ГЭС, демонстрируются преимущества разработанной модели.
В заключении приводится обзор проделанной работы, основные положения диссертации, практические результаты, и пути дальнейшего исследования.
В конце текста диссертации приведены справочно-сопроводительные материалы: перечень использованных сокращений, перечень таблиц и иллюстраций.
В приложениях приводятся доказательства утверждений и копия акта внедрения.
Основные результаты диссертации опубликованы в работах [22-28, 35, 36, 76, 109]. Работы [22-28, 76] написаны автором лично, в работах [35, 36, 109] постановка задачи построения хронологической модели данных рассматривалась совместно с научным руководителем, к.т.н., доц. Сидоровым А.А. Все остальные включенные в работу результаты получены автором лично.
Научная новизна. В ходе работы получен ряд новых результатов.
Впервые разработана хронологическая модель данных, предназначенная для хронологической информации, содержащейся в хранилищах данных.
Разработаны новые методы описания размерностей времени, меток времени и множеств меток времени, на основе которых построен язык описания данных. Исследованы свойства размерностей времени, применяемые для оптимизации их преобразования.
Разработан новый способ физической организации данных (1СВ-индекс), позволяющий осуществлять быстрый поиск данных с учетом интерполяции.
Практическая ценность и реализация результатов работы. На основе разработанных модели и методов была реализована система архивации параметров технологических процессов, внедренная на Жигулевской ГЭС (г. Жигулевск). Ее использование упростило формулировку запросов и обеспечило высокую скорость выборки данных, что подтверждено актом внедрения.
На защиту выносятся:
хронологическая модель данных;
методы описания размерностей, меток и множеств меток времени;
физическая организация данных, позволяющая осуществлять быстрый поиск информации с учетом интерполяции (ICB-индекс);
система архивации параметров технологических процессов, построенная на базе разработанных модели и методов, и результаты ее применения на Жигулевской ГЭС.
Поддержка возможности восстановления отсутствующих данных
Итак, как было отмечено в предыдущем разделе, "чисто объектные" СУБД обладают целым рядом недостатков. Поэтому целесообразность их использования вызывает сомнение у многих теоретиков баз данных. В связи с этим у ряда исследователей возникла идея объединения преимуществ, предлагаемых объектно-ориентированной технологией, и возможностей реляционной модели данных. Эта идея была сформулирована во втором манифесте, посвященном объектным СУБД - "Манифесте систем баз данных третьего поколения" [98]. Указанный манифест противопоставляется первому манифесту [41], утверждая, что современные базы данных должны не только включать поддержку объектно-ориентированной технологии, но и полностью поддерживать реляционную модель данных. Модель, построенную на подобном объединении двух технологий, принято называть объектно-реляционной. Однако в манифесте [98] пропагандируется поддержка не реляционной модели в чистом виде, а языка SQL. При этом язык SQL активно критикуется известными теоретиками К. Дейтом и X. Дарвеном за его весьма существенные отклонения от классической реляционной модели. Ими был написан третий манифест (посвященный объектно-реляционным БД) [56, 58], в котором утверждается, что объектно-реляционные БД должны основываться на классической реляционной модели, а единственным объектным расширением должна быть развитая поддержка типов данных. Т.е. предлагается включить в модель объектные классы, наследование и другие принципы объектно-ориентированного подхода, но при этом объектные классы должны быть лишь разновидностью доменов реляционной модели, а объекты-экземпляры этих классов - храниться в качестве значений атрибутов. В работе [58] утверждается, что принципы объектно-реляционных БД, предлагаемые во втором манифесте [98], сильно искажают классическую реляционную модель, что влечет за собой целый ряд негативных последствий, поэтому современные объектно-ориентированные системы должны базироваться на третьем манифесте.
Таким образом, согласно подходу К. Дейта и X. Дарвена, для поддержки в объектно-реляционной модели данных таких структур, с которыми нельзя эффективно работать в реляционной модели, необходимо включать в модель новые типы данных, предназначенные для описания этих структур, и операторы для манипулирования этими структурами. Например, СУБД Oracle, IBM Informix и IBM DB2 (см. раздел 1.4.3.4) включают таким способом поддержку финансовых временных рядов. В них включен тип данных "временной ряд", и разнообразные операции над временными рядами, которые используют временной ряд как единое целое (как атомарное значение).
Однако и объектно-реляционная модель не решает проблем хранилищ данных, содержащих хронологическую информацию. Во-первых, она не является готовым решением, а предоставляет только средства для включения новых объектов в БД. Для того чтобы воспользоваться этими средствами, необходимо разработать структуру этих объектов и операции над ними. Именно так дело обстоит с метками времени, размерностями времени и хронологическими последовательностями - необходимо разработать способ их описания и операции над ними (одна из задач, решению которых посвящена данная диссертационная работа). Во-вторых, хронологические последовательности крайне нежелательно представлять в виде объектов, являющихся значениями атрибутов в отношении. К хронологическим последовательностям зачастую требуется применять операции реляционной алгебры. Более того, зачастую необходимо формулировать запросы, объединяющие обычные реляционные данные и хронологические последовательности. Например, пусть имеется хронологическая последовательность некоторых технологических событий на предприятии, в которой каждое событие имеет определенный тип, и отношение, содержащее для каждого типа события подробную информацию об этом типе. Вполне естественной в такой ситуации является операция соединения указанных хронологической последовательности и отношения по типу события. Для того, чтобы такая операция была выполнима, в модели данных должна быть возможность рассматривать хронологическую последовательность как разновидность отношением (а не как значение атрибута внутри отношения). Поэтому модель для хронологической информации хранилищ данных должна базироваться на реляционной модели.
Согласно [84], временная база данных (англ. temporal database) определяется тем, что хранит данные, изменяющиеся во времени. В отличие от традиционных баз данных, предназначенных для представления мгновенного снимка некоторой части реальЦого мира, временные базы данных предназначены для представления некоторой части реального мира на протяжении некоторого ограниченного или неограниченного интервала времени. В таких базах данных каждый элемент данных представляет собой некоторый факт, снабженный интервалом времени, в течение которого он был истинным.
Данный раздел умышленно был назван " Модели для временной информации", а не "Временная модель данных", т.к. временная информация может быть представлена в различных моделях - существуют работы, предлагающие представлять ее на базе реляционной, объектно-ориентированной, объектно-реляционной или некоторой другой, специализированной временной модели. Временные базы данных получили внимание весьма большого числа исследований (см., например библиографии [97, 100] и книги [57, 99]). В данном разделе приводится обзор характерных особенностей временных данных (и проблемы, связанные с ними); также приводится краткое описание временной модели, построенной на базе реляционной, и являющейся обобщением многих разрозненных исследований и моделей в этой области. Целью этого обзора является подтверждение того факта, что, несмотря на то, что хронологические последовательности являются частным случаем временной информации (а значит, к ним применимы все разработки в области временных баз данных), ни одна временная модель данных не решает проблем формулировки и эффективного исполнения специфических видов запросов, свойственных хронологическим последовательностям, перечисленным в разделе 1.1. Это связано с тем, что исследования в области временных баз данных решали общие проблемы манипулирования временной информацией, при этом не решая частных проблем манипулирования хронологическими последовательностями. В завершающей части данного раздела приводится актуальный обзор научных работ, затрагивающих отдельные проблемы поддержки хронологических последовательностей в ХД.
Описание множеств меток времени одной размерности (календарей)
Непосредственно из определения 2.7 следует, что если существует описание метки времени (г, jun) по шкале juy:ju2: ...:jun, то, во-первых, оно единственно, а во-вторых, оно однозначно определяет эту метку времени (т.е. не существует другой метки времедш размерности /лп, имеющей такое же представление по шкале Ц\. г. ... ://„).
Определим теперь понятие описания по шкале jui:/u2:...:jun метки времени (г, if) для случая г] = /ип. Определение 2.8. Пусть размерность времени rj сравнима с р.ь і = \...п. Описанием метки времени (г, rj) по шкале /Лі ./Лг ... ://„ будем называть описание метки времени (г , jun) по этой шкале, если (г , цп) пересекается с (г, 77). Очевидно, что в случае г\Ф jun представление метки времени (г, rj) по шкале jUi:jU2 . ...:jun может быть не единственным и не однозначным. Пример 2.4. С помощью шкал можно описывать такие метки времени, как, например, "третий вторник января 2004 года". Для этого необходимо описать размерность вторник (например, с помощью операторов раздела 2.2.3) и задать метку времени размерности сутки по шкале год\месяц:вторник следующим образом: 2004:1:3. После этого заданную таким образом метку времени можно потребовать представить и по другой шкале, например, год:месяц:сутки, в результате будет получен ответ на вопрос, какого числа будет третий вторник января 2004 года. У шкал имеется целый ряд назначений: 1. представление пользователю меток времени, хранящихся в базе данных, в удобном для него виде; 2. предоставление пользователю возможности описывать интересующие метки времени в удобном для него виде; 3. предоставление пользователю возможности описывать множества меток времени и новые размерности времени. В первом случае пользователь указывает интересующую его хронологическую последовательность и шкалу, по которой должны быть представлены все ее метки времени. Например, метки времени хронологической последовательности, содержащей ежедневные данные, можно представить по шкале год\месяц:сутки или по шкале год:неделя:сутки. При этом система автоматически представляет метки времени по шкале на основе информации о том, каким образом одни размерности времени заданы через другие. Алгоритм представления метки времени по произвольной шкале обсуждается в третьей главе. Во втором случае пользователь указывает шкалу, и задает интересующие его метки времени с помощью их представления по шкале. Это может использоваться, к примеру, для задания наборов меток времени при запросе на выборку данных хронологической последовательности, относящихся к указанным меткам времени. Например, имея ежедневную хронологическую последовательность, пользователь может запросить данные за первый и третий вторник сентября 2004 года. Для этого надо указать шкалу год:месяц:вторник, и задать две метки времени размерности сутки с помощью представлений 2004:09:01 и 2004:09:03. Очевидно, не любая запись вида Т\:т2: ... :тп, где гг (i = 1...п) - целые числа, является представлением некоторой метки времени заданной размерности rj по заданной шкале jU\:jU2 . ... :jun. В частности, 2003:12:32 не является представлением ни одной метки времени размерности сутки по шкале год:месяц:сутки, т.к. не существует 32 декабря 2003 года. Ниже приводится достаточное условие того, чтобы запись вида Т\\т2: ... :тп, где г, (і = \...п) -целые числа, являлась описанием некоторой метки времени (т, /лп) по шкале Утверждение 2.3. Пусть задана шкала ju\: i2 - ..:/4 и пусть с каждой меткой времени размерности ju \ пересекается не менее М, меток времени размерности juh і = 2...п (для выявления данного факта можно пользоваться свойствами, которые формулируются в разделе 3.2.1). Тогда для того, чтобы запись вида Х\\т2: ... :тп, где гг (/ = 1 ...п) - целые числа, являлась представлением некоторой метки времени размерности /лп по шкале /2i:/u2:ju3:...:jun, достаточно выполнения следующих условий: данного утверждения непосредственно следует из определения 2.7. При задании метки времени (г, rf) через ее представление тх:т2. ... \т„ по шкале Ц\./л2. -Ип кроме явного указания элементов г,- (/ = 2...п) будем также использовать обозначение last. Данное обозначение, встречающееся на месте г„ обозначает следующее: last(/dh и_і) -first(pb tt-i), где ti - метка времени размерности juh имеющая представление Т\.ТЇ. ... :ъ ПО шкале JUI:JU2: ... ./НІ, а оператор last(rj, (г, /І)), возвращает максимальное значение из таких т\ что метка времени (г1, rj) пересекается с (г, //). Например, запись 2QQ3:last по шкале год:неделя описывает последнюю неделю 2003 года. Кроме того, с помощью шкал, допуская в записи Т\:т2: ... :тп не только числа, но и множества чисел, мы будем описывать множества меток времени и новые размерности времени (см. разделы 2.2.2 и 2.2.3).
Преобразование меток времени в случае, когда одна размерность напрямую задана через другую
Предполагается, что способ интерполяции задается извне, т.е. явно назначается пользователем или администратором хранилища данных. Наиболее распространенные способы интерполяции могут быть описаны в СУБД изначально (например, кусочно-постоянная интерполяция для числовых и нечисловых атрибутов, кусочно-многочленная интерполяция для числовых атрибутов и т.д.), а специфические - задаваться пользователем. При этом при формулировке запроса должен указываться только идентификатор требуемого способа интерполяции.
С вводом поддержки интерполяции в алгебру ХП связан ряд вопросов. 1. Может ли для одной и той же хронологической последовательности использоваться несколько различных способов интерполяции? 2. Результат оператора INTERPOLATE может иметь большую мощность. Каким образом он представляется конечному пользователю? 3. С помощью каких методов обеспечивается эффективное исполнение запросов, использующих интерполяцию? Рассмотрим последовательно ответы на эти вопросы. Использование различных интерполирующих функций для одной хронологической последовательности Для большинства приложений свойственно совместное решение задач выбора дискретизации измеряемых параметров и выбора способа их интерполяции. Поэтому использование для интерполяции способа, отличного от того, который учитывался при выборе дискретизации, может привести к непредсказуемым погрешностям интерполяции. В связи с этим имеет смысл жестко назначать способ интерполяции для каждого из атрибутов хронологической последовательности, и при выполнении оператора INTERPOLATE использовать только его. Исключение составляет лишь кусочно-постоянная интерполяция, которая требуется в случаях, когда хронологическая последовательность, содержащая результаты некоторых измерений, интерпретируется не только как носитель информации о значениях измеряемого параметра, но и как носитель информации о самих событиях измерения. Примером может служить запрос: "Для каждой метки времени календаря С определить время последнего предшествующего ему измерения и полученный результат измерения", ответить на который можно, применив к хронологической последовательности измерений кусочно-постоянную интерполяцию, и выполнив оператор выборки по календарю С.
В соответствии с вышесказанным, язык описания данных хронологической модели должен включать средства назначения способа интерполяции атрибутам хронологических последовательностей, а язык манипулирования данными должен включать поддержку оператора INTERPOLATE, допуская выбор между кусочно-постоянной интерполяцией и способом интерполяции, назначенным операнду.
Представление результата операции INTERPOLATE пользователю Результат операции INTERPOLATE может иметь большую мощность. В связи с этим использование данного оператора допускается лишь в связке с последующей выборкой по календарю (в этом случае хронологическая последовательность будет содержать данные только для меток времени, входящих в календарь), или с выборкой по условию, наложенному на невременной атрибут, с последующим применением операции calendar (в этом случае результатом будет не ХП, а календарь, который можно использовать в других операциях выборки). Это позволит, во-первых, представлять результат запроса в более компактной форме, а, во-вторых, разработать методы эффективного выполнения описанных связок операторов, которые не материализуют результат операции INTERPOLATE, а сразу вычисляют результат ее связки с выборкой.
В соответствии с вышесказанным, язык манипулирования данными должен операцию INTERPOLATE не в виде самостоятельного оператора, а, во-первых, в виде модификатора для оператора выборки по календарю, и, во-вторых, в виде оператора, выполняющего связку операций INTERPOLATE - о - calendar.
Пусть хронологическая последовательность R содержит неэквидистантный временной ряд показаний датчика. Необходимо получить значения измеряемого параметра на границе каждых 10 секунд в течение всех воскресений января 2003 года. Такой запрос формулируется следующим образом: а (INTERPOLA TE(R, I), periodic((ro, миллисекунда), 10000) слраиет(год\месяц, 2003:01, воскресенье)). Исполнение запросов, использующих интерполяцию Исполнение выборки по календарю при включенной интерполяции не представляет труда - для этого достаточно вычислить значения интерполирующей функции для меток времени, входящих в заданный календарь. Исполнение цепочки операций INTERPOLATE — ст — calendar связано с большими трудностями. По сути дела, это есть задача поиска всех меток времени, для которых значение интерполирующей функции F(t), применяемой для восстановления значений параметра, представленного временным рядом, содержащимся в ХП, удовлетворяет условию 0. Проблема заключается в том, что для восстановления параметров, представленных временными рядами, обычно используют интерполирующие функции F, склеенные из функций Fi, і- l...w-І, где п - количество отсчетов временного ряда (например, кусочно-линейная интерполяция, кусочно-квадратичная интерполяция, интерполяция сплайнами [2, 8, 18]). При этом каждая функция Fh г = 1... и-1, задана на интервале между соседними отсчетами временного ряда, и для ее построения требуются ближайшие к этом интервалу отсчеты временного ряда.
Скорость выборки данных с учетом интерполяции с использованием ICB-индексов и объем, занимаемый индексами
В данной главе рассматриваются принципы физической организации данных и методы, предназначенные для эффективного исполнения операций над хронологическими последовательностями.
В таблице 3-1 для каждой из операций алгебры хронологических последовательностей приводятся методы, позволяющие их выполнять. Как видно из таблицы 3-1, для выполнения операций алгебры хронологических последовательностей, кроме существующих методов и алгоритмов, требуются алгоритм поиска информации с учетом интерполяции, алгоритм сравнения меток времени различных размерностей, алгоритм получения элементов календаря по его описанию (имеется в виду описание с помощью средств, введенных в разделе 2.2.2), а также алгоритм преобразования меток времени к произвольной размерности.
Нетрудно убедиться, что алгоритм сравнения меток времени различных размерностей и алгоритм получения элементов календаря по его описанию легко формулируются при наличии алгоритма преобразования меток времени к произвольной размерности, в то время как построение алгоритма поиска информации с учетом интерполяции, а также алгоритма преобразования меток времени к произвольной размерности являются менее тривиальными задачами. Решению первой из них посвящен раздел 3.1, в котором рассматривается новая индексная структура, предназначенная для поиска информации с учетом интерполяции, приводятся алгоритм вставки данных в нее и алгоритм поиска данных с ее помощью. Решению второй задачи - задачи преобразования меток времени - посвящен раздел 3.2.
В разделе 2.4.1 был введен оператор языка манипулирования данными find, предназначенный для выборки данных с учетом информации, восстановимой с помощью интерполяции. Данный оператор крайне важен для хранилищ данных многих предприятий. Рассмотрим в качестве примера хронологическую последовательность, содержащую значения активной мощности одного из гидроагрегатов (ГА) Жигулевской ГЭС за сутки (рисунок 3-1). Типичными запросами к такой хронологической последовательности являются следующие: найти интервалы времени, в течение которых гидроагрегат работал в нормальном режиме с полной загрузкой (интервалы, где мощность больше 100, но меньше 120); найти интервалы времени, в течение которых гидроагрегат работал с предельной загрузкой (интервалы, где мощность больше 120); найти моменты времени, в которые происходила загрузка/разгрузка гидроагрегата по мощности (моменты времени, в которые мощность пересекала границу 50).
Результаты перечисленных типов запросов интересны специалистам сами по себе, и, кроме того, могут использоваться для формулировки более сложных запросов, например: "выбрать ежеминутные показания температур подшипника за последний месяц за те интервалы времени, в течение которых гидроагрегат работал с полной загрузкой".
Все перечисленные виды запросов требуют поиска не только среди данных, явно присутствующих в хронологической последовательности, но и среди данных, восстановимых при помощи интерполяции. Ни в одной современной СУБД нет индексов для быстрого выполнения таких запросов -все современные индексные структуры предназначены для поиска данных, явно присутствующих в БД. Поэтому в хранилищах данных для выполнения указанных видов запросов приходится выполнять полный просмотр файла, содержащего хронологическую последовательность. В то же время для большинства хранилищ данных эффективность выполнения запросов является критическим фактором, что связано с большими объемами хранимых данных. Так, количество записей в хронологической последовательности может достигать миллионов, и полный просмотр хронологической последовательности может занимать много времени. Это особенно критично на фоне необходимости быстрого добавления данных в ХД. Так, в хранилище данных Жигулевской ГЭС хранится около 5000 хронологических последовательностей, около 1000 из которых обновляются ежесекундно. Поэтому, если система сильно загружена запросами, требующими полного просмотра файла, ей может не хватить ресурсов на своевременное обновление всех 5000 хронологических последовательностей.
