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

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

Кантор Илья Александрович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ОБУЧАЮЩИХ

СИСТЕМ, ОСНОВАННОЕ НА ГЕНЕРАЦИИ ФУНКЦИОНАЛЬНО ЗАВИСИМЫХ ЦЕПОЧЕК И СПЕЦИАЛИЗИРОВАННЫХ АЛГОРИТМАХ

ВЫБОРКИ

05 13 11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

2 3 ,'/

Москва - 2008

003170590

Работа выполнена в Московском государственном институте связи и информатики

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

доктор физико-математических наук,

профессор

Данилов В Г

Официальные оппоненты доктор технических наук,

доцент

Никольский С Н

кандидат технических наук, Федоров К М

Ведущая организация Московский государственный университет пу-

тей сообщения

Защита состоится 24 июня 2008 года в 14 ч 00 мин на заседании Диссертационного совета Д 212 133 01 при Московском государственном институте электроники и математики по адресу 6109028, Москва, Б Трехсвятительский пер , д 3/12

С диссертацией можно ознакомиться в библиотеке МИЭМ Автореферат разослан " %Ъ 2008

Ученый секретарь диссертационного совета уу

кандидат технических наук, доцент Бузников С Е

Общая характеристика работы

Актуальность темы

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

В настоящей работе предложена модификация порождающих грамматик для систем электронного обучения математике

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

Такой способ обладает рядом известных недостатков, например

• небольшое количество вариантов задач,

• нельзя использовать элементы одной задачи для описания другой

Можно кратко сформулировать актуальные преимущества использования предлагаемого в работе метода генерации задач как

1 большое количество вариантов в рамках единой схемы решения,

2 возможность описания сложной задачи как композиции подзадач

Для систем электронного обучения также актуальны технические

возможности

1 возможность применения в интернет, в браузере,

2 интегрируемость генератора в независимую систему обучения

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

Новая индексная структура также востребована в других системах с большим объемом многопараметризованных данных, включая интерфей-

сы по выбору товара, маршрута, системы оптимизации, некоторые методы поиска по полуструктурированным базам и др

Цель и задачи работы

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

Новый язык должен обеспечивать следующие основные возможности

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

2 Использовать существующие описания задач при создании новых

3 Предоставлять удобные средства описания задач

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

1 реализует функционал, заложенный спецификацией языка,

2 предоставляет программные интерфейсы для интеграции с существующими системами обучения, с интернет-системами,

3 обеспечивает средства добавления новых задач, организации существующих задач,

4 гарантирует стабильное, не требующее приостановки операций внесение изменений в систему,

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

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

В частности, такая структура должна поддерживать эффективный поиск при большом количестве записей

Дополнительно, для практического тестирования и внедрения должна быть создана практическая реализация индексной структуры, произведена апробация и сравнительный анализ Характеристики новой индексной структуры следует сравнить с традиционными индексными структурами

В соответствии с этим в диссертационной работе поставлены и решены следующие основные задачи

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

2 Создание специализированного языка для описания таких цепочек, включая

(a) формальную грамматику языка,

(b) интерпретатор для его обработки,

(c) интеграцию с символьными вычислениями в системе Mathematica

3 Программная реализация генератора задач, удовлетворяющего описанным требованиям и основанного на новом языке

4 Проверка математической модели и реализации путем внедрения генератора в обучение

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

(a) описание алгоритмов построения, поиска и обновления индекса,

(b) исследование и стоимостные оценки предложенных алгоритмов,

(c) рекомендации по выбору параметров индексной структуры

6 Реализация индексной структуры на основе СУБД Cache, тесты новой структуры, сравнение с традиционными индексами в РСУБД Oracle 10g

Методика исследования

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

Описана модель на основе цепочек с функциональными зависимостями, создан язык для задания цепочек

С использованием теории графов, формальных грамматик, объектно-ориентированного программирования и ЬЬ(*)-генератора парсеров, создан генератор задач

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

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

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

С использованием постреляционной СУБД Cache' произведена реализация новой индексной структуры

Получены данные по производительности на синтетических тестах по сравнению с традиционными методами поиска Произведена проверка надежности и эффективности поиска на реальных базах данных

Научная новизна

Научной новизной обладают следующие результаты диссертационной работы

1 В работе описан новый грамматик — грамматики с функциональными зависимостями Создан язык для описания порождающих грамматик для семейств математических задач

2 Реализован генератор задач, работающий на созданном языке

Предусмотрены архитектурные и программные средства интеграции в существующие системы обучения

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

4 Выполнена практическая реализация новой индексной структуры для постреляционной СУБД Cache'

Практическая значимость

Теория и программные компоненты, представленные в работе, могут быть использованы для обучения решению задач по математике, физике и другии наукам, в которых требуются алгоритмические навыки решения задач

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

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

Реализация и внедрение результатов работы

Тестирование программных компонент системы начато в 2005 году Элементы системы прошли апробацию на базе Московского технического университета связи и информатики (МТУСИ)

Индексная структура была создана в 2006 году, успешно прошла тестирование для поиска по грамматикам и, кроме того, произведено внедрение новой индексной структуры для подбора предложений по базе туристического агентства "Обновление", подбора жилья в риэлторской компании

"Рестро", в ряде других компаний

Доклады и печатные публикации

Результаты работы, связанные с интеграцией с системами обучения, докладывались на "Международной конференции РНР-разработчиков" в 2006 году, на конференции "Российские Интернет-Технологии" в 2008 году

Публикации

1 Кантор И А "Метод нестрогого поиска в базах полуструктурированных данных" Технологии высокопроизводительных информационно-вычислительных систем Сборник статей молодых ученых Переславль-Залесский "Университет города Пере-славля 2003г

2 Кантор И А "Интернет-система дистанционного обучения на основе порождающих грамматик Хомского", сборник научных трудов, МИЭМ, 2007г

3 Кантор И А "Многокритериальные ограниченные сортирующие выборки в реляционных СУБД Метод деревьев битовых карт", журнал "Информационные Технологии", изд "Новые Технологии", N2, 2008г

Структура работы

Первая глава закладывает необходимые основы для создания языка описания математических задач

Секции 1-4 содержат обзор существующих подходов к генерации и введение в новый подход Представлено сравнение существующих методов с предлагаемым, обосновано создание метода, использующего порождающие грамматики

Секции 5-6 вводят грамматики с детерминированными правилами Описан граф вывода(аналог дерева вывода) для таких грамматик, показан способ его получения Доказан ряд теорем о свойствах графа вывода и указан способ получения из него сентенциальной формы

В секции 7 описаны грамматики с функциональными зависимостями и введено понятие обобщенного объекта

Во второй главе рассматривается язык описания грамматик, его грамматика и интерпретатор

В секциях 1-2 предложен новый язык LogicTask для описания грамматик с детерменированными правилами и функциональными зависимостями Приведена краткая грамматика(подробная дана в приложении), рассмотрены основные компоненты языка

В секции 3 описаны алгоритмы разбора(полукомпиляция), внутренняя структура, основные объекты и работа интерпретатора языка

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

Секции 1-3 содержат формализацию задачи, обзор и сравнение существующих подходов к ее решению

В секциях 4-G предложен новый метод "метод деревьев битовых карт" Описана индексная структура, операции вставки, удаления и поиска Выведены оценки для размера индексной структуры, ее плотности, для количества операций при поиске Предложены дополнительные оптимизации и рекомендации по выбору параметров индексной структуры

В секциях 7-8 проведено сравнительное тестирование поиска по новой индексной структуре, реализованной на СУБД Cache', по сравнению с некоторыми традиционными способами на Oracle 10g

Основное содержание работы

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

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

Далее представлена модификация контекстно-свободных грамматик,

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

Определение 1. Цепочка а функционально зависит от цепочек ci с,г, если а = /(ci Сп) для некоторой функции грамматики /

Функциональное правило над терминалами VT, нетерминалами VN и функциями грамматик F — это элемент множества VNxFx (VTU VN)*x x (VT U VN)*

При выводе грамматики оно ставит в соответствие нетерминалу VN значение функции грамматики F на цепочке (VT U VN)*

Определим грамматику с функциональными зависимостями как расширение контекстно-свободной грамматики Эта грамматика будет использоваться для генерации функционально зависимых цепочек

Определение 2. Грамматика с функциональными зависимостями (или функциональная грамматика) Gf - это шестерка (VT,VN,R,S,F,RF), где VT, VN, R, S определяются аналогично контекстно-свободным грамматикам, F — набор функций грамматики, RF — функциональные правила над VT, VN, F

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

Определение 3. Отображаемый объект рекурсивно определяется как

1 набор именованных свойств - упорядоченных пар вида (key, value), где

key - цепочка символов алфавита имен (подмножество естественного алфавита)

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

2 str ingValue - представление объекта, закодированное непосредственно для отображения через естественный алфавит

Причем значение key уникально среди пар (key, value), так что value по key определяется однозначно

Таким образом, отображаемый объект представляется строкой естественного алфавита и может содержать функции грамматики

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

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

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

Компоненты языка

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

Правило объявляются так <имя> rule <тело>

Предусмотрены различные типы правил для формул, для облегчения интернационализации i енерируемых задач

Команды В правилах могут быть функции грамматики, "команды", которые выделяются тильдой например ~If, ~Сабе

Общий синтаксис кодманд имеет вид ~<имя команды>{аргументы} Результат выполнения команды подставляется вместо ее вызова

Например, команда математических вычислений вызывается как ~ { } Ее результатом являются обработка аргумента по правилам языка Mathcmatica

Таким образом можно, например, задать правило, вычисляющее сумму двух чисел sum rule { Сумма равна Simplify[#a+#b] } }

Также доступны условные команды If /Case, построение графиков и другие

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

1 на уровне правил,

2 на уровне включения одной грамматики в другую,

3 на уровне пакетов грамматик

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

Далее описываются внутреннее устройство интерпретатора LogicTask, процессы полукомпиляции и интерпретации, внутреннее представление правил, грамматик, команд, отображаемых объектов и тп

Порождающая грамматика, описанная на LogicTask сначала транслируется во внутреннее представление При этом производится синтаксическая проверка Затем интерпретатор производит генерацию, основываясь на сохраненном оттранслированном варианте

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

Рассмотрены известные методы многокритериальных сортирующих с заданным окном Предложен новый метод деревьев битовых карт, использующий индексную структуру, где Б-деревья применяются для поддержки обновлений в сортированных битовых картах

Будем рассматривать выборки из отношения(или таблицы) Т с заголовком < Ai,N >, < .Аг, N >, ,< Afteidbcouiit,N > Элементы множества кортежей(записи) обозначим Тд, Каждый триплет кортежа имеет вид

<v42, N, г;г> Упрощенным обозначением кортежа является запись в виде последовательности значений атрибутов {г>1, ,Vflti^Cmmt} Будем обозначать V, = 1J и, — множество всех значений атрибута А,, V, 6 N, \/г

Определение 4. Задачей(или условием задачи) ограниченной сортированной многокритериальной выборки называется упорядоченный набор Q = (Cond, /, с, s, Skip, Count, Тор), где

• Cond = {Cl(x),i = 1, , ?г} — упорядоченный набор усло-вий(предикатов) равенства EqCond С Cond и неравенства или нахождения в промежутке RangeCond С Cond Cond = EqCond U RangeCond

• f {Cond}, ,Cond„} —■> {0,1} — логическая ограничивающая функция над условиями

• с — перестановка, которая задает отображение номера Cond на номер атрибута А и, таким образом, привязывает условие к атрибуту Одному атрибуту может соответствовать несколько условий

• s 6 1, , | А | — номер атрибута сортировки

• Skip € N — число пропускаемых записей

• Count £ N — размер окна поиска

• Тор € N — число максимального предпросмотра

Определение 5 Запись {ui, ,Vfiri,hCmmt называется удовлетворяющей критериям задачи, если f(Condi(v,^)), ,Condu(v^n))) = 1

Определение 6. Полным множеством результатов для задачи Q является множество Results АН упорядоченных по атрибуту As записей, удовлетворяющих критериям задачи

Определение 7 Искомым множеством или окном поиска для задачи Q называется упорядоченное множество

ResultsWmdow = (ResultsAllskip+\, , ResultsAllshp+Count)

Будем говорить, что окно поиска полное, если | ResultsWmdow |= Count

Определение 8 Числом предпросмотра для задачи Q называется число CountMore = mm(| Results All | — (Skip + Count), Top)

Определение 9 Решением задачи <3 называется упорядоченная пара

(ВевиН зШгпйоги, Сои^Моге),

где КевиШХУгпсЬги — искомое множество, а СоипЬМоге — число предпро-смотра

Структура индекса

Индексная структура состоит из нескольких частей Первая из них — основное Б-дерево БеагсНТгее

Каждому ключу Кг основного Б-дерева соответствует значение Кг юн € причем отображение ключей в V, инъективно, те не более одного ключа в дереве с данным значением атрибута В элементе, который задан ключом К1, хранятся данные о записях со значенями у3 £ [■^г,40^,^1+1,60^), причем = 0, К\щ еоН = оо

Данные элемента основного дерева состоят из нескольких компонент

1 Набор пар (А,п, От),т = 1, , /геМвСоипЬ, где Ат — имя атрибута, а £>т — Б-дерево значений атрибута Ключами От являются значения атрибута V £ а данными — битовые карты Каждому ключу V соответствует ровно одна битовая карта, которая содержит столько единиц, сколько записей таблицы имеют значение ьт = V

2 Б-дерево данных ЯоинйТгее имеет своими элементами пары (р = (гоипй^), где р — позиция в битовых картах, гогигд — идентификатор записи в таблице, а 5 — значение г>5 этой записи Каждая позиция появляется в дереве не более одного раза

3 Б-дерево позиций ОгдегТгее состоит из элементов вида (гоыгй,р) и хранит отображение идентификатора записи в позицию в битовых картах

4 Битовая карта свободных мест Extentk содержит 1 на тех позициях, которые есть в ЯоипдТгее, и 0 — на остальных

Оценка размера индексной структуры

Средняя оценка размеры индексной структуры ¿'(байт) выполнена для ЭВМ семейства х86, 32-битной адресации, для общепринятых размеров типов данных, при равномерном распределении значений полей по кортежам

Она имеет вид 5 = [32 | Т | +Ш(1 + ( ц | compre&s(^t

где compress(a) — средняя степень сжатия битовой карты при равномерном распределении с плотностью а

Теорема 1 При равномерном распределении значений vs мат ожидание плотности дерева поиска равно-¡тг~®-

2 7т„ш^,ге \BitmapSize

Оценка числа операций при поиске

В современных РСУБД используется стоимостной оптимизатор Для практического применения алгоритма необходима не асимптотическая оценка, а оценка, разбитая по типам - число операций должно быть задано отдельно для поиска по дерева, булевых вычислении, сортировки и т и Введем обозначения

• ResultsPer Element =

• RowidTreeh = [logBitmapSize]

• Среднее число битовых карт(необходимых операндов) для вычисления логической функции f Mapj, и количество операций для вычисления / Cost/ Они зависят от вида функции Например, если / = C[v ~С~2, то Мар/ = 2, Costj = 3,

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

• Elem = [mm(SkipЛ-Count, \ ResultsAll — [тш(5А,гр, | BesultsAll

Тогда оценка количества операций при поиске будет иметь вид

• Операций чтения битовых карт Elem * Map/ операций длины BitmapSize,

• Логических операций над битовыми картами Elem * Costf операций дтины BitmapSize,

• Results Per Element операций поиска узла по ключу, для каждого из Б-деревьев общим количеством Elem, штук, со средней высотой RowidTreeh,

• Elem операций сортировки ResultsPerElement чисел

Следедующие основные результаты выносятся на защиту

1 Способ генерации описанных в работе цепочек с функциональными зависимостями путем описания на предложенном языке LogicTask

2 Система генерации математических задач, включающая в себя парсер и интерпретатор LogicTask

3 Индексная структура для РСУБД, обеспечивающая эффективные ограниченные сортированные многокритериальные выборки

4 Оценки размера, стоимости операций, рекомендации по параметрам новой индексной структуры

5 Реализация и результаты тестирования новой индексной структуры на базе СУБД Cache',практическое тестирование новой индексной структуры

Основное содержание диссертационной работы изложено в

следующих публикациях:

[1] Кантор И А — Метод нестрогого поиска в базах полуструктурированных данных // Технологии высокопроизводительных информационно-вычислительных систем Сборник статей молодых ученых Переславль-Залесский "Университет города Переславля 2003 - 132с ил , стр 53-64

[2] Кантор И А Интернет-система генерации задач на основе порождающих грамматик // Сборник научных трудов МИЭМ, 2007

[3] Кантор И А Многокритериальные ограниченные сортирующие выборки в реляционных СУБД Метод деревьев битовых карт // Журнал "Информационные Технологии", нзд "Новые Технологии", N2, 2008, стр 42-46

Заказ Jfe 151/05/08 Подписано в печать 14 05 2008 Тираж 100 экз Уел пл 0,75

vN ООО "Цифровичок", тел (495) 797-75-76, (495) 778-22-20 {'У;, www cfr ru, e-mail info@cfr ru

Введение

1 Генерация математических задач при помощи модификации формальных грамматик

1.1 Введение.

1.2 Функции математического ядра

1.3 Обзор существующих математических ядер.

1.3.1 Полностью раздельное описание задач.

1.3.2 Подстановка зависимых параметров, основанная на случайном выборе.

1.3.3 Языки программирования общего назначения

1.3.4 Использование математических пакетов.

1.4 Применение порождающих грамматик.

1.4.1 Требования к генератору задач.

1.4.2 Реализация простейшего примера ах — b.

1.4.3 Сравнение предлагаемого подхода с существующими

1.5 Грамматики с детерминированными правилами.

1.6 Дерево и граф вывода детерминированной грамматики

1.6.1 Дерево вывода детерминированной грамматики

1.6.2 Граф вывода детерминированной грамматики

1.7 Генерация цепочек с функциональными зависимостями

1.7.1 Обобщенные символы. Объектные грамматики

1.7.2 Отображаемые объекты. Функции грамматики

1.7.3 Грамматика с функциональными зависимостями

1.7.4 Применение грамматик для генерации задач.

2 Язык описания грамматик

2.1 Введение в LogicTask.

2.1.1 Пример описания семейства задач на LogicTask

2.1.2 Компоненты языка.

2.2 Грамматика LogicTask.*.

2.2.1 Внешняя грамматика

2.2.2 Внутренняя грамматика.

2.3 Интерпретатор LogicTask.

2.3.1 Основные типы объектов.

2.3.2 Деление объектов по иерархиям

2.3.3 Компиляция грамматики.

2.3.4 Генерация.

2.3.5 Пример компиляции.

2.3.6 Структура правил.

2.3.7 Команды

2.3.8 Интерпретация правил.

3 Многокритериальные ограниченные сортирующие выборки в реляционных базах данных. Метод деревьев битовых карт.

3.1 Введение.

3.2 Задача ограниченной сортированной многокритериальной выборки.

3.3 Способы решения задачи Q.

3.3.1 Пересечение битовых карт.

3.3.2 Сканирование Б-дерсва.

3.3.3 Геометрические индексы: i?*-tree, Ы-tree, X-tree и др.

3.3.4 Метод упорядоченных битовых карт.

3.3.5 Комбинированные методы.

3.4 Дерево битовых карт.

3.4.1 Принципы построения индекса.

3.4.2 Структура индекса.

3.4.3 Вставка записи в основное дерево поиска.

3.4.4 Удаление записи.

3.4.5 Блокировка и одновременный доступ

3.4.6 Поиск по дереву битовых карт.

3.4.7 Размер основного дерева поиска.

3.4.8 Дополнительные оптимизации

3.5 Оценка операций при поиске.

3.6 Выбор параметра BitmapSize.

3.6.1 Оптимизация операций ввода-вывода.

3.6.2 Влияние на стоимость поиска.

3.6.3 Оценка плотности при равномерном распределении

3.7 Сравнение со сканированием Б-дерева.

3.8 Сравнительное тестирование.

3.8.1 Методы поиска.

3.8.2 Размеры индексных структур.

3.8.3 Агрегатные результаты

3.8.4 Результаты по времени и блокам.

3.8.5 Дополнение.

Актуальность темы

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

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

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

В настоящей работе порождающие грамматики применяются для систем электронного обучения математике.

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

Такой способ обладает рядом известных недостатков, например:

• небольшое количество вариантов задач,

• нельзя использовать элементы одной задачи для описания другой.

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

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

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

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

Ни одна из известных систем электронного обучения (MathAid, Angel Learning, "1С Репетитор: Математика", всего рассмотрено 14 различных систем см. в приложении) такого не может Большое количество вариантов задач весьма востребовано при обучении, проведении экзаменационных, тестовых работ.

Правила вывода одной порождающей грамматики могут применяться в часть другой (наследование грамматик /1/). Это позволяет описывать

Например, в системе "1С Репетитор: Математика" находится всего около 600 задач, в системе "MathAid" - порядка 1500 задач, по несколько - на каждую тему сложные задачи в виде композиции нескольких подзадач. Такая возможность в существующих системах математического обучения отсутствует.

Можно кратко сформулировать актуальные преимущества использования предлагаемого в работе метода генерации задач как:

1. большое количество вариантов в рамках единой схемы решения,

2. возможность описания сложной задачи как композиции подзадач.

Для систем электронного обучения также актуальны технические возможности:

1. возможность применения в интернет, в браузере,

2. интегрируемость генератора в независимую систему обучения.

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

Стандартом де-факто для такого хранения являются реляционные базы данных.

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

Но объем такой базы, в отличие от традиционных систем, составляет не тысячи, а сотни тысяч, миллионы и более записей. Поэтому актуально создание специализированной индексной структуры. В работе предложено "дерево битовых карт".

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

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

Такие выборки нужны не только в высоконагружепных системах, включая:

• интерфейсы по выбору товара, маршрута и т.д в реальном времени,

• системы оптимизации,

• системы принятия решений.

Например, типичная задача такой выборки - нахождение первых 20 самых дешевых предложений в большой базе, причем на параметры искомых предложений накладывается большое количество разнообразных условий.

Сотни условий на параметры накладываются при многокритериальных сортированных выборках также в задачах астрономии /2, 3/.

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

Цель и задачи работы

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

Новый язык должен обеспечивать следующие основные возможности.

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

2. Использовать существующие описания задач при создании новых.

3. Предоставлять удобные средства описания задач.

Требуется создать интерпретатор языка и использующий его генератор задач, обладающий следующими характеристиками:

1. реализует функционал, заложенный спецификацией языка,

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

3. обеспечивает средства добавления новых задач, организацир! существующих задач,

4. гарантирует стабильное, не требующее приостановки операций внесение изменений в систему,

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

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

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

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

В соответствии с этим в диссертационной работе поставлены и решены следующие основные задачи:

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

2. Создание специализированного языка для описания таких цепочек, включая a) формальную грамматику языка, b) интерпретатор для его обработки, c) интеграцию с символьными вычислениями в системе Mathematica.

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

4. Проверка математической модели и реализации путем внедрения генератора в обучение.

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

6. Реализация индексной структуры на основе СУБД Cache', тесты новой структуры, сравнение с традиционными индексами в РСУБД Oracle 10g.

Методика исследования

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

Описана модель на основе цепочек с функциональными зависимостями, создан язык для задания цепочек.

С использованием теории графов, формальных грамматик, объектно-ориентированного программирования и ЬЬ(*)-геиератора парсеров /4/, создан генератор задач.

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

Изучены существующие алгоритмы многокритериального поиска, включая методы, основанные на как деревьях /3, 5, 6, 7/ и битовых картах /8, 9/. Рассмотрены их характеристики в приложении к рассматриваемой задаче.

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

С использованием постреляционной СУБД Cache' /10/ произведена реализация новой индексной структуры.

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

Научная новизна

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

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

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

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

4. Выполнена практическая реализация новой индексной структуры для постреляционной СУБД Cache', получены результаты практических тестов.

Практическая значимость

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

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

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

Реализация и внедрение результатов работы

Тестирование программных компонент системы начато в 2005 году. Элементы системы прошли апробацию на базе Московского технического университета связи и информатики (МТУСИ).

Индексная структура была создана в 2006 году, успешно прошла тестирование для поиска по грамматикам и, кроме того, произведено внедрение новой индексной структуры для подбора предложений по базе туристического агентства "Обновление", подбора жилья в риэлторской компании "Рестро", в ряде других компаний.

Доклады и печатные публикации

Результаты работы, связанные с интеграцией с системами обучения, докладывались на "Международной конференции РНР-разработ^иков" в 2006 году, па конференции "Российские Интернет-Технологии" в 2008 году.

Публикации:

1. Кантор И.А. "Метод нестрогого поиска в базах полуструктурированных данных" Технологии высокопроизводительных информационно-вычислительных систем: Сборник статей молодых ученых. Переславль-Залесский: "Университет города Пере-славля 2003г.

2. Кантор И.А. "Интернет-система дистанционного обучения на основе порождающих грамматик Хомского", сборник научных трудов, МИЭМ, 2007г.

3. Кантор И.А. "Многокритериальные ограниченные сортирующие выборки в реляционных СУБД. Метод деревьев битовых карт", журнал "Информационные Технологии", изд. "Новые Технологии", N2, 2008г.

Структура работы

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

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

Секции 5-6 вводят грамматики с детерминированными правилами. Описан граф вывода(аналог дерева вывода) для таких грамматик, показан способ его получения. Доказан ряд теорем о свойствах графа вывода и указан способ получения из него сентенциальной формы.

В секции 7 описаны грамматики с функциональными зависимостями и введено понятие обобщенного объекта.

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

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

В секции 3 описаны алгоритмы разбора(полукомпиляция), внутренняя структура, основные объекты и работа интерпретатора языка.

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

Секции 1-3 содержат формализацию задачи, обзор и сравнение существующих подходов к ее решению.

В секциях 4-6 предложен новый метод: "метод деревьев битовых карт". Описана индексная структура, операции вставки, удаления и поиска.

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

В секциях 7-8 проведено сравнительное тестирование поиска по новой индексной структуре, реализованной на СУБД Cache', по сравнению с некоторыми традиционными способами на Oracle 10g, более подробно описанными в /11, 12, 13/.

Выводы

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

Однако, описанные недостатки частично нивелируются средствами, позволяющими использовать любой способ описания там, где он оптимален:

• Возможно отдельное описание конкретной задачи

• Специализированная графическая оболочка и язык-фасад для описание через набор параметров

• Есть программные и архитектурные решения для интеграции языка с программами на Java

Заключение

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

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

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

Для поиска по большой базе задач предложена новая индексная структура. Как и многие теоретико-практические результаты в области проектирования эффективных СУБД, она не привязана жестко к предметной области, а может быть применена в ряде смежных областей, включая САПР, пользовательские интерфейсы.

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

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

1. М. Aksit, R. Mostert, and B.R.H.M. Haverkort. Compiler generation based on grammar inheritance. 1990.

2. Parr and Quong. LL and LR translators need k>l lookahead. SPNOTICES: ACM SIGPLAN Notices, 31, 1996.

3. Christian Bohm, Stefan Berchtold, and Daniel A. Keim. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv., 33(3):322-373, 2001.

4. Marcel Kornacker. High-performance extensible indexing. In VLDB '99: Proceedings of the 25th International Conference on Very Large Data

5. Bases, pages 699-708, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.

6. John T. Robinson. The k-d-b-tree: a search structure for large multidimensional dynamic indexes. In SIGMOD '81: Proceedings of the 1981 ACM SIGMOD international conference on Management of data, pages 10-18, New York, NY, USA, 1981. ACM.

7. Ioannadis Y.E. Chan C.-Y. Bitmap index design and evaluation. In SIGMOD Conf., 1998.

8. Yu P.S. Wu K.L. Range-based bitmap indexing for high cardinality attributes with skew. Technical report, IBM Watson Research Center, 1996.

9. W. Kirsten, Michael Ihringer, and Anthony Rudd. Object-Oriented Application Development Using the Cache Postrelational Database. SpringerVerlag, 2003.

10. Donald K. Burleson. Oracle High-Performance SQL Tuning. McGraw-Hill, Inc., New York, NY, USA, 2001.

11. Gavin J. T. Powell. Oracle Performance Tuning for 10gR2, Second Edition. Digital Press, Newton, MA, USA, 2006.

12. Richard Niemiec. Oracle Database lOg Performance Tuning Tips & Techniques. McGraw-Hill Osborne Media, 2007.

13. Система электронного обучения "angel learning". http://angellearning.com/.

14. Система электронного обучения "atutor". http://www.atutor.ca/.

15. Документация по системе электронного обучения "blackboard", http: //www.blackboard.com/us/index.Bb.

16. Пинский А.И. Гуртовой А.В. Автоматизация и проектирование обучающих систем с использованием порождающих грамматик. НИИВО, 1989.

17. Ульман Дж. Ахо А. Теория синтаксического анализа, перевода и компиляции, Том 1. Издательство "Мир 1978.

18. Richard Н. et al. Gamma, Е. Design patterns: elements of reusable object-oriented software. Addison-Wesley Professional, 1995.

19. Wolfram Research. Wolfram Mathematica Documentation. http://documents.wolfram.com/mathematica/.

20. Кантор И.А. Интернет-система генерации задач на основе порождающих грамматик. МИЭМ, 2007.

21. Terence J. Parr and Russell W. Quong. ANTLR: A predicated-LL(k) parser generator. Software Practice and Experience, 25(7):789-810, 1995.

22. Rosanna Lee and Scott Seligman. The Jndi API Tutorial and Reference: Building Directory-Enabled Java Applications. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2000.

23. Alan Shalloway and James R. Trott. Design Patterns Explained: A New Perspective on Object-Oriented Design. Addison-Wesley Professional, Septembre 2001.

24. Дейт Дж. Введение в системы баз данных. Вильяме, 2006.

25. Quass D. O'Neil P. Improved query performance with variant indexes. In SIGMOD Conf, 1997.

26. Buchmann A. Wu M.C. Encoded bitmap indexing for data warehouses. In 14th ICDE, 1998.

27. Graefe G. O'Neil P. Multi-table joins through bitmapped join indices. In SIGMOD Record, 24(3j, 1995.

28. Кантор И.А. Метод нестрогого поиска в базах полуструктурированных данных. Переславль-Залесский: "Университет города Переслав-ля 2003.

29. Sarawagi S. Indexing olap data. In Bulletin of the Technical Committee on Data Eng., Vol 20, No. 1, 1997: ;

30. Яблонский С.В. Введение в дискретную математику. М.: Высш. шк., 2002.

31. К.Дж. Дейт. Введение в системы баз данных, изд-во Вильяме, 2006.

32. David Salomon. A Concise Introduction to Data Compression. 2008.

33. Faloutsos C. Sellis Т.К., Roussopoulos N. The r+-tree: A dynamic index for multi-dimensional objects. In Hammersley P. Stocker P.M., Kent W., editor, VLDB, pages 507-518. Kaufmann M., 1987.

34. Kriegel H.-P. et al. Beckmann N. The r*-tree: An efficient and robust access method for points and rectangles. In Jagadish H.V. Garcia-Molina H., editor, SIGMOD Conference, pages 322-331. ACM Press, 1990.

35. Kriegel H.-P. Berchtold S., Kcim D.A. The x-tree : An index structure for high-dimensional data. In Buchmann A.P. et al. Vijayaraman T.M., editor, VLDB, pages 28-39. Morgan Kaufmann, 1996.

36. Philip A. Bernstein and Nathan Goodman. Concurrency control in distributed database systems. ACM Comput. Surv., 13(2): 185-221, 1981.

37. Кантор И.А. Многокритериальные ограниченные сортирующие выборки в реляционных СУБД. Метод деревьев битовых карт. Новые Технологии, 2008.

38. Gurry М. Corrigan P. ORACLE Performance Tuning. 1993.