Разделы

Счетчики








Глава 5. Структура Q-языка

5.1 Принципы построения Q-языка

5.1.1 Идеология Q

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

В данной модели для постанализа (генерации SQL) не предполагается наличие выходного представления для собственно лингвистического анализа по двум причинам:

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

  • нет четкого разграничения между лингвистическим и пост-лингвистическим анализом в терминах этапов работы Л-процессора: в нашей модели весь анализ предназначен для экспликации риторического содержания запроса, т.е. извлечения информации из БД.

После завершения анализа построенное дерево предикатов и дополнительные признаки используются для генерации Q-представления запроса. В текущей модели предполагается проводить генерацию (как и лингвистический и пост-лингвистический анализ) средствами продукционных правил SNOOPа.

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

Зарплата Петрова (Чья зарплата больше 2000 руб) (инженеры и снс)

“сообщаю”

“запрашиваю”

Риторическая часть запроса “сообщаю” представлена в виде матрицы атрибутов и ограничений на их значения, тип матриц взят из заданной системы категорий ПО (структура этой системы описана в разделе 4 МПО), одним из важных ее признаков является наследование классов:

 

Один из классов этой системы (СОТРУДНИК в нашем примере) задает набор атрибутов объекта запроса (тип матрицы) и возможно некоторые логические условия (например, класс Начальник или Клиент задает особую прагматическую интерпретацию). Определение класса объекта запроса является одной из важных задач пост-анализа; класс объекта запроса определяется на основании следующих условий:

  • объект непосредственно упомянут в запросе (Кто, Какой корабль);

  • в запросе упомянуты атрибуты или значения данного объекта (Зарплата Петрова);

  • контекстного сочетания лингвистических значений (Кого обслужил Петров vs. Кто обслужил Петрова).

Недоопределенное описание этого объекта состоит из логических выражений, ограничивающих диапазон значений этих атрибутов, а также задающих принадлежность объекта некоторому множеству, в частности, полученному в результате вложенного запроса. Логические выражения состоят из имени атрибута, отношения и значения. Отношения включают в себя отношения сравнения (=, <, …) и принадлежности (ХÎ списку, интервалу или множеству, ХÊ текстовое значение). Логические выражения могут соединяться связками И, ИЛИ, НЕ (список строк матрицы соответствует по умолчанию И). Логические выражения в Q и связки между ними строятся из предикатов и соответствующих связок дерева, построенного в ходе лингвистического анализа.

Атрибуты логических выражений соответствуют классу объекта запроса. К значениям относятся понятия онтологии, строковые и арифметические выражения, списки и интервалы. Арифметическое выражение может сопровождаться указанием единицы измерения (руб в примере выше). Понятия онтологии соответствуют тому, что является гиперзначением в IB/Dos (отношение общее-частное в SQL переводится в дизъюнкцию частных). Атрибуты и их значения являются составляющими предикатов дерева анализа, помимо этого возможны процедуры нормализации этого дерева, приводящие к соединению значений в интервалы (так, запросы вида Вечерние электрички от Выхино не позже 22.00 с точки зрения лингвистического дерева составляют два предиката, которые могут быть объединены в один интервал в Q).

Для множества объектов, отождествленных с недоопределенным объектом запроса, производится операция, заданная в части “запрашиваю” Q-запроса. В регистре запросов к БД возможно два вида таких операций: предъявление этих объектов пользователю и отображение этого множества в значение. В первом случае предъявление основывается на наборе идентифицирующих атрибутов данной категории (это задано в МПО), а также импликациях из присутствия в запросе атрибутов, отношений или значений (о чем спрашивается в запросе). Группа атрибутов может быть объединена в гиператрибут. При порождении списка отображаемых атрибутов часть из них берется непосредственно из списка несвязанных атрибутов запроса (Зарплата Петрова), часть — из атрибутов, связанных в предикатах (Сотрудники с зарплатой большей 2000), часть — из списка идентифицирующих атрибутов данного объекта. В последнем случае конструктор задает набор правил отображения, например: для сотрудника всегда отображается фамилия, если задается отображение зарплаты, то отображается и должность; если задается отображение комнаты, то отображается и телефон. В интерфейсе должна также существовать возможность отображения всех атрибутов найденного объекта.

Во втором случае выполняется некоторая операция отображения множества объектов в числовое значение (функторы):

У кого из снс со стажем больше 15 лет максимальная зарплата?

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

Функторы всегда непосредственно упомянуты в запросе; определение их значения (см. описание системы значений Сколько) является задачей лингвистического анализа (лексическое выражение максимума и минимума через минимальный/максимальный или аналитическое самый высокий). Некоторые классы объектов функционируют в таком качестве только в функторных запросах (например, страна в Сколько стран имеют фрегаты, в других случаях это атрибут класса КОРАБЛЬ). Стандартный набор значений функторов: MIN, MAX, AVG, SUM, COUNT,.

 

5.1.2 Структура Q-запроса, общие принципы

5.1.2.1 Составляющие запроса

В запросе присутствуют следующие составляющие:

  • Класс выдаваемых объектов, называемый объектом запроса.

  • Условия отбора объектов.

  • Состав выдаваемой информации об объектах (атрибуты, агрегатные функции типа min, max).

  • Указание порядка сортировки выдаваемого результата (необязательно) и ограничение на количество отбираемых объектов, например, первые пять (необязательно).

  • Требование группировки результата по некоторым атрибутам, относящимся к выдаваемым объектам (необязательно) и фильтр на выдаваемые группы (необязательно).

5.1.2.2 Примеры представления запроса

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

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

ЕЯ:

list all the products in bottles that cost less than 5$;

Q:

OQL:

select p.price, p.name, p.measure_unit
from Product p
where price<=5{$}
and measure_unit='bottle'

Q-дерево:

5.1.2.3 Q-дерево

Приведенный выше пример содержит представление запроса в виде дерева. Узлы этого дерева являются компонентами, или классами (в понятиях SNOOP). Набор компонентов, участвующих в Q, частично пересекается с набором компонентов, участвующих в МПО (Класс, Атрибут, Множество и пр.).

Корневым узлом всегда является узел Запрос. К нему относятся узлы Выдаваемая информация, Объект запроса, Условия (обязательные), а также необязательные узлы Сортировка, Ограничение кол-ва, Группировка.

К узлу Выдаваемая информация могут подсоединяться узлы-атрибуты, аггрегатные функции (min, max, ...) и т.д.. Узел Объект запроса задает класс объектов, к которому применяются условия, заданные узлом Условия и связанными с ним. В Условия входят наследники узла Предикат. Выдаваемый результат сортируется исходя из узлов - наследников класса Выражения, которые содержит узел Сортировка.

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

В целом структура Q-запроса повторяет структуру SQL-запроса. Часть классов узлов прямо отображается на ключевые слова SQL и OQL:

Узел (руское название)

Имя класса SNOOP

Ключевые слова SQL (OQL)

Выдаваемая информация

Get

select

Объект запроса

QObject

from

Условия

Conds

where

Сортировка

Sort

sort by

Группировка

Group

group by

Фильтр групп

GroupFilter

having

 

5.1.2.4 Представление Q-дерева в сети SNOOP

Q-дерево строится при выполнении продукционной программы в SNOOP, при этом оно представляет собой сеть с некоторыми ограничениями. Узлы в этой сети связываются в основном двумя классами отношений - одно выражает зависимость (depend), второе - порядок следования равноправных узлов (follow). Построенная таким образом сеть может быть по завершению анализа записана в виде дерева, отношения follow исчезают, определяя порядок равноправных узлов дерева.

Кроме этих двух отношений, применяются accessor, связывающее атрибуты аксессорной цепочки, и measure, связывающее выражение с единицей измерения.

5.1.2.5 Иерархия узлов Q-дерева

Классы узлов в Q-дереве образуют иерархию наследования. Например, класс Предикат является предком для Сравнение, от Выражения наследуются Аксессор, Значение, Функтор и т.д. Иерархия вводится для использования в продукционной программе правил, абстрагирующихся от несущественных для данного правила деталей (например, все предикаты равноправны по отношению к классу Условия). Часть классов фактически являются абстрактными - в Q-дереве присутствуют только их предки. Абстрактые классы - Предикат, Выражение, Множество, Атрибут, Аксессор.

Предикат

Выражение

Атрибут

Запрос

Список

Множество

APredicate

Compare

InOSet

InVSet

Exists

ForAll

Or

And

Not

AExpr

Val

Aggr

VQuery

Expr

AAttr

AAttr

Attr

CAttr

GAttr

OAttr

AQuery

Query

VQuery

LQuery

SQuery

AList

List

LQuery

ASet

Set

SQuery

Intersect

Union

Except

Из таблицы видно, что в иерархии применяется множественное наследование: например, для класса LQuery (запрос-список) предками является список AList и запрос AQuery.

5.1.2.6 Аксессоры

Аксессор выражает связку элементов МПО, обозначающую атрибут, связанный с объектом опосредованно через другие объекты. При этом эта цепочка записывается синтаксически как названия компонент через точку: Объект1.Атрибут1.Объект2.Атрибут2.Объект3.Атрибут3. Для сокращения и устранения избыточности этой конструкции допустимо в цепочке Атрибут1.Объект.Атрибут2 пропускать элемент Объект, так как каждое отношение, связывающее другие классы с данным классом, имеет уникальное для данного класса название. Таким образом, "навигация" от одного класса к другому может задаваться только атрибутами: Объект1.Атрибут1.Атрибут2.Атрибут3.

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

С точки зрения структуры Q-дерева аксессор представляет собой "вертикальную" цепочку, состоящую из атрибутов, связанных отношением accessor. Верхним является крайний правый атрибут в аксессоре. Хотя в синтаксисе аксессора на первом месте стоит всегда название класса, структурно началом аксессорной цепочки считается класс главного объекта запроса (QObject), который всегда связан с узлом Query; атрибуты в дереве запроса не связаны с узлом QObject непосредственно.

Пример:

ЕЯ:

Who ordered beer?

Q:

OQL:

Select c.orders.products, c.name
from Customer c
where c.orders.products in Beer

Q-дерево:

Примечание:

в этом примере в OQL и Q-дереве участвует предикат "принадлежит множеству" - Beer - определенное в МПО множество объектов (продукты, у которых названия принадлежат некоторому списку имен сортов пива).

5.1.2.7 Вложенные запросы

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

Вложенный запрос-множество (OSetQuery) возвращает множество объектов, он может входить в предикаты, работающие со множествами (InOSet, Exists, ForAll), а также подчиняться узлам-операторам множеств (Intersect, Union, Except).

Вложенный запрос-список (VSetQuery) возвращает список простых значений. Он может участвовать в предикатах работы со списками (InVSet).

Вложенный запрос-значение (VQuery) возвращает одно простое значение. Он может присутствовать во всех местах Q-дерева, где допустимо использование узла-значения (Value).

5.1.2.8 Использование предопределенных множеств и списков

Описываемая модель предполагает использовать в запросах предварительно определенные в МПО объектные множества (OSet) и множества значений (VSet).

Множество задается как запрос, возвращающий множество объектов (OSetQuery). То есть в МПО этот узел связан с деревом запроса. Таким способом может решаться проблема толкований - пользователь вводит определение множества на ЕЯ, которое переводится в Q-дерево и в таком виде хранится в МПО.

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

5.2 Состав классов узлов Q-дерева

5.2.1 Запрос: AQuery, Query, VQuery, VSetQuery, OSetQuery

От абстрактного класса AQuery наследуется четыре класса запросов - верхнего уровня Query, и вложенные запросы VQuery, VSetQuery и OSetQuery. VQuery выражает вложенный запрос, возвращающий при ответе простое значение, VSetQuery выражает вложенный запрос, возвращающий при ответе список простых значений, OSetQuery - вложенный запрос, возвращающий при ответе множество объектов.

Любой наследник AQuery должен содержать подчиненные узлы Get, QObject, Conds, и опционально - Order, Group, GroupFilter, Top (Bottom).

5.2.2 Выдаваемая информация: Get

Обязательная часть запроса - этот узел подчинен наследникам AQuery. В подчинении этому узлу могут быть наследники AExpr, наследники AObject, гиператрибуты (GAttr). Все эти узлы должны относиться к классу, заданному MainClass. Например, аксессоры должны иметь TheClass с именем, заданным главным классом, в качестве начального элемента в цепочке.

5.2.3 Объект запроса: QObject

Является обязательным подчиненным узлом для классов-наследников AQuery.

5.2.4 Выражения: AExpr, Expr, Value, Aggr, VQuery, AAttr

Выражения имеют типы простых значений. Value - простое значение (числовое, строковое, логическое и пр.). Aggr представляет аггрегатную функцию (min, max, count, sum, avg). Aggr связывается с атрибутом. Если значение Aggr - count, то Aggr может быть не связан с атрибутами - выдается количество объектов в выдаваемом множестве.

Наследниками выражения являются также атрибуты.

5.2.5 Атрибуты: AAttr, Attr, CAttr, GAttr

Атрибуты (наследники AAttr) могут быть простыми (Attr), вычисляемыми (CAttr), гиператрибуты (GAttr).

5.2.6 Единицы измерения: MUnit

Этот класс узлов может быть привязан к выражениям (связью measure).

5.2.7 Предикаты: APredicate, Comparе, InSet, InList, Exists, ForAll, Or, And, Not

Предикаты имеют логический тип. APredicate - абстрактый класс. Compare - сравнение. В нем указывается название оператора сравнения в качестве строкового поля (>,<,=,<>,<=,>=, like). InSet - предикат принадлежности объекта множеству. InList - принадлежности (атрибута или выражения) списку. Exists - предикат наличия в множестве объекта с заданными свойствами. ForAll - предикат, определяющий истинность того, что все объекты множества обладают заданными свойствами. Or, And, Not здесь условно отнесены к предикатам, они объединяют другие предикаты в условия.

5.2.8 Множества: ASet, Set, SQuery, Intersect, Union, Except

Множества наследуются от абстрактного предка ASet. Set является именованным множеством, он должен быть определен в сети МПО. Предполагается, что Set будет определяться в виде SQuery. SQuery является вложенным запросом, возвращающим множество объектов как результат. Intersect, Union, Except - операторы над множествами (пересечение, объединение и вычитание соответственно). Операторы содержат другие узлы-множества в подчинении.

5.2.9 Списки: AList, LQuery, List

Списки наследуются от абстрактного предка AList. Список значений может появиться как результат вложенного запроса (LQuery), либо он может быть определен в МПО (List) - перечислением элементов списка или как результат запроса LQuery.

5.2.10 Сортировка: Sort

Узел Sort указывает порядок сортировки. Связан с узлом запроса. Необязателен. К нему привязаны узлы-выражения.

5.2.11 Ограничение кол-ва: ALimit, Top, Bottom

Узлы-наследники абстрактного ALimit позволяют ограничивать результат запроса сверху (Top) или снизу (Bottom) заданием определенного кол-ва выдаваемых объектов, либо процентом от всего количества объектов, удовлетворяющим условиям. Используются только при наличии в запросе узла Sort.

5.2.12 Группировка: Group, GroupFilter

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

Предназначение GroupFilter аналогично ключевому слову having в SQL-запросе. К нему "подвешивается" узел Conds, к нему, в свою очередь - предикаты, ограничивающие полученные группы.

Источник: http://www.aha.ru/~zhigalov/science/disser/disser.htm (Компьютерный диалог)
Дополнительно
Дисертация Владислава Жигалова
http://www.aha.ru/~zhigalov/science/disser.zip - Word'97 (zip - 336k)