Содержание к диссертации
Введение
1 Анализ подходов к прогнозированию социально-экономических показателей и сжатию баз данных. Постановка задач исследования 9
1.1 Цель исследования 9
1.2 Анализ способов решения задачи прогнозирования социально-экономических показателей 11
1.2.1 Характерные особенности прогнозирования социально-экономических показателей... 11
1.2.2 Известные способы решения задачи прогнозирования 14
1.2.3 Выбор подхода к прогнозированию 24
1.3 Анализ подходов к решению задачи компактного представления баз данных социально-экономических показателей 26
1.3.1 Особенности баз данных социально-экономических показателей 26
1.3.2 Методы повышения производительности СУБД 33
1.3.3 Использование методов сжатия данных без потерь информации в СУБД 38
1.4 Постановка задач исследования 46
1.5 Выводы 46
2 Прогнозирование социально-экономических показателей 48
2.1 Модель авторегрессии и проинтегрированного скользящего среднего 48
2.2 Построение прогностических моделей 51
2.3 Вычислительные эксперименты на искусственно сгенерированных данных , 54
2.3.1 Описание экспериментов и результаты 54
2.3.3 Эксперименты для ряда с моделью АРПСС (2,0,0) 64
2.4 Оценка сложности вычислений для предлагаемого подхода 70
2.5 Выводы . 74
3 Алгоритмы сжатия баз данных социально-экономических показателей без потерь информации 76
3.1 Словарное кодирование с сохранением упорядочивания Diet ..77
3.2 Статистическое кодирование на базе контекстного моделирования Context.. 81
3.2.1 Понятия и определения 82
3.2.2 Описание алгоритма 85
3.3 Кодирование с учетом горизонтальных зависимостей между колонками Depend 91
3.3.1 Описание алгоритма , 92
3.3.2 Определение набора факторных колонок (детерминанта) 96
3.4 Теоретические оценки наилучшего и наихудшего коэффициента сжатия... 100
3.4.1 Словарное кодирование с сохранением упорядочивания Diet 100
3.4.2 Статистическое кодирование на базе контекстного моделирования Context 102
3.4.3 Кодирование с учетом горизонтальных зависимостей между колонками Depend 106
3.5 Теоретические оценки скорости выполнения основных операций поиска и извлечения данных из БД в зависимости от коэффициента сжатия 107
3.6 Теоретические оценки сложности алгоритмов экономного кодирования 110
3.6.1 Словарное кодирование с сохранением упорядочивания Diet 110
3.6.2 Статистическое кодирование на базе контекстного моделирования Context 110
3.6.3 Кодирование с учетом горизонтальных зависимостей между колонками Depend 112
3.7 Сводные теоретические характеристики разработанных алгоритмов 113
3.8 Выводы 113
4 Вычислительные эксперименты по прогнозированию показателей развития Санкт-Петербурга и сжатию базы данных 116
4.1 Прогнозирование социально-экономических показателей 116
4.1.1 Описание эксперимента 116
4.1.2 Результаты эксперимента 119
4.2 Экономное кодирование информации базы данных социально-экономических показателей ... 125
4.2.1 Общая характеристика реализации 125
4.2.2 Реализация физических операторов 126
4.2.3 Описание эксперимента 129
4.2.4 Результаты эксперимента 131
4.2.5 Сравнение с СУБД Sybase IQ 135
4.3 Выводы , .138
Заключение 140
Список использованных источников
- Известные способы решения задачи прогнозирования
- Вычислительные эксперименты на искусственно сгенерированных данных
- Кодирование с учетом горизонтальных зависимостей между колонками Depend
- Экономное кодирование информации базы данных социально-экономических показателей
Введение к работе
Актуальность темы. Прогнозирование показателей социально-экономических процессов региона используется в системах поддержки принятия решений как при государственном управлении, так и при управлении масштабной организацией. Вопрос получения прогноза, при котором используется ретроспективная информация о поведении только прогнозируемого показателя, актуален как для задач вычисления прогнозных значений отдельных показателей в кратко- и среднесрочной перспективе, так и для задач комплексного прогнозирования социально-экономического развития. В последнем случае прогнозирование в сочетании с экспертными оценками может применяться при формировании сценариев эволюции экономической системы для комплексного имитационного моделирования развития субъекта Российской Федерации. Применение комплексной модели позволяет достичь сбалансированности прогнозных значений макроэкономических показателей.
Необходимая интерактивность анализа и прогнозирования социально-экономических процессов должна обеспечиваться не только благодаря эффективным алгоритмам обработки данных и прогнозирования, но и за счет быстрого выполнения операций извлечения необходимых данных. При прогнозировании большого числа рядов значений, извлекаемых из БД, основная доля затрачиваемого времени может приходиться на обработку запроса в СУБД. Большой объем баз данных социально-экономических показателей диктует необходимость использования специальных методов повышения производительности СУБД.
Целью работы является разработка алгоритма кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона, а также повышение производительности систем управления большими базами данных социально-экономических показателей за счет использования сжатия данных.
Задачами диссертационного исследования являются: разработка алгоритма кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона на основе модели авторегрессии и проинтегрированного скользящего среднего; разработка алгоритмов сжатия баз данных социально-экономических показателей без потерь информации для повышения производительности СУБД; реализация предложенных алгоритмов в виде комплекса программ, обеспечивающего прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных; проведение вычислительных экспериментов по прогнозированию социально-экономических показателей развития субъекта Российской Федерации, по оценке точности прогноза, получаемого для разработанного алгоритма, по оценке изменения скорости выполнения типовых запросов и уменьшения размера хранимых данных в случае использования алгоритмов сжатия базы данных.
Методы исследования. Для решения поставленных задач в работе использованы: теория вероятностей, математическая статистика, нелинейное программирование, анализ временных рядов, теория кодирования дискретных источников сообщений, теория сложности алгоритмов.
Основные положения, выносимые на защиту:
Алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона на основе набора моделей авторегрессии и проинтегрированного скользящего среднего (АРПСС).
Алгоритмы сжатия баз данных без потерь информации, основанные на словарном и статистическом кодировании с использованием контекстного моделирования.
Комплекс программ, обеспечивающий кратко- и среднесрочное прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных.
Результаты вычислительных экспериментов по прогнозированию, по оценке точности прогноза для предложенного алгоритма, по оценке изменения скорости выполнения запросов к сжатой базе данных и уменьшения размера хранимых данных.
Научная новизна работы состоит в следующем: разработанный алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона отличается использованием набора моделей класса АРПСС, каждая из которых идентифицируется для прогнозирования ровно на к шагов вперед; предложенный алгоритм словарного кодирования для применения в СУБД обеспечивает сохранение упорядочивания и позволяет минимизировать число перестроек словаря при появлении новых значений; разработанный алгоритм словарного кодирования с учетом горизонтальных зависимостей обеспечивает сильное сжатие данных в случае детерминированной или тесной зависимости между столбцами таблицы; разработанный алгоритм статистического кодирования с использованием контекстного моделирования, предназначенный для применения в СУБД, обладает свойством сохранения упорядочивания и не требует больших временных затрат при кодировании новых, ранее не встречавшихся значений атрибута; разработанный комплекс программ обеспечивает кратко- и среднесрочное прогнозирование показателей социально-экономического развития региона по предложенному алгоритму и отличается возможностью хранения и обработки сжатых данных для повышения скорости обработки запросов.
Практическая ценность. Разработан алгоритм прогнозирования социально-экономических показателей развития региона. Предложены алгоритмы сжатия баз данных социально-экономической информации. Создан комплекс программ, обеспечивающий кратко- и , среднесрочное прогнозирование показателей социально-экономического развития региона и позволяющий хранить и обрабатывать сжатые данные. При выполнении вычислительных экспериментов показано, что реализация разработанного алгоритма прогнозирования позволяет увеличить точность предсказания, а реализация алгоритмов сжатия баз данных — достичь более компактного представления хранимых данных и большей скорости обработки запросов, чем известный аналог. Результаты работы могут быть использованы в автоматизированных информационных системах анализа и прогнозирования развития территории.
Внедрение и реализация результатов работы. Основные теоретические и практические результаты были внедрены и использованы в комплексе программ для анализа социально-экономических процессов Санкт-Петербурга и комплексного имитационного моделирования развития субъекта Российской Федерации на примере Санкт-Петербурга. Результаты работы были получены при выполнении хозяйственной договорной научно-исследовательской работы (НИР №199), проведенной Санкт-Петербургским государственным университетом аэрокосмического приборостроения по заданию СПб ГУП «Санкт-Петербургский информационно-аналитический центр».
Полученные в диссертационной работе результаты используются в учебном процессе кафедры вычислительных машин и комплексов ГУАП.
Апробация работы. Основные положения докладывались на: международной конференции «Региональная информатика - 2004» (г. Санкт-Петербург, 22-24 июня 2004 г.), всероссийской научной конференции «Управление и информационные технологии» (г. Санкт-Петербург, 3-4 апреля 2003 г.), трех научных сессиях аспирантов и молодых ученых ГУАП (г. Санкт-Петербург, 2002-2004 годы).
По теме работы опубликовано 7 печатных работ, в том числе одна монография.
Известные способы решения задачи прогнозирования
Множество моделей, используемых для прогнозирования, ограничивается обычно двумя классами линейных моделей: классом стационарных временных рядов и классом однородных нестационарных рядов. Модели первого класса используются в первую очередь для описания поведения случайной компоненты.
Временной ряд у{/) считается стационарным в широком смысле в том случаеі при котором его среднее значение m = Ey(j)t дисперсия er =Djy( ) и ковариация у(т) = Е[(У(Г) - Ey(t)%y(t + г) - Ey(t + г))] не зависят от времени t. Ряд y(t) называется стационарных в узком смысле (строго стационарным), если совместное распределение вероятностей m наблюдений ( ), ( ))-- (0 такое же, как и для m наблюдений y(ti +v),y(t2 +T),...,y(tm +т) при любых m,tjyr. Ряд у(t) считается однородным нестационарным, если в результате вычитания из него неслучайной составляющей f (г) образуется стационарный в широком смысле ряд. Выделяют 4 типа факторов, определяющих динамику временного ряда:
1) долговременные, определяющие общую в сравнительно длительной перспек тиве тенденцию в изменении ряда y(t); тенденция описывается неслучайной и в большинстве случаев монотонной функцией fTP\t) —трендом;
2) сезонные, формирующие периодически повторяющиеся в определенные вре мена года колебания анализируемого показателя у (г); функция суммарного действия сезонных факторов p(t) является неслучайной и периодической;
3) циклические, обусловленные долговременными циклами экономического и природного характера, отличными от сезонных колебаний; результат действия циклических факторов является неслучайной функцией ф{і);
4) случайные, обеспечивающие стохастическое поведение y(t); факторы такого типа не поддаются учету и регистрации, и результатом их воздействия является случайная компонента ("ошибка", "остаток", "невязка") (t).
В конкретном случае не обязательно, чтобы в формировании y(t) участвовали факторы всех четырех типов. Кроме того, часто сезонные и циклические факторы рассматриваются как однотипные и не разделяются. Но, безусловно, всегда требуется наличие компоненты s(t). Иначе процесс детерминированный, и его прогнозирование не должно выполняться средствами математической статистики. Как правило, принимается аддитивная структурная схема влияния факторов на y{t): у(0=/40 + 0 + (0 + (0. где отдельные слагаемые могут быть нулевыми константами в конкретном случае. Также может использоваться мультипликативная схема: y(t) = f (0 р(і)ф(?) -e{t).
Выводы о наличии или отсутствии влияния факторов некоторого типа на у(t) могут основываться на двух источниках информации: содержательный предметный анализ задачи с привлечением экспертных знаний; статистический анализ прогнозируемого ряда y(t).
В целом среди всех подходов к однофакторному прогнозированию (автопрогнозированию) можно отметить: экспоненциальное сглаживание; метод сезонных коэффициентов; методы на основе моделей скользящего среднего; методы на основе моделей авторегрессии; метод Бокса-Дженкинса, или метод прогнозирования на основе модели авторегрессии и проинтегрированного скользящего среднего (АРПСС); метод марковских цепей; спектральные методы; оптимальную фильтрацию; аппроксимацию сплайн-функциями.
Как правило, каждый из перечисленных подходов соответствует целой группе методов, обладающих своими особенностями и областью применимости. Экспоненциальное сглаживание Экспоненциальное сглаживание (ЭС) является простым и очень популярным подходом к автопрогнозированию. Типовыми разновидностями метода являются ЭС для процессов с постоянным трендом, с линейным трендом и для рядов с сезонной компонентой. Сравнительное описание и классификация видов ЭС даны в [6].
Простое ЭС позволяет выявить среднее значение ряда, усредняя предшествующие значения с экспоненциально убывающими весами. Иначе говоря, простое экспоненциальное взвешенное скользящее среднее определяется как і— л ,=о где Я — параметр сглаживания или адаптации, Я є (0,1).
Метод ориентирован на выделение детерминированной составляющей ряда. В предельном случае для f - оо выражение для ул(ї) есть
Для прогнозирования на 1 шаг вперед применяется выражение УС+ 1)= (0 Полезным свойством метода является возможность вычисления очередного прогнозного значения без пересчета всех учитываемых предшествующих элементов. Для рядов с «бесконечной» историей справедливо отношение Ул(0 = (/-1)+(1-ЯМ ) Метод ЭС может быть обобщен на случай полиноминальной неслучайной составляющей, так что
Для учета сезонной компоненты вводится дополнительная характеристика, которая также рассчитывается посредством ЭС. Сезонные компоненты могут учитываться как аддитивные и как мультипликативные. Прогнозное уравнение для аддитивной схемы: где I(f — Т) — сглаженный сезонный фактор в момент t минус Т, при этом Г — период (длина) сезона.
Вычислительные эксперименты на искусственно сгенерированных данных
Для оценки характеристик предлагаемого подхода, при котором для идентификации моделей Mw используется критерий оптимизации (2.5) был проведен ряд компьютерных экспериментов. Исследование были ориентированы на доказательство неслучайности результатов, полученных при прогнозировании реальных временных рядов и приведенных в разделе 4, и оценку стабильности получаемых результатов.
Для совокупности рядов, искусственно построенных как реализации уравнения (2.1) с разными значениями параметров , ai и # , была определена точность прогноза для обычного подхода с использованием модели типа М (далее план 1) и для подхода с использованием моделей М (далее план 2). При идентификации М использовался критерий оптимизации (2.4), при идентификации Л/ А) — его обобщенная форма (2.5), Компонента (t) бралась как случайная величина со стандартным нормальным распределением, (t) є N(0,\). Вычислительные эксперименты отличались следующим: 1) числом параметров модели АРПСС(р ,d ,q)(P yD ,Q), использованной для генерации ряда (модель источника данных); 2) видом модели АРПСС, использованной для прогнозирования ряда (прогнозной модели), в обычном режиме совпадавшей с моделью источника данных; 3) значениями коэффициентов , at и Q.; 4) длиной временного ряда (объемом выборки) и; 5) шириной w «окна», в пределах которого вычислялись прогнозные значения, далее использовавшиеся при сравнении; 6) положением pos «окна» относительно начала ряда; 7) горизонтом прогнозирования /. В рамках пункта 1) были рассмотрены модели источника данных АРПСС(р ,d,q)(P,D,Q)n с числом параметров p,dtq,P,D,Q = 0,2, при этом р , q, Р, Q не равны нулю одновременно.
Пункт 2) был введен для изучения ситуации, при которой структура источника данных значимо отличается от структуры прогнозной модели. Такой случай типичен при решении практических задач, когда об истинной природе источника данных часто можно только догадываться.
Параметр pos — положение «окна» относительно начала ряда — был введен в целях компенсации возможных возмущений, вносимых генератором псевдослучайных чисел, а также обусловленных используемой процедурой нелинейной оптимизации (попадание в локальный экстремум). Идентификация модели (2.1) проводилась по МНК, в качестве процедуры оптимизации использовался метод Гаусса-Ньютона. Вектор изменения Ч? искомых параметров в методе Гаусса-Ньютона определяется как [81 Ч = (ХТХУ1ХТГЪ (2.8) где Ч [1: К] — вектор изменения, или вектор текущих значений искомых параметров; X[n: К] — матрица значений частных производных целевой функции относительно параметров; г\п: 1] — вектор невязок целевой функции; и — объем выборки (обучающей); К — число искомых параметров.
Вектор Ч вычисляется в конце каждой итерации. В начале следующей итерации исходя из определяется значение целевой функции. Если в результате изменения Ч не происходит уменьшения целевой функции, то 4і уменьшается вдвое и целевая функция перевычисляется. Данное действие (подытерация) повторяется либо заданное количество раз, либо пока значение целевой функции не «улучшится». В первом случае процесс оптимизации завершается, во втором выполняется переход к следующей итерации.
Выбор метода Гаусса-Ньютона был определен результатами сравнения нескольких методов нелинейной оптимизации: метода Гаусса-Ньютона; метода Марквардта-Левенберга (Marquardt-Levenberg) [8]; метода направленного случайного поиска Сушкова [65]. Для метода Марквардта-Левенберга вектор 4у определяется по формуле 4 = (xTX+Adiag(xTx)yXTr, где Л — специальный коэффициент; diagVC X J — матрица, полученная из X X путем обнуления всех элементов, не относящихся к главной диагонали матрицы X X .
Перед началом итераций Я присваивается малое значение 10 .В начале каждой итерации исходя из F определяется значение целевой функции. Если значение целевой функции не улучшается, то Л увеличивается в 10 раз, после чего оценка повторяется. При достижении порога для Л (использовалось 1013) или при «улучшении» значения целевой функции итерация завершается. Перед началом следующей итерации Л уменьшается до тах О Д/Ю).
Для нескольких видов моделей производилось оценивание параметров с помощью трех указанных методов. В рамках рассмотренных моделей и тестовых выборок не было отмечено статистически значимых расхождений оценок параметров (проводилось попарное сравнение дисперсий рядов оценок параметров по критерию Фишера). В качестве иллюстрации на рисунке 8 даны величины отклонений оценок параметров от реальных величин для нескольких моделей АРПСС(р ,d,q){P,D,Q)n с параметрами p,d,q,P,D,Q, принимающими значениями 0, 1, 2.
Кодирование с учетом горизонтальных зависимостей между колонками Depend
Второй этап экспериментов Как и на первом этапе экспериментов, для некоторых наборов значений параметров at не было получено надежных оценок для прогнозной модели из-за не сходимости процесса оптимизации. В исследование были включены данные, соответствующие только таким наборам af, для которых были получены надежные оценки для планов 1 и 2 одновременно. В результате размер выборки п составил 450. Шаг изменения параметров w, pos , Д), а2, I аналогичен использованному на первом этапе.
Результаты экспериментов приведены в таблицах 10 и 11. Сравнение таблицы 10 с родственной ей таблицей 8 показывает, что, как и следовало ожидать, при несоответствии модели источника прогнозной модели ошибка прогноза больше.
Оценка сложности вычислений для предлагаемого подхода
Использование предлагаемого подхода подразумевает идентификацию / моделей при горизонте прогнозирования /. Сложность вычислений складывается из двух составляющих: сложность вычисления целевой функции; сложность вычисления вектора изменения 4х в процедуре оптимизации выражения (2.8). Сложность вычисления целевой функции определяют затраты на расчет X и г.
При оценке сложности будут учитываться только операции умножения, поскольку стоимость таких операций (в смысле затрат машинного времени) обычно в разы больше стоимости операций сложения.
Использование предлагаемого подхода увеличивает сложность вычисления целевой функции, но трудоемкость вычисления собственно Ч остается постоянной. Из (2.8) следует, что вычисление Ч из известных Х[п:К] и г[и:1] предполагает выпол нение пКК + КпК + пК 2пК + пК операций умножения. Поэтому функция трудо емкости вычисления 4у имеет порядок пК .
Из (2.1) следует, что все искомые параметры, за исключением , входят в уравнение АРПСС один раз как сомножитель. Поэтому для обычного подхода расчет значения целевой функции {t + \\t) ={y{t + l) p(t + \\t)) требует выполнения К -1 +1 = К операций умножения, когда в число оцениваемых параметров входит свободный член , и К + 1 в противном случае. Следовательно, вычисление целевой функции имеет сложность 0(К).
Вычисление частных производных целевой функции, в силу линейного характера выражения (2.1), также имеет сложность О(К), Поэтому трудоемкость определения Х[м: К] имеет порядок КпК = пК .
Невязка г[и:1] непосредственно определяется целевой функцией, поэтому вычисление г[п: 1] имеет сложность 0{К). Из приведенных выкладок следует, что сложность каждой итерации при обычном подходе можно оценить как 0(К) + 0(пК2) + 0(пК2) = 0(пК2), поскольку слагаемым О(К) можно пренебречь.
При предлагаемом подходе трудоемкость вычисления целевой функции значительно увеличивается. Это обуславливается тем, что все авторегрессионные слагаемые, неизвестные в момент /, заменяются их оценками по уравнению (2.1). Каждая такая замена добавляет до К операций умножения. Общее число умножений NmuI( при вычислении e(t + k\t) зависит от: числа членов авторегрессии р\ в общем случае учитывающего как обычную, так и сезонную авторегрессионную компоненту; текущей дальности прогнозирования k,k = \,l. Необходимо найти Nmu!( -Nmuh(p\k). С ростом к на 1 число умножений также увеличивается на 1 вследствие использования оценки fit — ї) вместо у (/ — /). Следовательно, в данном случае
Nmul((l,k) = k. Если авторегрессионый член является сезонным, то использование вместо y(t — і) оценки f{t —і) необходимо только при і Т , где Т — период сезонности. Поэтому в общем случае Nmuh (l,fc) к.
Ряд чисел 5,- образует фрагмент последовательности Фибоначчи2: 1, 2, 3, 5, 8, 13,... s., Sj+l, (я, +s-+i), ... Действительно, 5, равно сумме числа сомножителей y(t — i), «появившихся» впервые в выражении для f(t\г — /), и числа сомножителей y(t — i), «унаследованных» из выражения для y (t\t — i + \). Такие «унаследованные» элементы имеют входящие вертикальные стрелки на рисунке 12. тл А« (і + УзУ- - У Известно, что для последовательности Фибоначчи sf = i- т ,—— 2 V5 [66].
Таким образом, зависимость 5, = s(/) имеет степенной характер. Их свойств степенной функции следует, что функция суммы последовательности Фибоначчи, которую можно найти интегрированием sf =5(/), также имеет степенной характер. Поэтому функция Nmu!t(p =2,k) имеет порядок 2 = (р ) . То, что несколько авторегрессионных членов могут быть сезонными, не меняет общности вывода. Для р =3 и АРПСС (3,0,0) выполняется соотношение
Экономное кодирование информации базы данных социально-экономических показателей
Для экспериментальной проверки полезности предложенных алгоритмов экономного кодирования была разработана рудиментарная РСУБД. Была реализована функциональность модуля выполнения, менеджера ресурсов, менеджера буфера и модуля доступа к данным (см. приложение А). Программный комплекс имеет только машинный интерфейс. ПВЗ задается и запускается на выполнение посредством инструкций машинного интерфейса.
Реализация выполнена на языке C++ в среде разработки программ Microsoft Visual Studio. Общий размер программного комплекса примерно 12.5 тыс. строк кода. Реализовано 44 класса объектов. Экспериментальная СУБД ниже обозначается как CDB (от Compressed DataBase — «сжатая база данных»).
Обеспечена возможность создавать реляционные таблицы и выполнять к ним запросы на чтение. Результаты запросов могут быть сохранены как отчеты в формате текста или HTML. Ограничения по набору физических операторов указаны в следующем пункте. Таблицы могут иметь колонки следующих типов: 1) строка фиксированной длины CHAR; 2) строка переменной длины VARCIIAR; 3) целое INT, внутренний размер 4 байта; 4) целое SMALLINT, внутренний размер 2 байта; 5) целое TINYINT, внутренний размер 1 байт; 6) число с плавающей точкой DECIMAL, внутренний размер 8 байтов; 7) уникальный идентификатор записи RID, внутренний размер 6 байтов; 8) дата DATE, внутренний размер 10 байтов; 9) дата и время DATETIME, внутренний размер 19 байтов. Максимальный размер записи (строки таблицы) ограничен размерами страницы файла данных, но при этом не может быть больше 216 — 2 байтов. Аналогичные ограничения наложены на размер полей CHAR и VARCHAR.
Обеспечена возможность кодирования и декодирования данных по предложенным алгоритмам Diet, Context и Depend для столбцов любого типа. Во всех случаях для способов Diet и Context при сжатии сохраняется упорядочивание. Также реализован известный способ кодирования числовых данных упаковкой битов. Сжатие осуществляется через представление разности между текущим числом и минимальным среди всех имеющихся значений столбца.
Физические операторы реализуются как итераторы унифицированного вида. Под итератором понимается логический элемент ПО (модуль, класс и т.п.), обеспечивающий выдачу очередного результирующего tR при каждом обращении элемента потребителя. Итераторы объединяются в древовидную структуру в соответствии с ПВЗ, так что один итератор может являться источником данных для другого. Итератор должен обеспечивать выполнение операций:
1) «Инициализация» — подготовка выдачи tR, инициализация внутренних структур данных, всех вложенных итераторов (являющихся, как правило, аргументами операции инициализации) и прочих источников данных;
2) «ВыдатьСледующий» — возвращение очередного результирующего tR и соответствующее обновление структур данных для последующих вызовов; как правило, реализация данной операции содержит вызовы «ВыдатьСледующий» итераторов-источников;
3) «Завершение» — завершение итеративного процесса выдачи tR при невозможности продолжения или после получения необходимого количества кортежей, очистка структур данных; как правило, выполняется вызов операции «Завершение» всех итераторов-источников,
В рамках экспериментального программного комплекса были реализованы операторы: 1) последовательного доступа TSC{R); 2) индексного доступа / (й), в качестве индексной структуры применено В+-дерево [72]; 3) агрегации yLE\R) с вычислением суммы sum, среднего avg, минимального значения min, максимального значения max, числа значений cut; 4) сортировки TL\R) методом двухфазного многоканального слияния; 5) тета-соединения х методом вложенного цикла; с 6) соединения по эквивалентности X методом сортировки; 7) сохранения отношения SA VE; 8) сохранения PRINTL результата выполнения запроса в виде отчета; данный оператор реализует также функциональность проекции жь \R); 9) сжатия PACKER с сохранением результата в табличном файле.
Результат работы операторов TSc\R)i ISC{R), PR1NTL может быть представлен как в сжатом (закодированном) виде, так и в декодированном. В типовой ситуации сжатые данные декодируются только при формировании результата оператором PRINT,.
Для оценки влияния использования сжатия на производительность РСУБД группа типовых запросов выполнялась к незакодированной и к сжатой таблице фактов (таблица Value), содержавшей значения СЭП субъектов Российской Федерации. Описание структуры таблицы и сведения об использованном способе экономного кодирования для каждой колонки приведены в приложении Г. В качестве тестового набора были использованы перечисленные ниже запросы.
1. Извлечение временного ряда показателя по заданной территории и для заданного шага по времени. В форме SQL: select from value where id_ind=X and id_territory=l and spacing=0 and actual_for_isl= 1 order by year В запросе использованы колонки таблицы Value: id_ind — код показателя, значение X задается; id_territory — код территории (1 соответствует Санкт-Петербургу); spacing — шаг по времени (0 соответствует году, 1 — кварталу, 2 — месяцу); actuaI_for_is I — признак актуальности значения показателя ( Г соответствует актуальному значению, т.е. не устаревшему); year — год, к которому отнесено значение показателя.
2. Нахождение максимального значения заданного показателя для разных территорий. В форме SQL: select max(value) as ma, id_territory from value where id_ind=X and spacing=2 and actual_for_isl=/ V group by id_territory Колонка value, использованная в запросе, содержит значение показателя.
3. Извлечение среза показателя по измерению «Территория» для заданного интервала времени и заданного территориального уровня.
