Содержание к диссертации
Введение
1 Генерация математических задач при помощи модифика ции формальных грамматик 18
1.1 Введение 18
1.2 Функции математического ядра 19
1.3 Обзор существующих математических ядер 20
1.3.1 Полностью раздельное описание задач 21
1.3.2 Подстановка зависимых параметров, основанная на случайном выборе 22
1.3.3 Языки программирования общего назначения . 23
1.3.4 Использование математических пакетов 24
1.4 Применение порождающих грамматик 25
1.4.1 Требования к генератору задач 25
1.4.2 Реализация простейшего примера ах — b 26
1.4.3 Сравнение предлагаемого подхода с существующими 28
1.5 Грамматики с детерминированными правилами 33
1.6 Дерево и граф вывода детерминированной грамматики . 34
1.6.1 Дерево вывода детерминированной грамматики . 34
1.6.2 Граф вывода детерминированной грамматики . 36
1.7 Генерация цепочек с функциональными зависимостями . 41
1.7.1 Обобщенные символы. Объектные грамматики . 41
1.7.2 Отображаемые объекты. Функции грамматики . 42
1.7.3 Грамматика с функциональными зависимостями . 45
1.7.4 Применение грамматик для генерации задач 47
2 Язык описания грамматик 49
2.1 Введение в LogicTask 49
2.1.1 Пример описания семейства задач на LogicTask . 49
2.1.2 Компоненты языка 50
2.2 Грамматика LogicTask - 58
2.2.1 Внешняя грамматика 59
2.2.2 Внутренняя грамматика 60
2.3 Интерпретатор LogicTask . 64
2.3.1 Основные типы объектов 69
2.3.2 Деление объектов по иерархиям 71
2.3.3 Компиляция грамматики 72
2.3.4 Генерация 74
2.3.5 Пример компиляции 74
2.3.6 Структура правил 78
2.3.7 Команды 80
2.3.8 Интерпретация правил 80
3 Многокритериальные ограниченные сортирующие выборки в реляционных базах данных. Метод деревьев битовых карт . 83
3.1 Введение 83
3.2 Задача ограниченной сортированной многокритериальной выборки 86
3.3 Способы решения задачи Q 89
3.3.1 Пересечение битовых карт 89
3.3.2 Сканирование Б-дерсва 90
3.3.3 Геометрические индексы: R*-tiee, kd-tree, X-tree и др. 92
3.3.4 Метод упорядоченных битовых карт 93
3.3.5 Комбинированные методы 94
3.4 Дерево битовых карт 95
3.4.1 Принципы построения индекса 95
3.4.2 Структура индекса 99
3.4.3 Вставка записи в основное дерево поиска 102
3.4.4 Удаление записи 109
3.4.5 Блокировка и одновременный доступ 109
3.4.6 Поиск по дереву битовых карт 110
3.4.7 Размер основного дерева поиска 115
3.4.8 Дополнительные оптимизации 117
3.5 Оценка операций при поиске 120
3.6 Выбор параметра BitmapSize 123
3.6.1 Оптимизация операций ввода-вывода 123
3.6.2 Влияние на стоимость поиска 124
3.6.3 Оценка плотности при равномерном распределении . 125
3.7 Сравнение со сканированием Б-дерева 126
3.8 Сравнительное тестирование 127
3.8.1 Методы поиска 130
3.8.2 Размеры индексных структур 132
3.8.3 Агрегатные результаты 134
3.8.4 Результаты по времени и блокам 135
3.8.5 Дополнение 140
Заключение 140
Приложения 143
Приложение 1 Системы математического обучения 143
Список использованной литературы
- Полностью раздельное описание задач
- Грамматики с детерминированными правилами
- Пример описания семейства задач на LogicTask
- Задача ограниченной сортированной многокритериальной выборки
Введение к работе
Формальные грамматики являются важным инструментом синтаксического анализа и генерации. Они используются для выполнения программ на множестве языков программирования, в молекулярной биологии, в лингвистике и многих других сферах деятельности.
Однако, теоретической базы в виде классификации по Хомскому часто не хватает для полного описания предметной модели. Например, в молекулярной биологии добавляются вероятности, в лингвистике - специальные статистики.
Расширение теоретических основ и рассмотрение новых видов грамматик актуально для применения грамматик в новых областях.
В настоящей работе порождающие грамматики применяются для систем электронного обучения математике.
Современные системы математического обучения предоставляют возможности по обучению и проверке знаний путем решения определенного набора задач. Как правило, набор задач на определенную тему является фиксированным. При пополнении набора задач, составителями описывается условие, решение и ответ для каждой новой задачи.
Такой способ обладает рядом известных недостатков, например:
• небольшое количество вариантов задач, нельзя использовать элементы одной задачи для описания другой.
Актуально создание новых математических моделей для описания задач, которые этих недостатков лишены.
В работе предлагается подход к описанию условия, решение и ответа математических задач в виде цепочек с функциональными зависимостями. Для генерации задач предлагается специализированный язык, на котором описывается порождающая грамматика. Одна грамматика задает семейство задач, решающихся по одной логической схеме.
Процесс генерации нового варианта задачи состоит в получении вывода для соответствующего начального символа порождающей грамматики, причем общее количество различных выводов ограничено только самой грамматикой.
Использование результатов настоящей работы позволяет задавать большое количество (сотни, миллионы..) логически сходных задач с помощью единой порождающей грамматики.
Ни одна из известных систем электронного обучения (MathAid, Angel Learning, "1С Репетитор: Математика", всего рассмотрено 14 различных систем см. в приложении) такого не может 1. Большое количество вариантов задач весьма востребовано при обучении, проведении экзаменационных, тестовых работ.
Правила вывода одной порождающей грамматики могут применяться в часть другой (наследование грамматик /1/). Это позволяет описывать
1 Например, в системе "1С Репетитор: Математика" находится всего около 600 задач, в системе "MathAid" - порядка 1500 задач, по несколько - на каждую тему сложные задачи в виде композиции нескольких подзадач. Такая возможность в существующих системах математического обучения отсутствует.
Можно кратко сформулировать актуальные преимущества использования предлагаемого в работе метода генерации задач как:
1. большое количество вариантов в рамках единой схемы решения,
2. возможность описания сложной задачи как композиции подзадач.
Для систем электронного обучения также актуальны технические возможности:
1. возможность применения в интернет, в браузере,
2. интегрируемость генератора в независимую систему обучения.
Задачу (цепочку) недостаточно генерировать, ее также необходимо хранить. Современные системы обучения требуют хранения вместе с задачами большого количества метаданных: в какому разделу относится задача, среднее время ее решения, процент успешных решений, время последнего предъявления задачи и другую информацию.
Стандартом де-факто для такого хранения являются реляционные базы данных.
При моделировании задачи как цепочки с функциональными зависимостями, ее также можно хранить в реляционной базе данных.
Но объем такой базы, в отличие от традиционных систем, составляет не тысячи, а сотни тысяч, миллионы и более записей. Поэтому актуально создание специализированной индексной структуры. В работе предложено "дерево битовых карт". Ввиду своей эффективности на рассматриваемом классе задач эта индексная структура также весьма востребована в системах с большим объемом многопараметризованных данных, оперирующих в реальном времени.
Если расширить сферу применения поискового алгоритма на произвольные данные, то дерево битовых карт полезно для многокритериальных сортированных выборок с небольшим окном поиска, т.е запросов с сильно варьирующимися ограничениями на поля, результат которых должен быть отсортирован по одному или нескольким фиксированным полям и востребовано лишь небольшое окно, например первые 20 записей.
Такие выборки нужны не только в высоконагружеиных системах, включая:
• интерфейсы по выбору товара, маршрута и т.д в реальном времени,
• системы оптимизации,
• системы принятия решений.
Например, типичная задача такой выборки - нахождение первых 20 самых дешевых предложений в большой базе, причем на параметры искомых предложений накладывается большое количество разнообразных условий.
Сотни условий на параметры накладываются при многокритериальных сортированных выборках также в задачах астрономии /2, 3/.
Высокоэффективная индексная структура особенно актуальна в системах реального времени. То есть, когда на максимальное время выполнения запроса накладываются жесткие временные ограничения. Цель и задачи работы
Основной целью работы является разработка языка описания и алгоритмов генерации и поиска цепочек с функциональными зависимостями, включая создание интерпретатора и генератора математических задач, а также создание и реализацию индексной структуры для поиска по метаданным цепочек в РСУБД.
Новый язык должен обеспечивать следующие основные возможности.
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 году, успешно прошла тестирование для поиска по грамматикам и, кроме того, произведено внедрение новой индексной структуры для подбора предложений по базе туристического агентства "Обновление", подбора жилья в риэлторской компании "Рестро", в ряде других компаний.
Доклады и печатные публикации
Результаты работы, связанные с интеграцией с системами обучения, докладывались на "Международной конференции PHP-разработчиков" в 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/.
Полностью раздельное описание задач
При этом способе описания задач, выделяются изменяющиеся фрагменты в тексте условия/решения/ответа, и описывается класс задач с одинаковым, отличающимся только выделенными фрагментами, текстом. После этого каждая задача описанного класса задается набором значений выделенных фрагментов.
Например, в задачах вида (1.1) обозначим такие фрагменты квадратными скобками [...]. Набор значений фрагментов задает одну задачу. Пример 1.2. Условие с выделенными фрагментами будет иметь вид: Решите уравнение: [а]х = [Ь] Решение задачи: Поделим обе части уравнения на [а]: [а]х — [Ь] -4Ф х — 4 -Ф4 х — [answer]. Ответ: х = [answer].
Два набора значений фрагментов (а, Ь, answer) задают условие и решение для двух разных задач. 1. (2,4,2) -для2ж = 4 2. (3,12, 4) - для Зх = 12
В некоторых системах обучения для обозначения меняющихся фрагментов текста и задания наборов значений используется специальный синтаксис. Например, QQ-язык /17/. При таком способе задания легко добавлять новые задачи. Отсутствует дублирование, связанное с повторением текста. С другой стороны, шаблон задачи задан жестко, и каждая задача так же, как и при раздельном описании, задается отдельно.
Этот способ является естественной эволюцией полностью раздельного описания. При этом подходе создается программа, например, на языке Java или C++, которая реализует алгоритм генерации задачи и схему генерации решения. Так что программа может генерировать обширный класс задач с произвольными а, Ъ N, Є N.
Задание алгоритмов на языке программирования является максимально гибким способом описания. Обширный класс задач задается од ной программой. Возможно разбиение задачи на более мелкие части путем вызова подпрограмм.
Однако, языки программирования — мощный и сложный инструмент, который предоставляет множество ненужных и даже опасных возможностей, по сравнению с рапсе рассмотренными способами описания.
Например, ошибки в описании грамматики на C++ могут привести к сбоям в системе и порче других, не имеющих отношения к дайной грамматике данных.
Кроме того, применение языка программирования высокого уровня требует соответствующей квалификации.
Генерировать задачи можно с использованием математических пакетов, таких как Mathematica, Mapple, и др.
Математический пакет предоставляет собственный язык, предназначенный для математических преобразований, и средства ввода-вывода.
Этот подход не получил широкого распространения, так как язык ориентирован на получение решения, а не на вывод процесса решения. Пакет Mathematica может взять интеграл, но не описать процесс получения ответа.
По-видимому, основная сложность использования математического пакета для описания генерации задач — в том, что приходится использовать средства языка не так, как задумывали его создатели.
Грамматики с детерминированными правилами
Определение 1.5. Помеченное упорядоченное дерево D называется деревом вывода в КС-грамматике G = (VT, VN, Я, S), если выполнены следующие условия: 1. корень дерева D помечен S\ 2. Если Di,...,Dk - поддеревья, над которыми доминируют прямые потомки корня дерева, и корень дерева Di помечен ХІ, ТО S —» Х\... Xk - правило из множества R. Di должно быть деревом вывода в грамматике (VT, VN, R, ХІ), если ХІ - нетерминал, и Di состоит из единственной вершины, помеченной ХІ, если ХІ -терминал;
3. Если корень дерева имеет единственного потомка, помеченного б, то этот потомок образует дерево, состоящее из единственной вершины, и5- б- правило из R.
Пример 1.3. Ниже изображено одно из возможных деревьев вывода для порождающей грамматики из примера а х = Ъ. Все нетерминалы, кроме начального символа, обозначены решеткой "#". Это сделано для удобства работы с порождающей грамматикой, чтобы отличать символ естественного языка от обозначения нетерминала. "s4
Получить сентенциальную форму по дереву вывода можно однозначно — это его крона. С другой стороны, сентенциальная форма как таковая, вообще говоря, не задает однозначного дерева вывода.
Теорема 1.1 (Свойство эквивалентности поддеревьев). В дереве вывода детерминированной грамматики для каждой из левых частей правил все поддеревья вывода одинаковы.
Доказательство. 1. Левая часть правила является нетерминалом. Так как грамматика контекстно-свободная, то вывод не зависит от контекста.
2. С другой стороны, детерминированность грамматики гарантирует, что вывод каждый раз будет следовать только одной альтернативе. Из (1,2) следует, что нетерминал однозначно определяет свое дерево вывода, значит все поддеревья одинаковы. Поэтому в примере (1.3) одинаковы деревья вывода для #6.
Замечание 1.1. Свойство эквивалентности поддеревьев работает лишь в рамках одного, определенного дерева вывода. Оно ни как не связывает между собой различные деревья вывода одной грамматики. Дерево вывода отображается в граф при помощи операции склеивания вершин.
Определение 1.6. Упорядоченный помеченный граф, полученный из упорядоченного помеченного дерева G\ = (А\, R\, fi, g{) путем склеивания множества вершин с одинаковой меткой S — {si,..., sn} в вершину Sk Є S — это граф вида G2 = {А2, R2,/2,92), где 1. А2 получено из А\ удалением всех вершин, составляющих поддеревья с корнями Si Є S, где гфку 2. Множество дуг / получено из R\ заменой всех S{ на Sk в дугах вида (a,Si):a ф S,i ф к и затем удалением всех дуг вида (si,a),Va,i ф к, 3. /г = /і, #2 = 7ъ т-е метки на оставшихся дугах/вершинах сохраняются.
Можно сказать, что склеивание объединяет множество вершин в одну, "переназначая" на нее входящие дуги, и удаляя лишние одинаковые поддеревья. Следствие 1.1. Операция склеивания задает склеивающее отобраснсение G2 = (z(A1),z(Rl),z(f1),gl): которое отображает дерево в граф вывода следующим образом: переводит все вершины из S в одну: z(S) = s, отображает все вершины и дуги поддеревьев с корнями в S \{s} в равное им поддерево с корнем в z(s). отображает дуги входящие в вершины из S - во входящие дуги в вершину z(s).
В определении склеивающего отображения визуально наглядное удаление вершин и ребер заменено на отображение множества вершин/дуг исходного графа в одну вершину/дугу графа-образа отображения.
Определение 1.7. Граф вывода для КС-грамматики - это дерево вывода, в котором для всех одинаковых поддеревьев проведено склеивание корневых вершин.
Теорема 1.2. При склеивании в граф вывода никакие вершины на одном пути не отобразятся в одну вершину графа.
Доказательство. Если вершины Sj, s3 находятся на одном пути, то у них будут разные поддеревья, т.к либо Si находится в поддереве с корнем Sj, либо наоборот. Но склейка применяется к вершинам с одинаковыми под деревьями - противоречие.
С другой стороны, склеивание происходит на всех уровнях, в том числе, возможно и отображение вершин из двух непересекающихся путей в вершины, лежащие на одном пути.
Пример описания семейства задач на LogicTask
В качестве наглядного примера для общего представления о виде языка рассмотрим генерацию условия problem, решения solution и ответа answer для задач на нахождение предела вида: л. sin ах lim —: х-+оо ОХ при случайных значениях а, 6 из промежутка 2,..., 20. problem output { Найдите предел #limit. } limit { Limit [#sin_ax_bx, x- 0] } sin_ax_bx { Sin[#ax]/#bx } ax { #a x } bx { #b x } a { Random[Integer, {2, 20 ] } b { Random[Integer, {2, 20}] } solution output { Произведем замену переменной: {t - #ax}. При этом #xt и, таким образом, #sin_ax_bx = (#xt) = #sin_t_ct.
Число #c можно вынести за знак предела: #limit = #limit_c. Так как {х- 0}, то и {t- 0}. Применяя первый замечательный предел "{HoldForm[Limit[Sin[t]/t,t- 0]=l] , получаем ответ: #answer. } answer {l/#c limit_c { (l/#c) Limit[Sin[t]/t, t- 0] xt { x - t/#a } с { Simplify [#b/#a] ct {#c t} sin_t_ct { Sin[t]/#ct } 2.1.2. Компоненты языка Правило Так как язык задает порождающие грамматики, то первый базовый компонент в нем - правило. Правила объявляются как имя [ тип ] { тело }.
В простейшем случае телом правила является простой текст. Например, правило author rule { Автор - Иванов И.И. } даст при вызове текст "Автор - Иванов И.И.". В следующем примере простой грамматики перечислены правила А, В и С. A rule { test of #В } В rule { new #С call } С rule { 123 }
При запуске порождающей грамматики для нетерминального символа #А — этот символ раскроется в "test of фВ", затем вместо нетерминала фВ будет подставлено тело правила В. Здесь и далее термин "тело правила" аналогичен термину "правая часть правила" в терминологии контекстно-свободных грамматик.
Раскрытие нетерминалов будет идти до тех пор, пока хоть один нетер-, минальный символ, так что в результате останутся лишь отображаемые объекты (в этом примере их нет) и символы естественного алфавита.
Так, результатом порождающей грамматики для правила С является текст "123", для правила В - текст "new 123 call", а для правила А - текст "test of new 123 call".
Если результат работы какого-то правила г - случайное число, то результат первого вызова будет сохранен, и при новых вызовах #т (например, из других правил) — использован снова и снова, без повторной генерации. Таким образом, результат одной и той же логической цепочки можно использовать во многих местах.
Кроме правила типа "rule" существуют специальные виды правил: "output" — для форматированного вывода мат. выражений и "formula", специализированный под предметную область "математика". Тип "formula" устанавливается по умолчанию, если не указан явно. Правило такого типа представляет собой корректное математическое выражение.
Команды и вычисления В правилах могут быть функции грамматики, "команды", которые выделяются тильдой , например: 7/, Case ... Общий синтаксис команд имеет вид: имя команды { аргументы }.
Например, команда математических вычислений вызывается как Eval{...}, и имеет дополнительный сокращенный синтаксис {...}. Ее результатом являются обработка аргумента по правилам языка Mathematica /20/. Общий синтаксис таков: имя команды аргументы . Результат выполнения команды подставляется вместо ее вызова. Команды являются функциями грамматики.
Задача ограниченной сортированной многокритериальной выборки
Здесь и далее используются термины и положения, общепринятые в теории реляционных СУБД и описанные в /32/. Будем рассматривать выборки из отношения(или таблицы) Т с заголовком АЪ N , А2, N ,..., AfieidsCount, N . Элементы множества кортежей (записи) обозначим 71. Каждый триплет кортежа имеет вид Д-, N, vi .
Таким образом, если не оговорено особо, то в таблице находятся Т записей, каждая запись состоит из А = fieldsCount натуральных чисел — значений атрибутов Ai jieidsCount- Упрощенным обозначением кортежа является запись в виде последовательности значений атрибутов: {vi, . . . , VfieidsCount} Выбор натуральных чисел N в качестве домена сделан для простоты рассуждений, которые также применимы ко всем предметным моделям, в которых домен преобразуется к N. Это, например, дата, булевы значения, 32-битные числа с плавающей точкой и т.п. Будем обозначать Vi = [jvi — множество всех значений атрибута Д, Vi GN,Vi.
Определение 3.1. Задачей(или условием задачи) ограниченной сортированной многокритериальной выборки называется упорядоченный набор Q = (Cond, f, с, s, Skip, Count, Тор), где 1. Cond = {СІ(Х),І = 1,...,n} — упорядоченный набор условий (предикатов) равенства и неравенства или нахождения в промежутке 2. / : {Condi,..., Condn} — {0,1} — логическая функция над условиями 3. с — перестановка, которая задает отображение номера Cond на номер атрибута А и, таким образом, привязывает условие к атрибуту. Одному атрибуту может соответствовать несколько условий 4. sGl,...,A — номер атрибута сортировки 5. Skip Є N — число пропускаемых записей 6. Count Є N — размер окна поиска 7. Тор Є N — число максимального предпросмотра
Первые три пункта задают ограничения на поля записи, последние три — ограничение на окно, т.с непрерывное сортированное по As множество записей, которые являются результатом выборки.
Определение 3.2. Запись {vi,... ,Vfieidscount} называется удовлетворяющей критериям задачи, если f(Condi(vc )),..., Condn(vc )) = 1.
Определение 3.3. Полным множеством результатов для задачи Q является множество Results All упорядоченных по атрибуту As записей, удовлетворяющих критериям задачи.
Определение 3.4. Искомым мноснсеством или окном поиска для задачи Q называется упорядоченное множество ResultsWindow: ResultsWindow = (ResultsAllskip+ResultsAllskip+Count) Будем говорить, что окно поиска полное, если ResultsWindow \= Count.
Определение 3.5. Числом предпросмотра для задачи Q называется число CountMore = min( ResultsAll \ —{Skip-\- Count), Top)
Определение 3.6. Решением задачи Q называется упорядоченная пара (Result sWindow, CountMore), где Result sWindow — искомое множество, a CountMore — число предпросмотра.
Наличие чисел Skip, Count, Тор в условии задачи дает возможность организовать постраничный вывод результатов поиска, востребованный в сложных пользовательских интерфейсах.
Можно упростить определение выборки, если объединить эти три числа в одно TotalCount = Skip + Count + Тор, а затем определить искомое множество как (Records Alii,..., RecordsAllm-m(\RecordsAuiTotaiCount)) С одной стороны, из искомого множества такой упрощенной задачи можно получить решение задачи Q, с другой — отдельное выделение Skip и Тор позволяют рассмотреть специальные алгоритмы оптимизации, т.к доступ к данным можно реализовать более эффективно, если важно лишь общее количество, а не атрибуты записей.
Важным частным случаем являются функции, задаваемые в виде без-отрицателыюй КНФ: / = д v Condi к \/і:ф)=к Таким функциям часто соответствуют возможности пользовательских интерфейсов к хранилищам данных.
