Метод приближенной обработки запросов в системах оперативного анализа данных тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Ухаров, Андрей Олегович

• Ухаров, Андрей Олегович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Ухаров, Андрей Олегович

ВВЕДЕНИЕ.

ГЛАВА 1. Критический анализ существующих методов приближенной обработки запросов в OLAP-системах.

1.1. Системы оперативного анализа данных.

1.2. Концепция приближенной обработки запросов.

1.3. Критический анализ методов выборки.

1.3.1. Однородная случайная выборка (Uniform Random Sampling).

1.3.2. Смещенные выборки (Non-Uniform Biased Sampling).

1.3.3. Прогрессивная выборка (Online Aggregation Sampling).

1.3.4. Динамически используемые смещенные выборки.

1.3.5. Недостатки, присущие методам приближенной обработки запросов на основе выборки.

1.4. Критический анализ методов гистограмм.

1.4.1. Гистограммы равной ширины и глубины. Гистограммы со смещением.

1.4.2. Гистограммы с контролем ошибок.

1.4.3. Многомерные гистограммы.

1.4.4. Гистограммы на основе отношений.

1.4.5. Недостатки, присущие методам приближенной обработки запросов на основе гистограмм.

1.5. Критический анализ методов вейвлет-преобразования.

1.5.1. Вычисление интервальных запросов на основе вейвлет-декомпозиции.

1.5.2. Приближенная обработка произвольных запросов на основе вейвлет-представления Чакрабарти.

1.5.3. Приближенная обработка запросов на основе вероятностного сжатия вейвлет-декомпозиции.

1.6. Постановка задачи.

1.7. Выводы.

ГЛАВА 2. Методы дискретного нестандартного вейвлет-преобразования Хаара для произвольной длины измерения исходного массива данных с возможностью обновления декомпозиции, оценки распределения погрешности восстановления исходных элементов.

2.1. Дискретное нестандартное вейвлет-преобразование Хаара (ДНВПХ) многомерного набора данных.

2.2. Прямая и обратная вей влет-декомпозиция дискретного набора данных» с произвольной длиной измерения.

2.2.1. ДНВПХ Чакрабарти (СЬакгаЬагф.

2.2.2. ДНВПХ с произвольной длиной измерения и уменьшенным количеством операций чтения/записи.

2.2.3. Восстановление исходного элемента данных с помощью обратного ДНВПХ с произвольной длиной измерения.

2.2.4. Восстановление суммы исходных элементов данных с помощью обратного ДНВПХ с произвольной длиной измерения.

2.3. Обновление вейвлет-декомпозиции дискретного набора данных.

2.4. Оценка распределения погрешности восстановления исходного элемента данных и суммы элементов при сжатии вейвлет-декомпозиции.

2.4.1. Оценка распределения погрешности восстановления исходного элемента данных.

2.4.2. Оценка распределения погрешности восстановления суммы исходных элементов данных.

2.4.3. Расчет распределения погрешности при сжатии и обновлении вейвлет-декомпозиции.

2.5. Выводы.

ГЛАВА 3. Разработка инструментального средства приближенной обработки запросов на основе ДНВПХ с произвольной длиной измерения.

3.1. Обоснование создания ИС.

3.2. Концептуальное описание системы.

3.2.1. Функциональное описание системы.

3.2.2. Структурное описание системы.

3.2.3. Описание архитектуры системы.

3.3. Проектирование базы данных.

3.4. Проектирование прикладной части ПО.

3.5. Выводы.

ГЛАВА 4. Использование разработанного средства для создания компонента OLAP-модуля системы "Надзор за заболеваемостью".

4.1. Описание предметной области.

4.2. Реализация подсистемы приближенной обработки запросов.

4.2.1. Комплекс технических средств и топология.

4.2.2. Комплекс программных средств.

4.2.3. Многомерные кубы.

4.3. Анализ результатов использования подсистемы приближенной обработки запросов.

4.4. Выводы.

ВЫВОДЫ.

Введение диссертации (часть автореферата) на тему «Метод приближенной обработки запросов в системах оперативного анализа данных»

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

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

В настоящее время распространены три основных подхода к приближенной обработке запросов: методы выборки, методы гистограмм и методы вейвлет-преобразования. Однако существующие подходы обладают рядом недостатков, что сдерживает их применение на практике. Методы выборки и гистограмм ориентированы на получение агрегатных значений с большим количеством элементов. Вычисление же единичных значений или сумм с небольшим числом слагаемых сопровождается значительной погрешностью. Более того с ростом размерности данных (а в современных ОЬАР-системах по оценкам аналитиков количество измерений в кубах достигает 10-15) увеличивается стоимость построения и хранения приближенного представления, обеспечивающего приемлемую погрешность. В этой связи наиболее перспективным представляется подход на основе вейвлет-преобразования, позволяющий вычислять как единичные, так и суммарные значения на основе многомерных данных. Однако существующие методы накладывают ряд ограничений на структуру данных, не позволяют производить обновление значений без полного пересчета всего набора и не предоставляют точных методов оценки погрешностей.

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

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

В работе решаются следующие задачи:

1. Разработка метода вейвлет-преобразования Хаара г-мерного набора данных с произвольной длиной измерений.

2. Разработка метода восстановления исходного элемента и суммы элементов из сжатого хранилища данных с произвольной длиной измерения.

3. Разработка метода обновления сжатого хранилища данных без полного пересчета вейвлет-коэффициентов.

4. Разработка метода оценки погрешностей восстановления исходного элемента данных и суммы элементов.

5. Разработка инструментального средства приближенной обработки запросов.

6. Разработка ОЬАР-системы «Надзор за заболеваемостью» и анализ результатов использования предложенных методов.

Объект исследования. Объектом исследования настоящей работы являются системы оперативного анализа данных (ОЬАР-системы).

Предмет исследования. Предметом исследования являются процессы приближенной обработки запросов на основе вейвлет-преобразования в системах оперативного анализа данных.

Научная новизна. В работе получены следующие новые научные результаты:

1. Разработан метод нестандартного вейвлет-преобразования Хаара, учитывающий произвольную длину измерений, отличную от 2П, и позволяющий уменьшить объем хранимых вейвлет-коэффициентов до объема исходных значений. Доказана лемма о замещении усредненных вейвлет-коэффициентов на разных уровнях детализации вейвлет-преобразования, что позволило сократить количество операций чтения/записи.

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

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

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

Методы исследования. Исследования проводились на основе комплексного использования теории вейвлетов, теории вероятности, теории алгоритмов.

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

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

Публикации по теме. По материалам настоящей работы опубликовано 6 печатных работ, из них 4 — в научных журналах, рекомендуемых ВАК.

Апробация работы. Материалы работы были изложены автором на семинарах кафедры ИУ-5 МГТУ им. Н.Э. Баумана в 2008 и 2009 годах.

Структура диссертационной работы. В первой главе «Критический анализ существующих методов приближенной обработки запросов в ОЬАР-системах» приведено описание концепции приближенной обработки запросов, рассмотрены основные особенности таких систем. Приведен критический анализ существующих подходов на основе методов выборки, гистограмм и вейвлет-преобразования.

Во второй главе "Методы дискретного нестандартного вейвлет-преобразования Хаара для произвольной длины измерения исходного массива данных с возможностью обновления декомпозиции, оценки распределения погрешности восстановления исходных элементов" предложен новый метод получения приближенного представления данных с измерениями произвольной длины. Разработаны алгоритмы вычисления исходного элемента и суммы элементов из такого представления, предложен метод оценки погрешности восстановления элементов. Разработан новый метод обновления приближенного представления без полного пересчета значений.

В третьей главе "Разработка инструментального средства приближенной обработки запросов на основе ДНВПХ с произвольной длиной измерения" разработан проект ИС приближенной обработки запросов на основе методологии объектно-ориентированного анализа и проектирования. Приводится концептуальное, функциональное и структурное описание системы, описание архитектуры ИС, а также формализованное описание схемы БД.

В четвертой главе "Использование разработанного средства для создания компонента ОЬАР-модуля системы "Надзор за заболеваемостью" приведено описание реализации разработанного средства, которое является частью аналитического модуля системы "Надзор за заболеваемостью". Исследованы результаты применения разработанного средства для приближенной обработки запросов.

Заключение диссертации по теме «Теоретические основы информатики», Ухаров, Андрей Олегович

ВЫВОДЫ

В качестве основных результатов работы определены следующие положения:

1. Разработан метод получения приближенных представлений данных на основе вейвлет-преобразования Хаара, позволяющий обрабатывать массивы с произвольными длинами измерений и сокращающий число операций чтения/записи.

II

2. Разработан метод восстановления исходного элемента и суммы I, элементов хранилища данных на основе приближенного вейвлет-1 представления с произвольной длиной измерения, учитывающий | взаимную компенсацию коэффициентов и позволяющий вычислять 1 несохраненные вейвлет-коэффициенты.

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

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

5. Разработано инструментальное средство, реализующее предложенные 1 методы приближенной обработки запросов на основе вейвлет преобразования, которое является частью аналитического модуля системы "Надзор за заболеваемостью".

6. Исследованы результаты использования разработанного инструментального средства и предложенных методов оценки погрешностей. Сжатие данных на 60% уменьшает время выполнения запросов в среднем на 50% при погрешности восстановления исходного элемента и суммы элементов хранилища данных, равной 15% и 5% соответственно.

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

Список литературы диссертационного исследования кандидат технических наук Ухаров, Андрей Олегович, 2011 год

1. Арлоу Д., Нейштадт A. UML 2 и Унифицированный процесс. Практический объектно-ориентированный анализ и проектирование. Второе издание: Пер. с англ.- СПб.: Символ-плюс, 2007,- 624 с.

2. Архипенков С. Я., Голубев Д.В., Максименко О. Б. Хранилища данных.-М.: Диалог-МИФИ, 2002.- 528 с.

3. Асеев М.Г., Баллюзек М.Ф., Дюк В.А. Разработка медицинских экспертных систем средствами технологий Data Mining // Datadiver. 2008. URL.http://www.datadiver.nw.ru (дата обращения 02.08.2008)

4. Боровков А. А. Теория вероятностей: Учеб. пособие для вузов.— 2-е изд., перераб. и доп.— М.: Наука. Гл. ред. физ.-мат. лит., 1986.- 432 с.

5. Буч Г., Рамбо Д., Якобсон И. Язык UML. Руководство пользователя: Пер. с англ.-М.: ДМК пресс, 2007.- 496 с.

6. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем // Citforum.ru. 2008. URL.http://www.citforum.ru/database/case/index.shtml (дата обращения 14.07.08)

7. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. СПб.: Изд-во ВУС, 1999. - 208 с.

8. Гашков С.Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений. -М.: Дрофа, 2005. -320 с.

9. Гмурман В.Е. Теория вероятностей и математическая статистика. Изд. 4-е. Учеб. пособие для вузов.- М.: Высшая школа, 1972.- 368 с.

10. Гнеденко Б.В. Курс теории вероятностей: Учебник- Изд. 6-е, перераб. и доп.- М.: Наука, гл. ред. физ.-мат. лит., 1988.- 448 с.

11. Гордиенко И. OLAP. Часть II. Разведка на местности // Компьютера (М.).- 2002.- №9.- С. 53-59.

12. Григорьев Ю.А., Ухаров А.О. Вейвлет-сжатие в хранилищах данных OLAP // Информатика и системы управления (Благовещенск). 2008. -№4. - С.3-10.

13. Григорьев Ю.А., Ухаров А.О. Возможности приближенной аналитической обработки многомерных данных на основе вейвлет-преобразования // Проблемы полиграфии и издательского дела (М.). -2007. №1. - С.60-68.

14. Григорьев Ю.А., Ухаров А.О. Обзор концепции многомерной модели данных в технологии OLAP // Проблемы построения: и эксплуатации систем обработки информации и управления (М.). — 2006. №4. - С. 1530.

15. Григорьев Ю.А., Ухаров А.О. Распределение ошибки при вейвлет-сжатии в хранилищах данных OLAP // Информатика и системы управления (Благовещенск). 2008. - №3. - С.3-14.

16. Григорьев Ю.А., Ухаров А.О., Плутенко А.Д. Использование вейвлет-преобразования для приближенной аналитической обработки многомерных данных // Информатика и системы управления (Благовещенск). 2008. -№1. - С.3-11.

17. Добеши И. Десять лекций по вейвлетам: Пер. с англ.- Ижевск: НИЦ Регулярная и хаотическая динамика, 2001. 464 с.

18. Дьяконов В. Вейвлеты. От теории к практике.- М.: СОЛОН Р, 2004.400 с.

19. Заботнев М.С. Методы представления информации в разреженных гиперкубах данных // OLAP.ru. 2008. URL.http://www.olap.ru/basic/theory.asp (дата обращения 19.01.08)

20. Инмон У. Типы Хранилищ данных // ISO.ru. 2001. URL. http://www.iso.ru/journal/articles/181.html (дата обращения 01.08.2007)

21. Истомина Т.В.,Чувыкин Б.В., Щеголев В.Е. Применение теории wavelets в задачах обработки информации: Монография. — Пенза: Изд-во Пенз. гос. ун-та, 2000. 188 с.

22. Ким. В. Три основных недостатка современных хранилищ данных // Открытые системы (М.).- 2003.- №2.- С.46-52.

23. Киммел П. UML. Универсальный язык программирования: Пер. с анг. -М.: НТ-Пресс, 2008.- 272 с.

24. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах // Открытые системы (М.).- 1997.- № 4.- С. 41-44.

25. Кнут Д. Искусство программирования, том 1. Основные алгоритмы: Пер. с анг. 3-е изд.- М.: Вильяме, 2006. - 720 с.

26. Кобринский Б.А. Ретроспективный анализ медицинских экспертных систем // Новости искусственного интеллекта (М.).- 2005.- №2,- С. 6-17.

27. Кудрявцев Ю. Обзор алгоритмов MOLAP // Citforum.ru. 2007. URL. http://www.citforum.ru/consulting/Bl/molapoverview (дата обращения 03.12.07)

28. Кузнецов С. Крупные проблемы и текущие задачи исследований в области баз данных // Citforum.ru. 2007. URL. http://www.citforum.ru/database/articles/problems (дата обращения 17.09.2007)31.

29. Леоненков A.B. Объектно-ориентированный анализ и проектирование с использованием UML и IBM Rational Rose. -M.: Бином, 2006.- 320 с.

30. Леоненков A.B. Самоучитель UML2.-OT6.: БХВ-Петербург, 2007.-576 с.33* Леоненков A.B. Самоучитель UML.-СПб.: БХВ-Петербург, 2002.-304 с. 34. Малла С. Вэйвлеты в обработке сигналов.-М.: Мир, 2005.-672 с.

31. Мартиросян С. OLAP-системы: обзор лидеров рынка // Gnews.ru. 2006. URL. http://cnews.ru/reviews/index.shtml72006/07/20/2063102 (Дата обращения 2.02.2007)

32. Математическая статистика: учеб: для вузов/ В.Б. Горяинов и др.; Под ред. B.C. Зарубина, А.П. Крищенко.- 2-е изд.- М.: Изд-во МГТУ им. Н.Э. Баумана; 2002.- 424 с.

33. Мацяшек JI.Ä. Анализ и проектирование информационных систем с помощью UML 2.0: Пер. с англ.- М.: Изд. Дом Вильяме, 2008. 816 с.

34. Методология IDEFlx. Стандарт. Русская версия.- М.: Метатехнология, 1993.- 108 с.

35. Некипелов Н., Арустамов А. Методика анализа данных // Basegroup. 2008. URL. http://www.basegroup.ru/library/methodology/base/ (дата обращения 02:08.2008)

36. Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. М.: МГУ, 1992. - 140 с.

37. Объектно-ориентированный анализ и проектирование с примерами приложений/Г. Буч и др.: Пер. с англ.- М.: Вильяме, 2008,- 720 с.

38. Овчинников В. Г. Методология проектирования автоматизированных информационных систем. Основы системного подхода. М.: Компания Спутник +, 2005.- 286 с.

39. Петухов А.П. Введение в теорию базисов всплесков. СПб.: Изд-во СПбГТУ, 1999. - 132 с.

40. Сахаров А. А. Концепция построения и реализации информационных систем, ориентированных на анализ данных // СУБД (М.).- 1996. № 4.-С. 55-70.

41. Сахаров А. А. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server) // СУБД (М.).- 1996.- № 3. С. 44-59.

42. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB.-M.:1. ДМК пресс, 2005.- 304 с.

43. Спирли Э. Корпоративные хранилища данных. Планирование, разработка, реализация: Пер. с англ.- М.: Изд. дом Вильяме, 2001. —Том 1.- 400 с.

44. Стивене P. Visual Basic. Готовые алгоритмы: Пер. с анг.- М.: ДМК, 2000.- 377 с.

45. Столниц Э., Дероуз Т., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения: Пер. с англ.- Ижевск: НИЦ Регулярная и хаотическая динамика, 2002. 272 с.

46. Стулов А. Особенности построения информационных хранилищ //OSP.ru: Открытые системы. 2007. URL. http://www.osp.ai/os/2003/04/182942/ (дата обращения 23.05.2007)

47. Управление научными данными в следующем десятилетии/ Д. Грэй и др. // ACM SIGMOD Record.- 2005.- Vol. 34(4).- P. 34-41.

48. Ухаров А.О. Использование вейвлет-преобразования для представления многомерных данных в системах OLAP // Интеллектуальные технологии и системы (М.). 2005. - №7. - С.256-271.

49. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии: Пер. с англ.- М.: Триумф, 2003. 320 с.

50. Фалевич Б.Я. Теория алгоритмов. -М.: Машиностроение, 2004. 160 с.

51. Фаулер М., Скотт К. UML. Основы: Пер. с англ.- СПб.: Символ-Плюс, 2002. 192 с.

52. Федоров А., Елманова Н. Введение в OLAP // КомпьютерПресс (М.).-2000.-№3.- С. 37-42.

53. Фрост Р., Дей Д, Слайк К.В. Базы данных. Проектирование и разработка.- M.: HT Пресс, 2007.- 592 с.

54. Чуи Ч. Введение в вейвлеты: llep. с анг.-М.: Мир, 2001 г. 412 с.

55. Шапот М. Интеллектуальный анализ данных; в системах поддержки принятия решений // Открытые системы (М.).- 19981- №1,- С. 30-35.

56. Шроэк М. Зинн Д. Интегрированная аналитика. Как извлечь максимальную выгоду из ERP-систем // Gitforum.ru. 2007. URL. http://www.citforum.ru/database/articles/erp-system (дата обращения 17.09.2007)

57. Шуленин А. Масштабируемость аналитических сиситем // Windows IT Pro (М.).- 2002. № 1. - С. 15-22.

58. Щавелёв JI.B. Оперативная аналитическая обработка данных: концепции и технологии// Citforum.ru. 1999. URL. http://www.citforum.ru/seminars/cis99/sch.shtml (дата обращения 09.04.2007)

59. A Taxonomy of Dirty Data / W. Kim and other. // Data Mining and Knowledge Discovery (Hingham).- 2003.- Vol. 7(1).- P. 81-99.

60. Aboulnaga A., Chaudhuri S. Self-tuning Histograms: Building Histograms Without Looking at Data // Proceedings of the 1999 ACM SIGMOD international conference on Management of data;- New York, 1999.- P. 181192.

61. Acharya S., Gibbons P. В., Poosala V. Congressional Samples for Approximate Answering of Group-By Queries // ACM SIGMOD Record.- 2000.- Vol. 29(2).- P. 487-498.

62. Acharya S., Gibbons P. В., Poosala V. Join Synopses for Approximate Query Answering//ACM SIGMOD Record.- 1999.- Vol. 28(2).- P. 275-286.

63. Aftari F.N., Lekeas P.V., Li С. Answering Aggregation Queries on Hierarchical Web Sites Using Adaptive Sampling // Proceedings of the 14th ACM international conference on Information and knowledge management.- New York, 2005.- P. 237-238.

64. Babcock В., Chaudhuri S. Das G. Dynamic sample selection for approximate query processing // Proceedings of the 2003 ACM SIGMOD international conference on Management of data.- New York, 2003.- P. 539-550.

65. Bruno N., Chaudhuri S., Gravano L. STHoles: A Multidimensional Workload-Aware Histogram // Proceedings of the 2001 ACM SIGMOD international conference on Management of data.- New York, 2001.- P. 211222.

66. Chakrabarti K., Garofalakis M., Rastogi R. Approximate query processing using wavelets // The VLDB Journal — The International Journal on Very Large Data Bases.- 2001.- Vol. 10(2).- P. 199-223.

67. Chaudhuri S., Das G., Datar M. Overcoming Limitations of Sampling for Aggregation Queries // Proceedings of the 17th International Conference on Data Engineering.- Washington, 2001.- P. 534-542.

68. Chaudhuri S., Das G., Narasayya V. Optimized Stratified Sampling for Approximate Query Processing // ACM Transactions on Database Systems (TODS).- 2007.- Vol. 32(2).- P. 17-25.

69. Codd E. F., Codd S. В., Salley С. T. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate // Informatik. 2006. URL. Http://www.informatik.uni-jena.de (дата обращения 17.10.2006)

70. Das G. Sampling Methods in Approximate Query Answering Systems // Uta.edu. 2008. URL. http://ranger.uta.edu/~gdas/website-pages/preprints-papers/data-warehouse.pdf (дата обращения 17.04.2008)

71. Data Warehouse Design Solutions / C. Adamson and other.- Hoboken: Wiley, 1998.- 523 p.

72. ERWin'Methods Guide / bogie Works Inc.- Princeton, 1997. 105 p.

73. Fast; Small-Space Algorithms for Approximate Histogram Maintenance / A. Gilbert and. other. // Proceedings of the thiry-fourth annual ACM symposium on Theory of computing.- Motreal, 2002.- P. 389-398.

74. Foote К. E., Huebner D. J. Error, Accuracy, and Precision // Colorado.edu. 2000: URL. http://www.colorado.edu/geography/gcraft/notes/error/error.html (дата обращения 02.08.2008)

75. Forsman S. OLAP Council White Paper // OLAPCouncilicom. 2007. URL. http://www.olapcouncil.org/research/whtpaply.htm (дата обращения 21.2.2007)

76. Franklin M., Halevy A., Maier D. From Databases to Dataspaces: A New Abstraction for Information Management // SIGMOD Record.- 2005.- Vol. 34(4).- P. 27-33.

77. Fryzlewicz P. Unbalanced Haar technique for nonparametric function estimation // wavelet.org. 2007. URL. http://www. wavelet. org/phpBB2/viewtopic.php?t=l06565 (дата обращения 17.09.2007)

78. Garofalakis M. Wavelet-Based Approximation Techniques in Database Systems // IEEE Signal Processing Magazine.- 2006.- VoL 23(6).-P. 54-58.

79. Garofalakis M., Gibbons P.B. Probabilistic Wavelet Synopses // ACM Transactions on Database Systems (TODS).- 2004.- Vol. 29(1).- P. 43-90.

80. Garofalakis M., Gibbons P.B. Wavelet Synopses with Error Guarantees // Intel-Research. 2007. URL. http://www.pittsburgh.mtel-research.net/people/gibbons/papers/wavelets-sigmod02.pdf (дата обращения 17.04.07)

81. Garofalakis M., Kumar A. Deterministic Wavelet Thresholding for Maximum Error Metrics // Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.- New York, 2004.-P. 166-176.

82. Gibbons P. B. Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports // Proceedings of the 27th International Conference on Very Large Data Bases.- San Francisco, 2001.- P. 541-550.

83. Gibbons P., Matias Y., Poosala V. Fast Incremental Maintenance of Approximate Histograms // ACM Transactions on Database Systems (TODS).- 2002.- Vol. 27(3).- P. 261-298.

84. Gibbons P.B., Matias Y. New Sampling-Based Summary Statistics for Improving Approximate Query Answers // Proceedings of the 1998 ACM SIGMOD international conference on Management of data.- New York, 1998.- P. 331-342.

85. Gunopulos D., Kollios G., Tsotras V. Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes // ACM SIGMOD Record.- 2000.- Vol. 29(2).- P. 463-474.

86. Haas P.J. Large-Sample and Deterministic Confidence Intervals for OnlineAggregation // Proceedings of the Ninth International Conference on Scientific and Statistical Database Management.- Washington, 1997.-P. 51-63.

87. Helberg С. Pitfalls of Data Analysis // Execpc.com. 2008. URL. http://www.My.execpc.com /-helberg/ (дата обращения 02.08.2008)

88. Hellerstein J. M., Haas P.J., Wang HJ. Online Aggregation // Proceedings of the 1997 ACM SIGMOD international conference on Management of data.-New York, 1997.-P. 171-182.

89. Holt J. UML (Unified Modelling Language) for Systems Engineering.-Stevenage: Institution of Engineering and Technology, 2001.- 296 c.

90. Inmon W.H. Building the Data Warehouse. Fourth Edition.- Hoboken: Wiley, 2005.- 543 p.

91. Ioannidis Y. The History of Histograms // Proceedings of the 29th international conference on Very large data bases.- Berlin, 2003.- Vol. 27 (l).-P. 19-30.

92. Ioannidis Y., Christodoulakis S. On the propagation of errors in the size of join results // Proceedings of the 1991 ACM SIGMOD international conference on Management of data.- New York, 1991.- P. 268-277.

93. Ioannidis Y., Poosala V.: Balancing Histogram Optimality and Practicality for Query Result Size Estimation // Proceedings of the 1995 ACM SIGMOD international conference on Management of data.- New York, 1995.- P. 233244.

94. Jagadish H. V., Jin H., Ooi B. C., Tan K.-L. Global Optimization of Histograms // Proceedings of the 2001 ACM SIGMOD international conference on Management of data.- Santa Barbara, 2001.- P. 223-234.

95. Kimball R. A Dimensional modeling // DBMS Magazine. 2007. URL.http://www.dbmsmag.com (дата обращения 08.03.2007)

96. Kimball R. Help for Hierarchies // DBMS Magazine. 2007.

97. URL.http://www.dbmsmag.com (дата обращения 08.03.2007)

98. Kimball R., Ross M. The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling. Second Edition.- Hoboken: Wiley, 2002.- 464 p.

99. Koudas N., Muthukrishnan S., Srivastava D. Optimal Histograms for Hierarchical Range Queries // Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.- Dallas, 2000.-P. 196-204.

100. Lee J.-H., Kim D.-H., Chung C.-W. Multi-Dimensional Selectivity Estimation Using Compressed Histogram Information // ACM SIGMOD Record.- 1999.- P. 205-214.

101. Lemire D. Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes // Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research.- Toronto, 2002.- P. 6-7.

102. Luo J., Zhou J., Zhang Y. Selectivity Estimation by Batch-Query based Histogram and Parametric Method // Proceedings of the eighteenth conference on Australasian database.- Durlinghurst, 2007.- Vol. 63.- P. 93102.

103. Lynch J. F. Analysis and Application of Adaptive Sampling // Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.- New York, 2000.- P. 260-267.

104. Matias Y., Vitter J.S., Wang M. Wavelet-Based Histograms for Selectivity Estimation // The IBM Research.com. 2007. URL. http://www.research.ibm.com/people/rn/minwang/publications/sigmod98.pdf (дата обращения 21.11.07)

105. MDX Description // Microsoft Developer Network. 2007. URL. http://msdn.microsoft.com/en-us/library/aa216767(SQL.80).aspx (дата обращения 13.06.2007)

106. Muralikrishna M., DeWitt D. Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries // ACM SIGMOD.1998.-Vol. 1(1).-P. 28-36.

107. Nailen R. Does precision imply accuracy? // BNet.com. 2008. URL. http://www.findarticles.eom/p/articles/miqa3726/is200105 (дата обращения 02.08.2008)

108. Optimal Histograms with Quality Guarantees / H. V. Jagadish and other. // Proceedings of the 24rd International Conference on Very Large Data Bases.- San Francisco, 1998.- P. 275-286.

109. Pendse N. Database Explosion // Olap Report. 2006. URL. http://olapreport.com (дата обращения 11.11.2005)

110. Pendse N. Multidimensional Data Structures // Olap Report. 2006. URL. http://olapreport.com (дата обращения 19.03.2006)

111. Pendse N. The OLPA Survey 5 // Olap Report. 2006. URL. http://olapreport.com (дата обращения 15.11.2005)

112. Poosala V., Ganti V., Ioannidis Y. Approximate Query Answering using Histograms // Journal of Intelligent Information Systems.- 2002.- Vol. 19(2).-P. 145-167.

113. Poosala V., Ioannidis Y. Histogram-Based Approximation of Set-Valued Query Answers // Proceedings of the 25th International Conference on Very Large Data Bases.- San Francisco, 1999.-P. 174-185.

114. Poosala V., Ioannidis Y. Selectivity Estimation Without the Attribute Value Independence Assumption // Proceedings of the 23rd International Conference on Very Large Data Bases.- San Francisco, 1997.- P. 486-495.

115. Poosala V., Ioannidis Y., Haas P. Improved Histograms for Selectivity Estimation of Range Predicates // ACM SIGMOD Record.- 1996.- Vol. 25(2).- P. 294-305.

116. Potgieter. J. OLAP Data Scalability // Information-management.com. 2006. URL. http://www.information-management.com/infodirect/20031031/763 6-l.html (дата обращения 10.12.2006)

117. Prasad Y. Z., Deshpande M., Naughton J.F., Shukla A. Simultaneous Optimization and Evaluation of Multiple Dimensional Queries // ACM SIGMOD Record.- 1998.- Vol. 27(2).- P. 271-282.

118. Raghuveer M. Rao, Ajit S. Bopardikar. Wavelet Transforms: Introduction to Theory & Applications.-Boston:Prentice Hall PTR, 1998. 310 p.

119. Redbook. Data Modeling Techniques for Data Warehousing // IBM.com. 2008. URL. http://www.redbooks.ibm.com (дата обращения 12.02.2008)

120. Runapongsa К., Nadeau T.P., Teorey T.J. Storage estimation for Multidimensional aggregates in OLAP // Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research.- Mississauga, 1999.- P.10-11.

121. Sarawagi S. Indexing Olap Data // Bulletin of the IEEE Computer Society Technical Committee on Data Engineering.- Los Alamitos, 1996.- P. 1-9.

122. Sherman R. Data Integration Advisor: The Enterprise Data Warehouse Strikes Again. Part 1 // DM Review. 2006. URL.http://www.athena-solutions.com/library-dmreview.shtml (дата обращения 11.05.2006)

123. Soni S., Kurtz. W. Analysis Services: Optimizing Cube Performance Using Microsoft SQL Server 2000 Analysis Services // Unisys. 2006. URL http://www.unisys.com (дата обращения 03.01. 2006)

124. Thomsen E. OLAP Solutions: Building Multidimensional Information Systems. Second Edition.- Hoboken: Wiley, 2005,- 728 p.

125. Vitter J. F., Wang M., Iyer B. Data Cube Approximation and Histograms via Wavelets // Proceedings of the seventh international conference on Information and knowledge management-Bethesda, 1998.- P. 96-104.

126. Vitter J.S., Wang M. Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets // Proceedings of the 1999 ACM SIGMOD international conference on Management of data.- New York, 1999:- P. 193-204.

127. Vonesch C., Unser M. A Fast Thresholded Landweber Algorithm for Wavelet-Regularized Multidimensional Deconvolution // IEEE Transactions on Image Processing.- 2008.- Vol. 17 ( 4).-P. 539-549

128. Wang H., Sevcik K.C. A multidimensional histogram for selectivity estimation and fast approximate query answering // Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research.-Toronto, 2003.- 328-342.

129. Whitehorn M, Zare R., Pasumansky M. Fast Track to MDX.-Berlin: Springer, 2004.- 266 p.

130. Wu Y.L., Amr El Abbadi D.A. Using Wavelet Decomposition to Support Progressive and Approximate Range-Sum Queries over Data Cubes // Proceedings of the ninth international conference on Information and knowledge management.- MCLean, 2000.- P. 414-421.

131. Yen J., Zhong N., Pal S.K. Wavelet Analysis And Its Applications, And Active Media Technology // Proceedings Of The International Computer Congress 2004.- Beijing: Logistical Engineering University, 2004.-Vol.2.- P. 713-729.