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

На правах рукописи 0-

ПОЛУХИН Константин Васильевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА СТАТИСТИЧЕСКИХ МЕТОДОВ ГРУППИРОВАНИЯ ЗАПРОСОВ В СЛОЖНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЕ

05.13.01 - системный анализ, управление и обработка информации

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2006

Работа выполнена в Санкт Петербургском институте информатики и автоматизации РАН

Научный руководитель:

доктор технических наук Вячеслав Анатольевич Дюк Официальные оппоненты:

доктор технических наук, профессор Адиль Васильевич Тимофеев доктор технических наук, профессор Владимир Владимирович Фомин

Ведущая организация: Санкт-Петербургский государственный университет аэрокосмического приборостроения

Защита диссертации состоится" 26" мая 2006 г. в 15 часов на заседании диссертационного совета Д.002.199.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского института информатики и автоматизации Российской академии наук.

Автореферат разослан" 2006 г.

Ученый секретарь

Диссертационного совета Д.002.199.01

кандидат технических наук

АЛ. Ронжин

Ш>6£

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Сравнительно новой проблемой является так называемая глобальная оптимизация запросов в информационной системе, под которой понимается совместная оптимизация потока запросов и выполнение общих операций за один раз. Решение проблемы глобальной оптимизации во многом связано с ' применением методов выявления повторяющихся фрагментов и соединений фрагментов в потоке запросов, что, в свою очередь, соотносится с решением задачи группирования похожих запросов. Это группирование является нетривиальной задачей, обусловленной специфическими конструкциями запросов в сложной информационной системе, многообразием возможных мер близости (различия) 8<2Ь-подобных выражений и алгоритмов группирования. Разработка методов и программных средств для группирования запросов в сложной информационной системе является актуальной теоретической задачей, имеющей важные практические приложения.

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

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

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

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

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

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

Положення, выносимые на защиту:

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения и списка литературы, включающего 150 наименований. Работа изложена на 148 страницах, содержит 16 рисунков и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность работы, сформулированы цель и задачи исследования, положения, выносимые на защиту, научная новизна и научно-практическая значимость полученных результатов, дается характеристика объекта исследования.

Фрагмент реальной сложной информационной системы (финансовая организация "American Express"), используемой для проведения широкомасштабных маркетинговых исследований и относящейся к объектам диссертационного исследования, приведен на рис. 1.

Поирамипш Марютиига (Азия)

(КМрабмжшег}

Рисунок 1. Фрагмент информационной системы для проведения маркетинговых исследований в финансовой организации "American Express"

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

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

[create,..] select <fields> from<tables> [where <logics>] [groupby <fields>]

[sort by <fields>], (i)

где любая из таблиц (tables) и любая часть логического условия (logics) может быть тоже запросом.

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

Таблица 1. Примеры запросов, генерируемых приложением в сложной информационной системе

create table TMP_UAC_417407_15256 UNRECOVERABLE as select distinct MSRCAMP.FACT_CUST_CORP.INDIVIDUAL_ID from MSRCAMP.FACT_CUST_CORP,TMP_UAC_417387_15256, MSRCAMP.DIM_PRODUCT where MSRCAMP.FACT_CUST_CORP.INDIVIDUAL_ID = TMP_UAC_417387_15256.INDIVIDUAL_ID and

((MSRCAMP.DIM_PRODUCT.PL_DESC = 'READER 'S DIGEST MAGAZINE') and (MSRCAMP.FACT_CUST_CORP.FIRST_ORDER_DT >= (SYSDATE - ((180 -27) + 0)))) and MSRCAMP.FACT_CUST_CORP.FIRST_ORDER_PROD_ID =

MSRCAMP.DIM_PRODUCT.PROD_ID__

select distinct MSRCAMP.FACT_CUST_PUB_PRODUCT.INDIVIDUAL_ID from MSRCAMP.FACT_CUST_PUB_PRODUCT, TMP_UAC_490268_ 13090 where MSRCAMP.FACT_CUST_PUB_PRODUCT.INDIVIDUAL_ID = TMP_UAC_490268_13090.INDIVIDUALJD and

((MSRCAMP.FACT_CUST_PUB_PRODUCT.LAST_ORDER_DT >= '08/01/2004') and

MSRCAMP.FACT_CUST_PUB_PRODUCT.LST_MB_LST_SB_MAG_PGM_CD IN ('2', 'Q', W)) order by

MSRCAMP.FACT_CUST_PUB_PRODUCT.INDrVIDUAL_ID_

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

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

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

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

Показано, что практически мало исследованным является применение для анализа потока запросов статистических процедур, в том числе современных методов Data и Text Mining, позволяющих выявлять в экспериментальном материале как сравнительно простые, так и неочевидные закономерности. Этому слабо изученному направлению посвящены следующие главы.

Вторая глава посвящена исследованию статистических методов многомерного группирования данных в контексте задачи анализа потока запросов. Исследуются методы визуализации данных, методы автоматического группирования данных, алгоритмы поиска if-then правил в данных и ассоциативных правил.

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

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

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

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

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

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

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

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

Кластер! Кластер 2

Рис. 2. Пример описания кластеров с помощью логических правил

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

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

Ш rmrcampW»ct_cu*tc<*"P <«0

Й »«M_<tatinct > О

□ numtojoLtebiw <«■ 3 BtoflicJnoO

□ log№_<ither<»6 ^ЫЦодкас-З

Й mercampefacLctat-COfP <" О Щ temp > О Ш tagicjn >О □ k>9k:_other > 0 О arithn\_<-2 Ш eJI_ari1hm <- 3

Проведенное в третьей главе исследование позволило выявить две технологии анализа текстов, способные оказаться полезными для группирования потока запросов в информационной системе. Это технология "ключи от текста" (http://www.fep.ru/text/dataarrays01.html) и технология, используемая в системе TextAnalyst (www.analyst.ru). Характерной чертой данных технологий является то, что они фактически пренебрегают обширными теоретическими изысканиями в области лингвистики, и опираются на результаты формального статистического анализа словоформ и их сочетаний в текстах. Несмотря на кажущуюся внешнюю ущербность подобного анализа, отмеченные технологии демонстрируют достаточно эффективные и не тривиальные результаты, которые способны в определенной мере претендовать на заявляемую функцию "семантический анализ и поиск". Технология "ключи от текста"еще не доведена до стадии коммерческого продукта. Поэтому в для исследования потоков запросов выбрана в качестве основы система TextAnalyst.

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

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

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

Рис. 3. Фрагмент слов-предпочтений и удаляемых слов в словаре Тех1Апа1у51, адаптированном для обработки запросов

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

Получение исходного материала для дальнейшего анализа потока запросов потребовало разработки специальных программных средств, встраиваемых в информационную систему и учитывающих специфику решаемых системой информационных задач. В четвертой главе описаны такие средства, созданные для работы в альянсе с известной системой "The Affinium Suite" компании UNICA (США), предназначенной для проведения полнофункциональных маркетинговых исследований. Эта система включает в себя модули моделирования, планирования, управления и генерации отчетов для обеспечения всей технологической маркетинговой цепочки.

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

Еще одна программная разработка - "Cross-Campaign Analyzer for Affinium Campaign" позволяет идентифицировать "плохие" запросы в повторяющихся маркетинговых кампаниях, обеспечивает детализацию элементов таких запросов для дальнейшего анализа, дает возможность оценивать эффективность использования источников данных, группировать по заданным критериям запросы в потоке запросов для определенных периодов времени. Одна из функций программы заключается в создании логов запросов с привязанными к ним характеристиками производительности (например, время выполнения запроса и др.) и экспорте заказанной информации в требуемый формат.

Для подготовки исходных данных к анализу с помощью инструментов статистического анализа разработана программа "Log Transformer". На входе LogTransformer имеется текстовый файл с запросами вида (1). На выходе LogTransformer выдает таблицу (как в виде текстового файла с разделителями, так и в экранном виде), где столбцами являются различные параметры запроса, а строками - запросы из входного файла (строка из входного файла соответствует строке выходного). Пользователь может выбирать, какие параметры запроса отобразить в таблице.

Программа LogTransformer рассчитывает следующие характеристики запросов:

• types - тип запроса. Для каждого типа запросов создается отдельный столбец. Если данный запрос принадлежит к данному типу, то в таблицу данных заносится 1. В противном случае ячейка оставляется пустой.

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

• logicjn - количество логических условий принадлежности типа: * in (*)

• Iogíc_other - количество логических условий типа =, >, с, =>, <= и т.п.

• alljogics - общее количество логических условий

• monthsjbetween - количество вызовов функции months_between().

• sysdate/current_date - количество вызовов функций sysdate и current_date.

• aríthm_+/- - количество арифметических операций сложения/вычитания.

• all_arithm - общее количество арифметических операций.

• levels - количество уровней запроса. Под уровнем понимается порядок вложенности, то есть запрос вида "Select.. from (select...).. where.." будет 2-х уровневым.

• num_of_selects - количество "Select" в запросе, то есть число подзапросов, включая основной запрос.

• fields_upper_Iev - количество полей, возвращаемых основным запросом (запросом верхнего уровня).

• num_of_tabIes - общее количество различных таблиц, из которых производится выборка в запросе.

Для вычисления указанных характеристик разработана следующая методика. Строка запроса вида (1) сначала разбивается на слова. После этого по первым словам запроса определяется его тип (например, select или select distinct). Далее, если тип запроса select, select distinct или create table, то запускается процедура Selecto со следующими входными параметрами: список слов запроса, список названий таблиц, номер слова, с которого производить дальнейший анализ, уровень запроса (имеется ввиду степень вложенности); и выходными параметрами: структура параметров запроса (состоит из полей "кол-во логич. усл.", "кол-во арифм. действий" и т.д.), номер слова, с которого производить дальнейший анализ, уровень запроса.

В процедуре Select сначала производится поиск слов union или minus (эти слова обозначают, что рассматриваемый запрос состоит из 2-х или более запросов). Если одно из этих слов встретилось, то строка "делится" по этому слову. Одна ее часть обрабатывается дальше, а для другой снова вызывается Select, образуя рекурсию. Рекурсивные вызовы осуществляются также, если вложенный запрос встречается в перечислении таблиц. Анализ производится до окончания перечисления таблиц.

Далее, если после перечисления присутствует слово where, то вызывается одноименная процедура (процедура where()). Процедура where также рекурсивна, так как может включать вложенные скобки, содержащие логические условия. Если скобка была проанализирована рекурсивным вызовом процедуры, то при возврате она (все слова, которые в нее входили) заменяется одним словом "bracket" для облегчения окончательного анализа. Если же в логических условиях встречается вложенный запрос, то вызывается процедура Select(). Алгоритм, реализующий бписанную методику работает в 2 прохода:

1. Находятся все возможные типы запросов и имена таблиц и составляются соответствующие списки (список типов и список имен таблиц).

2. Вычисляются значения параметров запросов. Типы запросов и имена таблиц присутствуют как параметры. Если в запросе присутствует данная таблица (запрос имеет данный тип), то в столбце с названием этой таблицы (типом запроса) ставится "1", если нет, то ячейка остается пустой.

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

Анализу подвергалась группа запросов NET SEG из Readers Digest (объем группы - 1696 запросов), соответствующих одной проведенной маркетинговой кампании. Результаты анализа разделены на 2 группы:

- Результаты анализа совокупности "сырых" запросов.

- Результаты анализа таблиц, содержащихся в запросах.

Цели анализа: - выявление групп запросов и их паттернов со сравнительно небольшим общим временем исполнения; - выявление групп запросов и их паттернов со сравнительно большим общим временем исполнения.

В качестве границ, разделяющих запросы с различными временами исполнения использовались 30,40 и 60 мин.

Для дальнейшей обработки сырых запросов использовалась программа "BigBasket" [http://datadiver.nw.ru/prod_bb.htm], хорошо зарекомендовавшая себя в задаче поиска высокоточных ассоциаций с высоким уровнем поддержки.

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

временем исполнения

Найденные паттерны в запросах Частота встречаемости Точность

Время исполнения меньше 60 мин.

MSRCAMP.CUST_ADDR & MSRCAMP.CUST_ADDR.USPS_STATE_PROVINCE_CD => Less60 173/1523 1

MSRCAMP.FACT CUST_PUB_PRODUCT & MSRCAMP.FACT_CUST_PUB_PRODUCT.INDIVroUAL_ro => Less60 166/1523 0.98

MSRCAMP.CUST ADDR.INDJVroUAL Ю& MSRCAMP.CUST. ADDR => Less60 226/1523 0.98

Время исполнения больше 60 мин.

MSRCAMP.DJM_CONTJHETH & MSRCAMP.DM_CONT_METH.CONTACT_MTHD_DESC & Telemarketing' & MSRCAMP.DIM CONT METH.CONTACT_METHOD CD & MSRCAMP.FACT_CUST_CORP_CONT_METH.INDIVroUAL_ro & MSRCAMP.FACT_CUST_CORP_CONTJvIETH & MSRCAMP.FACT CUST CORP_CONT METH.LTD ORDER QTYMSRCAMP.FACT_ CUST_CORP_CONT_METH.CONTACT_METHOD_CD => МогебО 18/173 0.86

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

В качестве исходных данных в следующем примере используется таблица данных, сконструированная с помощью программы Log Transformer. Из полученной таблицы была сгенерирована случайно организованная матрица данных ("Noise"), которая затем была пристыкована к реальной таблице данных ("Real"). Задача дальнейшего анализа заключалось в том, чтобы с помощью технологий поиска логических закономерностей выделить в "Real" ассоциации элементов запросов, которые не встречаются в "Noise".

Для анализа сформированной таблицы использовалась программа Argos Insightor™ (http://www.argosgrp.com/View.aspx), предназначенная для поиска в данных if-then правил. Было найдено 10 логических правил, описывающих и, соответственно, группирующих реальные данные (рис.4). Эти правила в совокупности покрывают 78 % всех запросов информационной системы в рамках анализируемой маркетинговой кампании. Детальный анализ ассоциаций позволил более четко интерпретировать подгруппы запросов, описываемых той или иной ассоциацией. Например, одна подгруппа запросов характеризуется наличием большой вложенности логических операторов, другой подгруппе свойственно использование арифметических операций и т.д. Такая интерпретация оказалась серьезным подспорьем для специалиста, проводящего работу по повышению производительности информационной системы, давая ему возможность более нацелено исследовать выделяемые подгруппы запросов._

i »лгЬ»_Л.йЫ«_(в watjt • mm*»rjíjMlit»jK_mimJtM k¿i¿_dfar_no_!ncf«_8 ■ aid (о®к_о«ж г»_тю»_! О - "

toOKr_fltíw_fc_íT5cr»_10 Kd Icgis.cdwr.ne.BwO' - &c0tc_o(NKj*_!no«J 1 «ad k»»c_gtbw_oo_m««_22 - 22 and

r tytdmjcmimjimeмi mmj> * tmOn»wm*n_imji<cnjb a«id wMhu» «onji - aMbmjKuncn 5 apd «Мт.яаюега 8-mitmjK>jpatmjS »id ¡SjmtenjnjfienJ - «id «В иЯш_кцм««_2 ■ ató «U_wi»un_(ie_ee<e_7 »

•Лjrtfw kuw*»_7 «id >í_a<W»nyj»unanjt» «IL«*i»U»j»»*»_1t «id • I*><>i»_ik>_><w<l2 mi

WffX_ut.aeí*ctt_míjnof«J • nwuO*MCta.i><un»-.'< Dt*n RMDltnRwlOXi

* m»rtw_e<J>bl«_(M_»»Mj - 1*ягЬ«г_о(_аЫ»_1пог«J and lojic_<»arjna4_1• lejie <*мг_«вп(_1 and bife «!w_i*¡_mw«_3 » to$ic_c>tíwrjr<ye 3 vid »y»&ta_cwrwt.íalo жикм_0 - «n«»Ld«ta nejiw»3 and а«ЫпйО_(ТУ*е_0 « wd»ru»jng«sJl «nd r anfc«yia_nw«J-imhffijie mo«„1 andanthmw>_nwr»_$* anvwu»jm**3aedatermv.muiicrO-»mhír^nc^fno jfl.jiflfer^.BctjnertLl W«{jntonjwtjnofij!

mi «Kjtn)hnx.no_fnaf«„£ * aH_«ftthmjx»_fromJ> «nd aH„«ri<i»nj»e_in«»Jí * аЯ_«гМяп_|»ц_|»оП1_1в RaaJOata«RariOal* d tejtc_o»*<_)H»«_l » tosk¡_flÍM«_no_mot»_1 md к«к_о<ш_п<>_1к»»_10»l«giejcfcarjiojiw»_10 and •

r tro rnOf«J> and anltojw iw*»J) ■ »r¡tí»i\.r«s_iT*jr«_0 and - andwr .1 and »B_«(aim.i)Hj>ie«_i •

»¡]_arriítfr>Jio_fnor»_4 ■ aH,jni№)jw,jncrO> «id J*.'„n©_ínot«_! - tfeaft

Рис. 4. Фрагмент логических правил, характеризующие ассоциации в характеристиках запросов

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

Исходный запрос: select distinct INDIVIDUALJD from MSRCAMP_CUST_ADDR where ((MSRCAMP_CUST_ADDRJNDIVIDUALJD < 3950000000) AND MSRC AMP_CUST_ ADDR_POST AL_CD IN 21201 ','21202721203','21205','21206','21209', '21210V21211','21212','21213','21204','21207',,21208','21219','21220','21221','21227','21228V21 234','21236','21214','21215','21216','21217','21218','21223','21224','21229',,21230','2123Г,'21225 ','21226','21240','21233','21235','21239','21241','21263','21264','21268','21270','21273V21274','2 1237','21244','21271','21282','21284','21285','21286','21279','2128Г,'21289','21290V21297','2129 8')) order by INDIVIDUALJD

Наиболее близкий к исходному запрос select distinct INDIVIDUALJD from MSRCAMP_CUST_ADDR where ((MSRCAMP_CUST_ADDRJNDIVIDUAL_ID < 3950000000) AND MSRCAMP_CUST_ADDRJPOSTAL_CD IN ('07101', '07102', '07103', '07104', '07105', '07106', '07107', '07108', '07112', '07114', '07192')) order by INDIVIDUALS

Наиболее отдаленный от исходного запрос select distinct MSRCAMP_CUST_ADDR_INDIVIDUAL_ID from

MSRCAMP_CUST_ADDR, TMP_UAC_413712_12362, MSRCAMP_DIM_POSTAL_.CODE where MSRCAMP_CUST_ADDR_ INDIVIDUALS =

TMP_UAC_413712_12362_INDIVIDUAL_ID and (MSRCAMP.CUST_ADDR_USPS_ STATE_PROVINCE_CD IN ('AS','AP,'FM',,GU',,MH,,'MP', !PW','AE',,AA,,'PR,,'Vr) OR (MSRCAMPJDIMJ>OSTAL_CODE_MKT_ADV_REGION_CD = 18')) and MSRCAMP_CUST_ADDR_POSTAL_9_CD=SRCAMP_DIM_roSTAL_CODE_roSTAL_9_ CD order by MSRCAMP_CUST_ADDRJNDIVIDUALJD

Скорость ранжирования запросов по степени "похожести" составила доли секунды на ПК Pentium IV 3 ГГц, что является весьма важным при проведении практических исследований потока запросов.

В целом повышение производительности информационной системы после проведения комплекса работ с использованием разработанных инструментов статистического анализа потока запросов характеризуется графиками (рис. 5 и рис. 6). Как следует из этих графиков, несмотря на постоянное увеличение количества обрабатываемых записей (рис. 5), удалось уменьшить среднее время исполнения запросов за период проведения отдельной маркетинговой кампании более чем в 2 раза.

Др оптимизации

После опгидвации

Дата

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

Дага

Рис. 6. Среднее время исполнения запросов в отдельной маркетинговой

кампании

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. ДюкВ.А., ПолухинК.В., Фомина И.К. Специфика прикладной статистики в предметной области со сложной системной организацией // В сб. "Технические средства судовождения и связи на морских и внутренних водных путях". - СПб, 2005. - С. 82-86.

2. Полухин К.В. О методах группирования запросов в сложной информационной системе II В сб. "Технические средства судовождения и связи на морских и внутренних водных путях". - СПб, 2005. - С. 126-128.

3. Полухин К.В. Практические методы, алгоритмы и программы анализа потока запросов в сложной информационной системе. - СПб: "Анатолия", 2005.-42 с.

4. Дюк В.А., Полухин К.В. Подход к конструированию случайной выборки с заданным распределением в задачах анализа многомерных данных //

1 Сб. научн. трудов юбил. конф. каф. информатики и управления в мед

системах СПбМАПО. - СПб: "Издательский дом СПб МАЛО", 2006. -С. 41-45.

5. Полухин К.В. Программа для подготовки потока запросов информационной системы к статистическому анализу// В сб. "Автоматизация, информатизация, инновации в транспортных системах". - СПб, 2006. -С. 163-169.

(

I

Отпечатано в издательстве ООО «Анатолия» Тираж 100 экз.

/û£àA ГШ

8 6 4 9

ВВЕДЕНИЕ.

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 раза.

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 с.