Исследование и разработка статистических методов группирования запросов в сложной информационной системе тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Полухин, Константин Васильевич

• Полухин, Константин Васильевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Полухин, Константин Васильевич

ВВЕДЕНИЕ.

1. АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ ОПТИМИЗАЦИИ ЗАПРОСОВ СУБД.

1.1. Локальная оптимизация запросов СУБД.

1.2. Эффективные алгоритмы выполнения запросов.

1.3. Глобальная оптимизация потока запросов.

1.4. Выводы.

2. МЕТОДЫ ГРУППИРОВАНИЯ ДАННЫХ В ЗАДАЧЕ АНАЛИЗА ПОТОКОВ ЗАПРОСОВ.

2.1. Методы визуализации данных.

2.2. Методы автоматического группирования данных.

2.3. Алгоритмы поиска if-then правил в данных.

2.4. Анализ ассоциативных правил.

2.5. Предлагаемые новации.

2.6. Выводы.

3. ИНСТРУМЕНТЫ ИССЛЕДОВАНИЯ ТЕКСТОВ В ЗАДАЧЕ АНАЛИЗА ПОТОКОВ ЗАПРОСОВ.

3.1. Возможности Text Mining на примере системы

Oracle ConText Option.

3.2. Системы семантического анализа текстов.

3.3. Система для семантического анализа текстов TextAnalyst

3.4. Выводы.

4. НОВЫЕ ТЕОРЕТИЧЕСКИЕ РЕШЕНИЯ И ПРАКТИЧЕСКИЕ АЛГОРИТМЫ И ПРОГРАММЫ АНАЛИЗА ПОТОКА ЗАПРОСОВ. 102 4.1. Программные средства для получения и преобразования исходной информации

-34.2. Поиск ассоциативных связей элементов "сырых" запросов в контексте времени их выполнения.

4.3. Бесконтекстный поиск ассоциативных связей в характеристиках запросов.

4.4. Результаты кластерного анализа потока запросов.

4.5. Результаты применения программы TextAnalyst в задаче локализации семантически сходных запросов.

4.6. Выводы.

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

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

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

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

В связи с оптимизацией запросов существует достаточное количество проблем: проблемы преобразований запроса к более эффективному непроцедурному представлению (логическая оптимизация), проблемы выбора набора альтернативных процедурных планов выполнения запроса, проблемы оценок стоимости выполнения запроса по выбранному плану и др. Для решения каждого класса проблем существует более одного подхода. Например, проблемы, связанные с логической оптимизацией запросов, породили направление, называемое семантической оптимизацией [1-6]. Очень многие исследователи заняты проблемами оценок стоимости процедурных планов выполнения запросов [7-23], хотя до сих пор вопрос о достоверности этих оценок до конца не ясен.

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

Особенно много работ в последние годы посвящается оптимизации запросов и выбору эффективных способов выполнения реляционных операций в распределенных реляционных системах управления базами данных [47-53]. Здесь, конечно, существует очень много вариантов и физической организации распределенных баз данных (с поддержкой копий отношений в нескольких узлах сети, с горизонтальным или вертикальным разделением отношений в нескольких узлах, с поддержкой мгновенных снимков базы данных и т.д.), и алгоритмов выполнения реляционных операций при каждой такой организации. Несмотря на то, что реально существуют и функционируют несколько распределенных реляционных СУБД (например, System R и распределенная INGRES), нельзя считать, что уже найдены адекватные решения этих проблем.

Наконец, сравнительно новой, еще недостаточно исследованной, но безусловно очень важной темой является глобальная оптимизация запросов в системах баз данных [54—72]. Под глобальной оптимизацией понимается совместная оптимизация заранее известного набора запросов. Это наиболее актуально в системах логического программирования (и подобных системах, связанных с обработкой правил), реализуемых на основе реляционных баз данных. При таком подходе выполнение логической программы в конечном счете сводится к выполнению большого количества запросов к базе данных, причем, как правило, запросы содержат соединения. Совместная оптимизация этих запросов способна резко уменьшить общее время выполнения.

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

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

Для достижения поставленной цели решаются следующие задачи:

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

2. Исследование и адаптация инструментов анализа текстов для решения задачи определения подобия запросов.

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

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

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

1. Методика преобразования потока запросов в матрицу количественных данных.

2. Подход к интерпретации результатов кластерного анализа потока запросов с помощью логических функций.

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

4. Словарь терминов-предпЪчтений для системы обработки потока запросов информационной системы.

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

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

2. Предложен подход к интерпретации кластеров в потоке запросов посредством логических правил.

3. Разработан метод генерации многомерной случайной выборки с распределениями значений отдельных признаков, идентичными распределениям значений в реальной выборке.

4. Разработан словарь терминов предпочтений для выявления сходных запросов.

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

Реализация. Исследования, отраженные в диссертации, реализованы в виде программные средств "Log-Analyzer", "Cross-Campaign Analyzer", и "Log Transformer", которые предназначены для получения, и преобразования данных для обработки запросов с помощью инструментов статистического анализа. Они внедрены на предприятиях США "Reader's Digest" и "American Express".

Апробация. Результаты работы докладывались и обсуждались на 3 международных и российских конференциях: "CRM for Business-to-Business and Business-to-Concumer" (Boston Prudancial Center, March 2000); "CRM for financial institutions" (June 2003, Toronto, Canada), Юбилейная конференция "20 лет медицинской информатике в СПбМАПО" (март 2006, СПб).

Публикации. Основные результаты диссертации изложены самостоятельно и в соавторстве в 5 публикациях.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы, включающего 152 наименования. Работа изложена на 151 странице, содержит 15 рисунков и 5 таблиц.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Полухин, Константин Васильевич

- 1324.6. Выводы

1. Получение исходного материала для дальнейшего анализа с целью оптимизации информационной системы связано с необходимостью разработки специальных программных средств, встраиваемых в данную информационную систему и учитывающих специфику решаемых системой информационных задач. В данном разделе охарактеризованы специально разработанные программные средства, "заточенные" для работы в альянсе с известной системой "The Affinium Suite" (Ь11р://шшш.ип1сасоф.сот/ргоёис18/тёех.Ь1ш1) компании UNICA (США), предназначенной для проведения полнофункциональных маркетинговых исследований. Это "Log-Analyzer for Affinium Campaign", который предоставляет возможность вычленения деталей работы отдельно взятой маркетинговой кампании в информационной системе, и "Cross-Campaign Analyzer for Affinium Campaign", который позволяет оценивать эффективность использования тех или иных источников данных, группировать по заданным критериям запросы в потоке запросов для определенных периодов времени. Одна из функций модуля Cross-Campaign Analyzer, полезная для нашего исследования, заключается в создании логов запросов с привязанными к ним характеристиками производительности (например, время выполнения запроса и др.) и экспорте заказанной информации в требуемый формат. Кроме того, нами разработана программа "Log Transformer", предназначенная для предварительной подготовки данных перед их дальнейшим анализом с помощью инструментов статистического анализа.

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

Для бесконтекстного варианта в потоке запросов выявлено 10 ассоциаций, покрывающих в совокупности 78 % всех запросов информационной системы в рамках анализируемой маркетинговой кампании. Более детальный анализ найденных ассоциаций позволил выделить в них наиболее информативные элементы, которые дают возможность более четко интерпретировать подгруппы запросов, описываемых той или иной ассоциацией. Например, одна подгруппа запросов характеризуется наличием большой вложенности логических операторов, другой подгруппе свойственно использование арифметических операций и т.д. Такая интерпретация оказалась серьезным подспорьем для специалиста, проводящего работу по глобальной оптимизации информационной системы, давая ему возможность более нацелено исследовать выделяемые подгруппы запросов.

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

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

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

ЗАКЛЮЧЕНИЕ Основные результаты работы

1. Выработаны рекомендации по применению методов многомерного статического анализа для решения задачи группирования потока запросов в информационной системе.

2. Разработаны методика и программные средства "Log-Analyzer for Affinium Campaign", "Cross-Campaign Analyzer for Affinium Campaign", "Log Transformer", предназначенные для получения, преобразования и подготовки данных для дальнейшей обработки запросов с помощью инструментов статистического анализа.

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

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

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

6. Изготовлена демонстрация в форме разбора конкретного случая (Case study) использования адаптированной системы TextAnalyst для решения задачи поиска сходных конструкций запросов.

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

Список литературы диссертационного исследования кандидат технических наук Полухин, Константин Васильевич, 2006 год

1. Chacravarthy U.S., Grant J., Minker J. Semantic Query Optimization: Additional

2. Constraints // Proc. 1st Int. Conf. Expert Database Syst., Charleston, S.C., Apr. 1986. New York, 1986.- C. 259-270

3. Chakravarthy U.S., Fishman D.H., Minker J. Semantic Query Optimization in

4. Expert Systems and Database Systems // Expert Database Syst.: Proc. 1st Int. Workshop, Menlo Park, Calif., Feb. 1986. New York, 1986.- C. 326-341

5. Lee S., Han J. Semantic Query Optimization in Recursive Databases 4th Int. Conf.

6. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988.- C. 444-451

7. Shenoy S.T., Ozsoyoglu Z.M. A System for Senantic Query Optimization // Proc.

8. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987.- C. 181-195

9. Sherhar S., Strivastava J., Dutta S. A Formal Model of Trade-off between

10. Optimization and Execution Costs in Semantic Query Optimization // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 457-467

11. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных1. СУБД

12. Christodoulakis S. Estimating Block Selectivities // Inf. Syst.- 1984.- 9, N 1.- C.69.79

13. Christodoulakis S. Estimating Record Selectivities // Inf. Syst.- 1983.- 8, N 2.- C.105.115

14. Christodoulakis S. Implication of Certain Assumtions in Database Performance

15. Evaluation // ACM Trans. Database Syst.- 1984.- 9, N 2.- C. 163-186

16. Demolombe R. Estimation of the Number of Tuples Satisfying a Query Expressed in Preducate Calculus Language // Proc. 6th Int. Conf. Very Large Data Bases, Montreal, Oct. 1980. New York, 1980.- C. 55-63

17. Faloutsos C., Christodoulakis S. Design of a Signature File Method that Accounts for Non-Uniform Occurrance and Query Frequencies // Proc. 11th Int.

18. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.C. 165-170

19. Hagmann R.B. An Observation on Database Buffering Performance Metrics // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 289-293

20. Kiessling W. Access Path Selection in Databases with Intelligent Disc Subsystems // Comput. J.- 1988.- 31, N 1.- C. 41-50

21. Luk W.S. On Estimating Block Accesses in Database Organization // Commun. ACM.- 1983.- 26, N 11.- C. 945-947

22. Lynch C. Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Ca, Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 240-251

23. Piatetski-Shapiro G., Connel C. Accurate Estimation of the Number of Tuples Satisfying a Condition // ACM SIGMOD Record.- 1984.- 19, N 2.- C. 256-276

24. Rowe N.C. Absolute Bounds on Set Intersection and Union Sizes from Distribution Information // IEEE Trans. Software Eng.- 1988.- 14, N 7.- C. 1033-1048

25. Stockmeyer L.H., Wong C.K. On the Number of Comparisons to Find the Intersection of Two Relations // SIAM J. of Comput.- 1979.- 8, N 3.- C. 388-404

26. Stonebraker M., Neuhold E. A Distributed Data Base Version of INGRES // Proc. 2nd Berkley Workshop Distrib. Data Manag. and Comput. Networks, Berkley, Calif., May 1977. Berkley, Calif., 1977. C. 19-36

27. Vander Zanden B.T., Taylor H.M., Bitton D. Estimating Block Accesses When Attributes Are Correlated // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- С. 119-127

28. Whang K., Wiederhold G., Sagalowicz D. Estimating Block Accesses in Database Organizations — A Closed Noniterative Formula // Commun. ACM.-1983.- 26, N 11.-C. 940-944

29. Yao S.B. Approximating Block Acess in Database Organizations // Commun. ACM.- 1977.- 20, N 4.- C. 260-261

30. Zahorjan J., Bell B.J., Sevcik K.C. Estimating Block Transfers When Record Access Probabilities Are Non-Uniform // Inf. Process. Lett.- 1983.- 16, N 5.- C. 249-252

31. Abitboul S., Scholl M., Gardarin G., Simon E. Towards DBMSs for Supporting New Applications // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 423-435.

32. Astrahan M.M., Schkolnick M., Whang K.Y. Counting Unique Values of an Attribute without Sorting // Inf. Syst.1987.- 12, N 1.- С. 11-16.

33. Bell D.A., McErlean F.J., Stewart P.M., Arbuckle W.A. Clustering Related Tuples in Databases // Comput. J.- 1988.31, N 3.- C. 253-257.

34. Bergamaschi S., Scales M.R. Choice of the Optimal Number of Blocks for Data Access by an Index // Inf. Syst.1986.- 11, N 3.- C. 199-209.

35. Bloom B.H. Space/Time Trade-offs in Hash Coding with Allowable Errors // Commun. ACM.- 1970.- 1.3, N 7.- C. 422-426.

36. Cheiney J.-P., Kierman G. A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988.- C. 394-401.

37. Desai B.C., Goyal P., Sardi F. Composite Index in DDBMS // J. of Syst. and Software.- 1988.- 8, N 2.- C. 105-120

38. DeWitt D., Gerber R. Multiprocessor Hash-Based Join Algorithms // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Palo Alto, Calif., 1985.- C. 151-164.

39. Gotlieb L.R. Computing Joins of Relations // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 14-16, 1975. New York, 1975.- C. 55-63.

40. Grazzini E., Pinzani R., Pippolini F. A Physical Structure for Efficient Processing of Relational Queries // Found. Data Organ. Proc. Int. Conf., Kyoto, May 22-24, 1985. New York.

41. Hsu M., Yang W.-P. Concurrent Operations in Extendible Hashing // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 241-247.

42. Jarke M., Koch J. Range Nesting: A Fast Method to Evaluate Quantified Queries // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1983. New York, 1983.- C. 198-206.

43. Kim W. A New Way to Compute the Product and Join of Relations // Proc. ACM SIGMOD Int. Conf. Manag. Data, New Work, May 1980. New York, 1980.-C. 178-187.

44. London, 1987.- C. 501-514.

45. Makinouchi A., Tezuka M., Kitakami H., Adachi S. The Optimization Strategy for Query Evaluation in RDB/V1 // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11,1981. New York, 1981.- C. 518-529.

46. Merrett Т.Н. Why Sort/Merge Gives the Best Implementation of the Natural Join // ACM SIGMOD Record. 1983.- 13, N 2, C. 40-51.

47. Pramanik S., Fotouhi F. Optimizing the Cost of Relational Queries Using Partial Relation Schemes // Inf. Syst.- 1988.- 13, N 1.- C. 71-79.

48. Valduriez P. Join Indeces // ACM Trans. Database Syst.- 1987.- 12, N 2.- C. 218-246.

49. Yu C.T., Jiang T.M. Adaptive Algorithms for Balanced Multidimensional Clustering // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988.- C. 386-391.

50. Bodorik P., Riordon J.S. Distributed Queiy Processing Optimization Objectives // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988.- C. 320-329.

51. Ceri S., Gottlob G. Optimizing Joins Between Two Partitioned Relations in Distributed Databases // J. Parall. and Distrib. Comput.- 1986.- 3, N 2- C. 183205.

52. Chen J.S.J., Li V.O.K. Optimizing Joins in Fragmented Database Systems on a Broadcast Computer Networks // 7th Int. Conf. Distrib. Comput. Syst., Berlin, Sept. 21-25, 1987. Washington, D.C., 1987.- C. 338-345.

53. Cornell D.W., Yu P.S. A Vertical Partitioning Algorithm for Relational Databases // 3rd Int. Conf. Data Eng., Los Angeles, Ca, Febr. 3-5, 1987. Proc. Washington, D.C., 1987.- C. 30-35.

54. Lee M., Freytag J., Lohman G. Implementing an Interpreter for Functional Rules in a Query Optimizers // Proc. 14th Int. Conf. Veiy Large Data Bases, Los

55. Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 218-229

56. Lohman G.M., Daniels D., Haas L.M., Kistler R., Selinger P.G. Optimization of Nested Queries in a Distributed Relational Database // Proc. 10th Int. Conf. Veiy Large Data Bases, Singapore, Aug. 27-31, 1984. New York, 1984.- C. 403-415.

57. Lohman G.M., Mohan C., Haas L.M., Lindsay B.G., Selinger P.G., Wilms P.F., Daniels D. Query Processing in R* // Query Processing in Database Systems. New York: Springer. 1985.- C. 31-47.

58. Chacravarthy U.S., Minker J. Multiple Query Processing in Deductive Databases Using Query Graphs // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 384-394.

59. Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design for Relational Databases // ACM Trans. Database Syst.- 1988.- 13, N 1.- C. 91-128.

60. Jarke M. Common Subexpression Isolation in Multiple Query Optimization // Query Processing in Database Systems. New York: Springer.- 1985.- C. 191205.

61. Kim W. Global Optimization of Relational Queries: A First Step // Query Processing in Database Systems. New York: Springer.- 1985.- C. 206-216.

62. King J.J. QUIST: A System for Semantic Query Optimization in Relational Databases // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981.- C. 510-517

63. London, 1987.- C. 487-500.

64. Lu H., Carey M. Some Experimental Results on Distributed Join Algorithms in a Local Network // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.- C. 425- 432.

65. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Local Queries // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986.- C. 173-180.

66. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Distributed Queries // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 149-159.

67. Miyao J., Tominaga K., Kikuno Т., Yoshida N. Optimization of Multiple Queries in Relational Database Systems // Syst. and Comput. in Japan.- 1988.19, N 4.-C. 56-65.

68. Otoo E.J., Santoro N., Rotem D. Improving Semi-Join Evaluation in Distributed Query Processing // 7th Int. Conf. Distrib. Comput. Syst., Berlin, Sept. 21-25, 1987. Washington, D.C., 1987.- C. 554-561.

69. Park J., Segev A. Using Common Subexpressions to Optimize Multiple Queries // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988.- C. 311-319.

70. Rosental A., Chakravarthy U. Anatomy of a Modular Multiple Query Optimizer // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 230-239.

71. Satoh K., Tsuchida M., Nakamura F., Oomachi K. Local and Global Query Optimization Mechanisms for Relational Databases // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.- C. 405-417.

72. Segev A. Optimization of Join Operations in Horizontally Partitioned Database Systems // ACM Trans. Database Syst.- 1986.- 11, N 1.- C. 48-80.

73. Sellis T. Global Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986.- C. 191-205.

74. Sellis T. Multiple-Query Optimization // ACM Trans. Database Syst.- 1988.13, N 1.- C. 23-52.

75. Whang K.-Y. Index Selection in Relational Databases // Found. Data Organ. Proc. Int. Conf., Kyoto, Japan, May 22-24, 1985. New York.

76. Yu C.T., Gun K.-C., Zhang W., Templeton M., Brill D., Chen A.L.P. Algorithms to Process Distributed Queries in Fast Local Networks // IEEE Trans. Comput.- 1987.- 36, N 10.C. 1153-1164.

77. Дейт К. Введение в системы баз данных.- М.: Наука. 1980.- 463 с.

78. Ульман Д. Основы систем баз данных.- М.: Финансы и статистика.- 1983.335 с.

79. Мейер Д. Теория реляционных баз данных.- М.: Мир. 1987.- 608 с.

80. Date C.J. An Introduction to Database Systems. V.l. 4th ed.- Reading, Mass.: Addison-Wesley.- 1984.- 639 c.

81. Jarke M., Koch J. Query Optimization in Database Systems // ACM Comput. Surv.- 1984.- 16, N2.- C. 111-152.

82. Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held. The Design and Implementation of INGRES. TODS 1 (3), 1976.

83. Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. Access Path Selection in a Relational Database Management System. SIGMOD Conference, 1979.

84. С. Кузнецов. Методы оптимизации выполнения запросов в реляционных СУБД, http://www.citforum.ru/database/articles/ art26.shtml.

85. С. Чаудхари. Методы оптимизации запросов в реляционных системах. // СУБД, № 3, 1998.

86. King J.J. QUIST: A System for Semantic Query Optimization in Relational Databases // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981.-C. 510-517.

87. Smith J.M., Chang P.Y.-T. Optimizing the Performance of a Relational Algebra Database Interface // Commun.- 1975.18, N 10.- C. 568-579.

88. Valduriez P. Join Indeces // ACM Trans. Database Syst.- 1987.- 12, N 2.- C. 218-246.

89. Ullmann J.R. Fast Implementation of Relational Operations Via Inverse Projections // Comput. J.- 1988.-31, N 2.- C. 147-154.

90. Thom J.A., Ramamohanarao K., Naish L. A Superjoin Algorithm for Deductive Databases // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 189-196.

91. Hong, W. and Wong, E. Multiple query optimization through state transition and decomposition. Memorandum, UCB/ERL M89/25, Electrical Research Lab, College of Engineering, University of California, Berkeley, 1989.

92. Wong E., Youssefi K. Decomposition A Strategy for Query Processing // ACM Trans. Database Syst.- 1976. - 1, N 3.C. 223-241.

93. Fa-Chung, Fred Chen, Margaret H. Dunham. Common Subexpression Processing in Multiple-Query Processing. May 1998 IEEE Transactions on Knowledge and Data Engineering, Volume 10 Issue 3.

94. Chakravarthy U., Rosental A. Anatomy of a Modular Multiple Query Optimizer // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 230-239.

95. Chakravarthy U., Rosental A. Anatomy of a Modular Multiple Query Optimizer // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 230-239.

96. Jarke M., Koch J. Query Optimization in Database Systems // ACM Comput. Surv.- 1984.- 16, N 2.- С. 111-152.

97. Hall P.A.V. Optimization of a Single Relational Expression in a Relational Data Base System // IBM J. of Res. and Dev.- 1976.- 20, N 3.- C. 244-257.

98. Finkelstein S. Common Expression Analysis in Database Applications // Proc. ACM SIGMOD Int. Conf. Manag. Data, Orlando, Fl, June 2-4, 1982. New York, 1982.- C. 127-133.

99. Rosenthal A., Reiner D. An Architecture for Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, Orlando, Fl., June 2-4, 1982. New York, 1982.- C. 246-255.

100. Park J., Segev A. Using Common Subexpressions to Optimize Multiple Queries // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988. -C. 311-319.

101. Kyuseok Shim, Timos Sellis, Dana Nau. Improvements on a Heuristic Algorithm for Multiple-Query Optimization.

102. T. Sellis, N. Roussopoulus and C. Faloutsus. The R+-Tree: A Dynamic Index for Multi-dimensional Objects. In Proceedings of the International Conference on Very Large Data Bases (VLDB), 1987 N.

103. Jamal R. Alsabbagh , Vijay V. Raghavan, Analysis of Common Subexpression Exploitation Models in Multiple-Query Processing, Proceedings of the Tenth International Conference on Data Engineering, p.488-497, February 14-18, 1994.

104. R. Karinthi, D. S. Nau, and Q. Yang. Handling feature interactions in process planning. Applied Artificial Intelligence 6(4):389-415, 1992. Special issue on Al for manufacturing.

105. Q. Yang, D. S. Nau, and J. Hendler. Merging separately generated plans with restricted interactions. Tech. Rep. CS-TR-2677, UMIACS-TR-91-73, University of Maryland, 1991.

106. K. Shim, T. Sellis, and D. S. Nau. Improvements on a heuristic algorithm for multiple-query optimization. Data and Knowledge Engineering 12(2): 197—222, 1994.

107. Айвазян C.A., Бежаева З.И., Староверов O.B. Классификация многомерных наблюдений. -М.: Статистика, 1974.

108. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Основы моделирования и первичная обработка данных. — М.: Финансы и статистика, 1983.

109. Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Классификация и снижение размерности. — М.: Статистика, 1989.

110. Налимов В.В. Теория эксперимента. М.: Наука, 1971.

111. Лоули Д., Максвелл А. Факторный анализ как статистический метод. — М.: Мир, 1967.

112. Александров В.В., Алексеев А.И., Горский Н.Д. Анализ данных на ЭВМ (на примере системы СИТО). М.: Финансы и статистика, 1990.

113. Тьюки Дж. Анализ результатов наблюдений. Разведочный анализ. М.: Мир, 1981.

114. Sammon J.W. A nonlinear mapping for Data Structure Analysis//IEEE Trans. Comput. v. С-18, N 5, 1969. - P. 401 -409.

115. Терехина А.Ю. Анализ данных методами многомерного шкалирования. -М.: Наука, 1986.

116. Попечителев Е. П., Романов С.В. Анализ числовых таблиц в биотехнических системах обработки экспериментальных данных. Л.: Наука, 1987.

117. Torgerson W.S. Multidimensional Scaling. Theory and Method // Psychometrika, v. 17, № 4,195.

118. Дэйвисон M. Многомерное шкалирование: Методы наглядногопредставления данных. М.: Финансы и статистика, 1988.

119. Александров В. В., Лачинов В.И., Поляков А.О. Рекурсивная алгоритмизация кривой, заполняющей многомерный интервал // Изв. АН СССР: Техн. кибернетика, 1978, № 1. С. 192-197.

120. Горский Н. Д. Рекурсивный метод отображения многомерного пространства при решении задач хранения и обработки данных в автоматизированных системах научных исследований. Автореф. на соиск. уч. степ. канд. техн. наук. — Л., 1981.

121. Дюк В.А. Компьютерная психодиагностика. СПб: "Братство", 1994.

122. Миркин Б.Г. Анализ качественных признаков и структур. — М.: Статистика, 1980.- 146122. Аркадьев А. Г. Браверманн Э.М. Обучение машины классификации объектов. М.: Наука, 1971.

123. Загоруйко Н.Г., Ёлкина В.Н., Лбов Г.С. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985.

124. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

125. Классификация и кластер // Под ред. Дж. Вэн Райзин. М.: Мир, 1980.

126. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. -Новосибирск: Наука, 1981. 160 с.

127. Лбов Г.С., Котюков В.И., Манохин А.Н. Об одном алгоритме распознавания в пространстве разнотипных признаков. Вычислительные системы, 1973, вып. 55, С. 98-107.

128. Загоруйко Н.Г. К вопросу об определении понятия закономерность. -Вычислительные системы, 1979, вып. 79. С. 3-6.

129. Манохин А.Н. Методы прогнозирования перспективности объектов, основанные на логических решающих функциях. Дисс. на соиск. учен, степ. канд. тех. наук. Новосибирск, Ин-т математики СО АН СССР, 1978. -146 с.

130. Bezdek J.C. Pattern recognition with fuzzy objective function algorithms. New York: Plenum Press, 1981. - 256 p.

131. Quinlan J. R. C4.5: Programs for Machine Learning. San Mateo, CA: Morgan1. Kaufmann, 1993.*

132. Quinlan J. R. Generating production rules from decision trees // In Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87). Morgan Kaufmann, 1987. - P. 304-307.

133. Quinlan J. R. Induction of decision trees // Machine Learning. 1986. - 1. - P. 81-106.

134. Lim, T.-S., Loh, W.-Y., & Shih, Y.-S. (1997). An emprical comparison of decision trees and other classification methods. Technical Report 979, Department of Statistics, University of Winconsin, Madison.

135. Loh, W.-Y, & Shih, Y.-S. (1997). Split selection methods for classification trees. Statistica Sinica, 7, 815-840.

136. Loh, W.-Y., & Vanichestakul, N. (1988). Tree-structured classification via generalized discriminant analysis (with discussion). Journal of the American Statistical Association, 83, 715-728.

137. Doyle, P. (1973). The use of Automatic Interaction Detection and similar search procedures. Operational Research Quarterly, 24, 465-467.

138. Quinlan, J.R., & Cameron-Jones, R.M. (1995). Oversearching and layered search in empirical learning. Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal (Vol. 2). Morgan Kaufman, 1019-10244.

139. Бонгард M.M. Проблема узнавания. -M.: Наука, 1967.

140. R. Agrawal, Т. Imielinski, A. Swami. 1993. Mining Associations between Sets of Items in Massive Databases. In Proc. of the 1993 ACM-SIGMOD Int'l Conf. on Management of Data, 207-216.

141. R. Agrawal, R. Srikant. 'Fast Discovery of Association Rules', In Proc. of the 20th International Conference on VLDB, Santiago, Chile, September 1994.

142. Savasere, E. Omiecinski, und S. Navathe, 'An Efficient Algorithm for Mining Association Rules in Large Databases', In Proc. 21st Int'l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco, 1995.

143. R. Srikant, R. Agrawal. 'Mining Generalized Association Rules', In Proc. of the 21th International Conference on VLDB, Zurich, Switzerland, 1995.

144. R. Srikant, R. Agrawal. 'Mining quantitative association rules in large relational tables'. In Proceedings of the ACM SIGMOD Conference on Management of Data, Montreal, Canada, June 1996.

145. S. Brin et al., 'Dynamic Itemset Counting and Implication Rules for Market Basket Data', In Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York, 1997.

146. Дюк В.А., Эммануэль В.JI. Информационные технологии в медико-биологических исследованиях. СПБ: Питер, 2003. - 525 с.