Найханова Л.С. Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL запросы
Подождите немного. Документ загружается.
61
утверждает, что концепт понятия контактные данные составляют понятия z
1
, z
2
, z
3
∈Ξ
l
(телефон, факс, e-mail);
- P
s
(x, y, r(verb),t(z
1
, …,z
k
),
r
fun
t ), - предикат, задающий отношение номинации между
понятием х и тремя следующими аргументами предиката y, r(verb), ),...,(
1 k
zzt . При этом
r(verb) задает функциональное отношение между понятием y и термом ),...,(
1 k
zzt
посредством глагола verb. Глагол определяет смысл между понятием y и понятиями
естественного языка
k
zz ,...,
1
, которые могут принадлежать множеству терминов логической
модели данных z
i
∈Ξ
l
или множеству понятий, релевантных проблемной среде z
j
∈Ξ
s
.
Например, предикат
)),(),(,,(
r
noms
tпризнаксоциальныйtиметьrстудентльготникP
утверждает, что
концепт понятия льготник определяется через понятие студент и понятие студент имеет
свойство «социальный признак»;
-
),,(
r
tips
tyxP - предикат, задающий отношение типизации
r
tip
t , например, предикат
),,(
r
tips
tоперациябольшеP утверждает, что термин больше∈Ξ
s
и является операцией оператора
SQL, а предикат
),,(
r
tips
tпроцедураьнаявычислителсреднийP утверждает, что термин
средний
∈Ξ
s
является вычислительной процедурой оператора SQL;
- ),,(
r
trs
tyxP - предикат, задающий отношение перевода
r
tr
t , например, предикат
),,(
r
trs
tбольшеP >
утверждает, что термин больше соответствует логической операции «>»,а
предикат ),,(
r
trs
tselectвыдатьP утверждает, что термин выдать соответствует операнду
Select оператора языка запросов SQL;
- P
s
(x, t(z
1
, …,z
k
),
r
agr
t ), - предикат, задающий отношение агрегации
r
agr
t между
понятием - атрибутом логической модели данных х∈Ξ
l
и термом ),...,(
1 k
zzt . Вектор
значений ),...,(
1 k
zz определяет объем понятия х. Например: предикат P
s
(социальный
признак, t(сирота, инвалид 1 группы, инвалид 2 группы, инвалид 3 группы, из многодетной
семьи, участник ликвидации аварии Чернобыльской АЭС, участник войны в Афганистане,
участник войны в Чечне, мать-одиночка), t
r
agr
) утверждает, что понятия сирота, инвалид и
т.д. составляют объем понятия социальный признак∈Ξ
l
.
Таким образом, знания проблемной среды можно разделить на четыре основные
группы:
- первая группа включает в себя знания об определениях терминов логической
модели данных и понятий естественного языка, релевантных проблемной среде, которые
описываются предикатами отношения номинации вида: P
s
(x, y, r(verb),t(z
1
, …,z
k
),
r
fun
t ) и
P
s
(x, t(z
1
, …,z
k
),
r
nom
t ), а также предикатами, задающими отношение агрегации P
s
(x,t(z
1
,.,z
k
),
r
agr
t );
- вторая группа знаний включает в себя специальные знания проблемной среды,
которые описываются предикатами типизации
),,(
r
tips
tyxP и перевода
),,(
r
trs
tyxP
;
- третья группа знаний включает в себя знания о синонимах терминов логической
модели данных и понятий естественного языка, релевантных проблемной среде, которым
соответствуют предикаты с отношениями тождества вида
),,(
r
tgs
tyxP
или
62
)),,...,(),,...,((
11
r
tgkns
tyytxxtP
и подобия
),,(
r
ans
tyxP
;
- четвертая группа знаний включает в себя знания, составляющие базовую модель
и не относящиеся к проблемной среде. К этой группе знаний относятся предикаты
),,(
r
ans
tyxP
, задающие отношение подобия между понятиями-синонимами, которые не
являются терминами логической модели данных.
Предикаты проблемной среды приведены в Приложении Г.
3.2. Базовые механизмы проблемного анализа
Таким образом, представленное формальное описание лингвистического обеспечения
определяет множество базовых объектов формальной системы транслятора, которые
впоследствии составят множество Г при доказательстве различных утверждений для
построения SQL – запроса. Анализ графа зависимостей G позволит построить граф
G
~
гомеоморфного исходному, вершины которого будут содержать термины физической
модели данных. Построение гомеоморфного графа зависимостей будем выполнять в две
стадии. На первой стадии построим граф
G
′
~
, выполнив анализ каждой вершины g∈G и
определив её принадлежность терминам логической модели данных
l
t Ξ∈
. Термины t
запишем в вершины
Gg
′
∈
′
~
~
и сформируем для вершин вектор
η
. На второй стадии
преобразуем граф
G
′
~
в граф
G
~
путем исключения дублирующихся вершин и заменой
терминов логической модели данных
l
t Ξ∈
на термины физической модели
f
t Ξ∈
.
3.2.1. Метод построения преобразования
3
Ψ
Построим граф G
′
~
, гомеоморфный графу G, затем преобразуем его в граф G
~
.
Для построения графа
G
′
~
необходимо найти транзитивное замыкание преобразований
вершин
gg
′
→
~
*
, где g∈G, Ξ
′
∈
′
,
~
~
Gg ,
fl
Ξ
∪
Ξ
=
Ξ
, G
′
~
- граф, гомеоморфный исходному G.
Если транзитивное замыкание не найдено, то это соответствует ситуации, которая означает,
что вершина несет в себе вспомогательную информацию для формирования SQL-запроса.
Длина транзитивного замыкания может быть равна или больше единицы. Первый
случай соответствует ситуации, в которой существует прямое соответствие между
вершиной g и термином
Ξ∈
′
g
~
. Во втором случае возможны ситуации, когда запросы могут
содержать не прямое соответствие с терминами логической модели, а косвенное. При
косвенном соответствии они могут выражаться через синонимы или через другие понятия
проблемной среды, описываемые множеством Ξ
s
.
В процессе первичного анализа графа зависимостей построим вектор
η
для каждой
вершины графа, который будет содержать необходимые для трансляции свойства вершин.
Определим вектор
η
следующим кортежем:
η
=<z
1
, z
2
, z
3
>,
где z
1
- признак, определяющий принадлежность множеству терминов логической
модели данных Ξ
l
;
z
2
- тип вершины g
′
~
: 1 – атрибут логической модели данных, 2 - сущность логической
модели данных, 3–операнд оператора SQL, 4- операция оператора SQL, 5 - вычислительная
процедура, 6 - значение атрибута базы данных;
z
3
- тип признака понятия для атрибута логической модели данных (d-
63
дифференциальный, h-характеристический, v-валентный) или null в случае, если вершина
является сущностью.
3.2.1.1. Построение транзитивных замыканий
При решении данной задачи может существовать три гипотезы о соответствии лексем
запроса понятиям базы данных или проблемной среды. Можно утверждать, что лексема
запроса g∈G может быть:
1) специальным понятием проблемной среды;
2) термином логической модели данных t∈ Ξ
l
;
3) понятием проблемной среды t∈ Ξ
s
.
Построение транзитивного замыкания
gg
′
→
~
*
выполним последовательно для
каждой гипотезы, задавая исходную ситуацию, которой описывается одна вершина g∈G.
Для доказательства каждой гипотезы сформируем множество предикатов
Γ
, на котором
будем доказывать утверждение, описывающее входную ситуацию d
0
. Если в результате
текущего доказательства получаем неуспех, то переходим к доказательству следующей
гипотезы.
Доказательство первой гипотезы. Эта гипотеза предполагает, что лексема в
вершине g является специальным понятием проблемной среды. Для её доказательства во
множество
Γ
включим предикаты, задающие отношение типизации
r
tip
t
, и докажем
выражение
0
d∧Γ методом линейной резолюции. Входную ситуацию опишем предикатом:
d
0
= ),,(
r
tips
tyxP . Если доказательство пройдет успешно, то в вершину g
′
~
, соответствующую
вершине g, заносится оператор, операнд или вычислительная процедура языка SQL,
согласно отношению перевода
r
tr
t , а в z
2
– значение «3», «4» или «5» соответственно. Затем
перейдем к рассмотрению следующей вершины графа G. В случае неуспеха, полученного
при доказательстве построенной формулы, доказывается вторая гипотеза.
Доказательство второй гипотезы. В этом случае g является термином логической
модели данных. Поэтому вершине приписывается соответствующий признак, который
определяет тип термина (атрибут или сущность).
Входная ситуация, описывающая текущую вершину дерева G, имеет следующий вид:
d
0
= ),,(
r
tips
tyxP , например,
d
0
=
),,(
r
tips
tyстудентP
(3.5)
или
d
0
= ),,(
r
tips
tyпереченьP .
(3.6)
В этом случае множество предикатов
Γ
формируется из предикатов типизации,
описывающих логическую модель данных (3.2) и (3.3), например:
Γ
={
),,(
r
tips
tатрибутфамилияP
,
),,(
r
tips
tсущностьстудентP
,…,
),,(
r
tips
tсущностьстьспециальноP
, …, ),,(
r
tips
tсущностьгруппаP ,…,
),),,((
r
tips
tатрибутдомашнийтелефонtP }.
На данном множестве
Γ
факт (3.5) будет доказан успешно, поэтому осуществится
переход к анализу следующей вершины графа
G
′
′
. При доказательстве факта (3.6) получим
64
неуспех и перейдем к доказательству следующей гипотезы.
Доказательство третьей гипотезы. Предположение о том, что вершина g∈G
является понятием проблемной среды t∈Ξ
s
, порождает четыре дополнительные гипотезы.
Поэтому основные три гипотезы будем называть гипотезами верхнего уровня, а
дополнительные – гипотезами нижнего уровня, к которым относятся предположения, что:
1) лексема является понятием, тождественным некоторому термину логической
модели данных;
2) лексема является частью агрегированного или видом обобщенного понятия;
3) лексема является составной частью определения некоторого понятия;
4) лексема является синонимом некоторого термина логической модели данных или
понятия естественного языка, релевантного проблемной среде.
При доказательстве гипотез нижнего уровня во множество
Γ
включим предикаты
проблемной среды. Первая гипотеза нижнего уровня доказывается аналогично
доказательствам, описанным выше. Множество
Γ
в этом случае включает в себя все
предикаты, описывающие отношение тождества
r
tg
t . Если доказательство прошло успешно,
то осуществляется переход на доказательство второй гипотезы верхнего уровня.
Вторая гипотеза нижнего уровня говорит о том, что лексема в вершине графа
является значением атрибута базы данных, который является обобщенным или
агрегированным понятием. Множество
Γ
в этом случае составляют предикаты с
отношениями агрегации
r
agr
t
и обобщения
r
ob
t . Если доказательство прошло успешно, то в
элемент z
2
вектора
η
вершины g записывается значение «6», которое указывает, что
понятие является значением базы данных, а перед вершиной g добавляется новая вершина
g
′
~
. В добавленную вершину g
′
~
записывается агрегированное или обобщенное понятие
логической модели данных. Для доказательства корректности проверяется вторая гипотеза
верхнего уровня.
Третья гипотеза нижнего уровня утверждает, что лексема является составной частью
определения некоторого понятия. Для её доказательства формируется множество
Γ
,
состоящее из предикатов с отношениями номинации
r
nom
t . Если доказательство прошло
успешно, то осуществляется запись в
g
′
~
аргумента y предиката P
s
(x, y, r(verb),t(z
1
, …,z
k
),
r
nom
t ) и добавляется k g
′
~
вершин ниже текущей, в которые записываются значения k
аргументов терма t(z
1
, …,z
k
) и осуществляется, как в предыдущих двух случаях, переход на
доказательство второй гипотезы верхнего уровня. Таким образом, длина транзитивного
замыкания при доказательстве первой, второй и третьей гипотез нижнего уровня равна
двум.
Если первые три гипотезы нижнего уровня потерпели неудачу, то доказывается
четвертая, которая имеет итеративный характер. Многошаговость построения
транзитивного замыкания
gg
~
*
→ заключается в последовательном переборе всех
синонимов для лексемы, находящейся в текущей вершине g. Для поиска синонима
формируется множество
Γ
, состоящее из предикатов с отношениями подобия
r
an
t . Для
каждого синонима доказываются первые две гипотезы верхнего уровня, а в случае
неуспеха – первые три гипотезы нижнего уровня третьей гипотезы. Доказательство
продолжается до тех пор, пока одна из гипотез не окажется истинной или пока не будет
65
перебран весь список синонимов текущей лексемы.
Граф
G
′
~
, полученный в результате доказательства гипотез, будет гомеоморфен графу
G и будет содержать в вершинах термины логической модели данных или термины языка
SQL, с приписанными к каждой вершине
g
′
~
векторами η.
3.2.1.2. Описание системы продукций
Доказательство гипотез связано с проверкой условий применимости каждой
отдельной гипотезы. Для удобства разобьем все множество предикатов Г на подмножества,
которые будут использоваться в процедуре доказательства вышеописанных гипотез.
1. Подмножество Г
1
включает в себя множество предикатов типизации и перевода,
составляющих вторую группу знаний проблемной среды.
2. Подмножество Г
2
включает в себя множество предикатов типизации,
составляющих первую группу знаний метаописания базы данных.
3. Для доказательства третьей гипотезы формируются следующие подмножества:
а) подмножество Г
3
- множество предикатов тождества, входящих в состав
третьей группы знаний проблемной среды;
b) подмножество Г
4
- множество предикатов агрегации первой группы знаний
проблемной среды;
с) подмножество Г
5
- множество предикатов номинации первой группы знаний
проблемной среды;
d) подмножество Г
6
- множество предикатов, задающих отношение подобия,
третьей и четвертой групп знаний проблемной среды.
Система продукций формирования графа
G
′
~
, гомеоморфного графу G, включает в
себя множество продукций трансляции
{
}
13,1Pr
1
== ipr
Tr
i
tr
, которые проверяются при
доказательстве описанных выше гипотез.
Система продукций для доказательства первой гипотезы
Доказательство первой гипотезы связано с проверкой условий применимости
продукций
TrTrTr
prprpr
321
,, . Для доказательства предположения, что лексема в вершине g
является специальным понятием проблемной среды, формируется множество
i
q
∧
Γ
=
Γ
′
11
=
{
),,(
r
tips
tyxP }∧{),,(
r
trs
tyxP }∧q
i
, где q
i
∈pr
i
( 3,1=i ) - условие применимости. Методом
линейной резолюции доказывается выражение
01
dГ ∧ , где d
0
задается предикатом вида
),,(
r
tipis
tyxP , в котором х
i
– понятие, находящееся в вершине g.
При доказательстве первой гипотезы рассмотрим три ситуации, которые зависят от
значения элемента z
2
вектора
η
.
Первая ситуация. Лексема x
i
является операндом, имеет вектор
η
i
с элементами z
1
, z
2
,
z
3
и ее можно заменить на соответствующее понятие из множества специальных понятий
проблемной среды тогда и только тогда, когда имеет место закономерность, описываемая
конъюнкцией следующих фактов:
1) лексема x
i
находится в отношении типизации с понятием y
1
- P
S
(x
i
, y
1
, t
r
tip
);
2) понятие y
1
имеет значение «операнд» - P
E
(y
1
, операнд);
3) лексема x
i
находится в отношении перевода с понятием y
2
- P
S
(x
i
, y
2
, t
r
tr
).
Утверждению о том, что существует лексема x
i
, которая находится в отношении
66
типизации с понятием «операнд» и имеет вектор
η
i
с элементами z
1
, z
2
, z
3
, соответствуют
предикаты: ( ∃ x
i
:Х) P
S
(x
i
, операнд, t
r
tip
) и P
par
(η
i
, t(z
1
, Null), t(z
2
, 3), t(z
3
, Null)).
В этом случае элементы pr
1
Tr
продукции записываются в виде:
q
1
Tr
= P
S
(x
i
, y
1
, t
r
tip
)
∧
P
E
(y
1
, операнд)
∧
P
S
(x
i
, y
2
, t
r
tr
)↔ (
∃
x
i
:Х) P
S
(x
i
, операнд, t
r
tip
)
∧
P
par
(η
i
, t(z
1
, Null), t(z
2
, 3), t(z
3
, Null));
r
1
Tr
= add[(P
par
(η
i
, t(z
1
, Null), t(z
2
, 3), t(z
3
, Null))
∧
(
i
g
′
~
, y
2
)].
Вторая ситуация. Лексема x
i
является операцией, имеет вектор
η
i
с элементами z
1
, z
2
,
z
3
и её можно заменить на соответствующее понятие из множества специальных понятий
проблемной среды тогда и только тогда, когда имеет место закономерность, описываемая
конъюнкцией следующих фактов:
- лексема x
i
находится в отношении типизации с понятием y
1
- P
S
(x
i
, y
1
, t
r
tip
);
- понятие y
1
имеет значение «операция» - P
E
(y
1
, операция);
- лексема x
i
находится в отношении перевода с понятием y
2
- P
S
(x
i
, y
2
, t
r
tr
).
Утверждению о том, что существует лексема x
i
, которая находится в отношении
типизации с понятием «операция» и имеет вектор
η
i
с элементами z
1
, z
2
, z
3
, соответствуют
предикаты: (
∃ x
i
:Х)P
S
(x
i
, операция, t
r
tip
) и P
par
(η
i
, t(z
1
, Null), t(z
2
, 4), t(z
3
, Null)).
Элементы продукции pr
2
Tr
записываются в виде:
q
2
Tr
= P
S
(x
i
, y
1
, t
r
tip
)
∧
P
E
(y
1
, операция)
∧
P
S
(x
i
, y
2
, t
r
tr
)↔ (
∃
x
i
:Х) P
S
(x
i
, операция, t
r
tip
)
∧
P
par
(η
i
, t(z
1
, Null), t(z
2
, 4), t(z
3
, Null));
r
2
Tr
= add[(P
par
(η
i
, t(z
1
, Null), t(z
2
, 4), t(z
3
, Null))
∧
(
i
g
′
~
, y
2
)].
Третья ситуация. Лексема x
i
является вычислительной процедурой, имеет вектор
η
i
с
элементами z
1
, z
2
, z
3
и ее можно заменить на соответствующее понятие из множества
специальных понятий проблемной среды тогда и только тогда, когда имеет место
закономерность, описываемая конъюнкцией следующих фактов:
- лексема x
i
находится в отношении типизации с понятием y
1
- P
S
(x
i
, y
1
, t
r
tip
);
- понятие y
1
имеет значение «вычислительная процедура» - P
S
(x
i
, y
1
, t
r
tip
); P
E
(y
1
,
вычислительная процедура);
- лексема x
i
находится в отношении перевода с понятием y
2
- P
S
(x
i
, y
2
, t
r
tr
).
В данном случае утверждение описывается продукцией pr
3
Tr
:
q
3
Tr
= P
S
(x
i
, y
1
, t
r
tip
) ∧ P
E
(y
1
, вычислительная процедура)
∧
P
S
(x
i
, y
2
, t
r
tr
)↔ ( ∃ x
i
:Х) P
S
(x
i
,
вычислительная процедура, t
r
tip
)
∧
P
par
(η
i
, t(z
1
, Null), t(z
2
, 5), t(z
3
, Null));
r
3
Tr
= add[(P
par
(η
i
, t(z
1
, Null), t(z
2
, 5), t(z
3
, Null))
∧
(
i
g
′
~
, y
2
)].
Таким образом, в случае успешного доказательства первой гипотезы в вершину
i
g
′
~
,
соответствующую вершине g
i
,
будет занесено понятие y
2
из множества специальных
понятий проблемной среды y
2
∈Ξ
s
и сформирован соответствующий ей вектор η
i
.
Система продукций для доказательства второй гипотезы
При доказательстве второй гипотезы необходимо рассмотреть две ситуации. Первая
ситуация касается случая, когда вершина g является сущностью. Вторая ситуация – когда
вершина g является атрибутом логической модели данных. При этом множество
предикатов Г включает в себя подмножество предикатов типизации Г
2
и условие
применимости q
i
∈pr
i
( 5,4=i ), т.е.
Γ
= Г
2
∧
q
i
= { ),,(
r
tips
tyxP }∧{ ),),,...,((
1
r
tipks
tyxxtP }∧
q
i
.
Доказательство осуществляется аналогично доказательству предыдущей гипотезы, а
67
входная ситуация d
0
задается в виде:
d
0
= ),,(
r
tipis
tyxP ∨ ),),((
r
tipis
tyxtP .
(3.7)
Рассмотрим подробнее возможные ситуации для второй гипотезы.
Первая ситуация. Лексема x
i
является сущностью и имеет вектор
η
i
с элементами z
1
,
z
2
, z
3
тогда и только тогда, когда имеет место следующая конъюнкция фактов:
- лексема x
i
находится в отношении типизации с понятием y
1
- P
S
(x
i
, y
1
, t
r
tip
) или
P
S
(t(x
i
), y
1
, t
r
tip
);
- понятие y
1
имеет значение «сущность» - P
E
(y
1
, сущность).
Тогда элементы продукции можно представить в виде pr
4
Tr
:
q
4
Tr
= (P
S
(x
i
, y
1
, t
r
tip
) ∨ P
S
(t(x
i
), y
1
, t
r
tip
))
∧
P
E
(y
1
, сущность) ↔ (∃ x
i
:Х) P
S
(x
i
, сущность,
t
r
tip
) ∧ P
par
(η
i
, t(z
1
, 1), t(z
2
, 2), t(z
3
, null));
r
4
Tr
= add[P
par
(η
i
, t(z
1
, 1), t(z
2
, 2), t(z
3
, null))].
Вторая ситуация. Лексема x
i
является характеристическим атрибутом и имеет вектор
η
i
с элементами z
1
, z
2
, z
3
тогда и только тогда, когда имеют место ситуации, составляющие
следующую конъюнкцию фактов:
- лексема x
i
находится в отношении типизации с понятием y
1
(P
S
(x
i
, y
1
, t
r
tip
) или
P
S
(t(x
i
), y
1
, t
r
tip
));
- понятие y
1
имеет значение «атрибут» (P
E
(y
1
, атрибут)).
Продукция представляется в виде pr
5
Tr
:
q
5
Tr
= (P
S
(x
i
, y
1
, t
r
tip
) ∨ P
S
(t(x
i
), y
1
, t
r
tip
))
∧
P
E
(y
1
, атрибут) ↔ (
∃
x
i
:Х) P
S
(x
i
, атрибут, t
r
tip
)
∧ P
par
(η
i
, t(z
1
, 1), t(z
2
, 1), t(z
3
, h));
r
5
Tr
= add[P
par
(η
i
, t(z
1
, 1), t(z
2
, 1), t(z
3
, h))].
В случае успешного доказательства второй гипотезы вершине g
i
будет приписан
соответствующий ей вектор η
i
.
Система продукций для доказательства третьей гипотезы
Доказательство третьей гипотезы связано с доказательством четырех гипотез нижнего
уровня.
Первая гипотеза нижнего уровня. Для доказательства предположения, что лексема в
вершине g является тождественным понятием некоторому термину логической модели
данных, формируется множество предикатов Г=
Γ
3
∧q
6
Tr
={ ),,(
r
tgs
tyxP }∧q
6
Tr
, где
{
),,(
r
tgs
tyxP }- подмножество предикатов, задающих отношение тождества, а
q
6
Tr
– условие
применимости продукции pr
6
Tr
. Входная ситуация d
0
в этом случае задается предикатом
вида
),,(
r
tgis
tyxP , где х
i
– понятие, находящееся в вершине g.
Если доказательство прошло успешно, то в вершину g заносится соответствующее ей
понятие y
j
, для доказательства корректности которого осуществляется переход на
доказательство второй гипотезы верхнего уровня. Для этого необходимо найти
транзитивное замыкание
10
6
dd
Tr
pr
→ , в котором применение продукции pr
6
Tr
позволит
получить новое состояние d
1
= ),,(
r
tipis
tyxP ∨ ),),((
r
tipis
tyxtP , где x
i
– понятие y
j
вершины g.
Утверждение о том, что существует лексема x
i
, которая является тождественным
понятием некоторому термину логической модели данных, соответствует предикат
(
∃ x
i
:Х)P
S
(x
i
, z
j
, t
r
tg
), а в продукции pr
6
условие применимости q
6
и программа r
6
будут иметь
следующий вид: q
6
= P
S
(x
i
, z
j
, t
r
tg
) ↔ (
∃
x
i
:Х) P
S
(x
i
, z
j
, t
r
tg
); r
6
= add[(x
i
, z
j
)].
68
В случае успешного доказательства понятие x
i
, расположенное в вершине g
i
, будет
заменено на тождественное понятие z
j
и осуществлен переход на продукцию pr
4
Tr
для
доказательства второй гипотезы верхнего уровня. Для него входная ситуация
переопределяется как d
0
=d
1
.
Вторая гипотеза нижнего уровня. Доказывается аналогично доказательству,
описанному выше. При доказательстве гипотезы необходимо рассмотреть две ситуации,
которые зависят от типа вершины.
Первая ситуация касается случая, когда лексема x
i
является обобщенным или
агрегированным понятием и будет иметь вектор
η
i
с элементами z
1
, z
2
, z
3
тогда и только
тогда, когда имеет место закономерность, описываемая конъюнкцией следующих фактов:
- лексема х
i
принадлежит терму z - P
f
(t
in
(х
i
), y, f
23
), где f
23
– ссылка на процедуру,
которая осуществляет поиск лексемы х
i
в терме ),...,(
1 k
yyt предикатов, задающих
отношение агрегации
)),,...,(,(
1
r
agrks
tyytxP , и возвращает в качестве y – имя
агрегированного понятия;
- терм z является агрегированным понятием - P
S
(y, t(y
1
, …, y
k
), t
r
agr
);
- вершина не имеет вектор η
i
- ¬ P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null), t(z
4
, null)).
Для данного случая входная ситуация d
0
задается в виде:
d
0
= )),(,(
r
agris
txtyP ∨
)),(,(
r
obis
txtyP
.
(3.9)
А множество
Γ
включает в себя предикаты, задающие отношения агрегации
r
agr
t и
обобщения
r
ob
t , а также условие применимости продукции q
7
Tr
:
Г =
Γ
4
∧ q
7
Tr
={ )),,...,(,(
1
r
agrks
tyytxP }∧ {)),,...,(,(
1
r
obcs
tyytxP }∧q
7
Tr
.
(3.10)
Данной ситуации соответствует продукция pr
7
Tr
=<q
7
Tr
, r
7
Tr
>, в которой:
q
7
Tr
= P
f
(t
in
(х
i
), y, f
23
) ∧ P
S
(y, t(y
1
, …, y
k
), t
r
agr
) ∧ ¬ P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null)) ↔
(
∃ x
i
:X) P
S
(y, t(х
i
), t
r
agr
) ∧ P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null));
r
7
Tr
= add[P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null)) ∧ ( g
′
~
, y)].
Вторая ситуация. Эту ситуацию рассмотрим на примере, когда имеется три случая:
первый - лексема x
i
является фамилией, второй – именем, третий - отчеством. Рассмотрим
подробнее каждый из них.
Для первого случая утверждение предполагает, что лексема x
i
является значением
атрибута фамилия тогда и только тогда, когда имеет место закономерность, описываемая
конъюнкцией следующих фактов:
- лексема x
i
входит в синтаксическую группу y
1
- P
f
(t
in
(х
i
), y
1
, f
24
), где f
24
– ссылка на
процедуру, которая осуществляет проверку вхождения лексемы x
i
в терм ),...,(
1 k
yyt (в
состав синтаксической группы) предикатов, задающих отношение характеризации, а y
возвращает имя синтаксической группы;
- y
1
имеет значение «ФИО» - P
E
(y
1
, ФИО);
- лексема x
i
является y
2
элементом в синтаксической группе ФИО - P
f
(t
in
(х
i
, ФИО),
y
2
, f
25
), где f
25
– ссылка на процедуру, которая определяет положение лексемы х
i
в
синтаксической группе ФИО и возвращает в качестве переменной y
2
ее порядковый номер;
- y
2
имеет значение 1 - P
E
(y
2
, 1);
- вершина не имеет вектор η
i
- ¬ P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null)).
69
Входная ситуация d
0
задается в виде:
d
0
=
),),((
r
chis
tyxtP
, где
(3.11)
y – название синтаксической группы.
Множество входных дизъюнктов
Γ
включает в себя условие применимости
продукции q
8
Tr
, а также множество предикатов, задающих отношение характеризации
r
ch
t ,
которые описывают синтаксические группы, полученные на этапе синтаксического
анализа:
Г =
Γ
7
∧ q
i
={ ),),,...,((
1
r
chks
tyxxtP }∧q
i
, (
10,8=i
).
(3.12)
Тогда утверждению о том, что существует лексема x
i
, которая является значением
атрибута фамилия, будут соответствовать предикаты: (
∃
x
i
:X)
),),((
r
chis
tФИОxtP
∧ P
par
(η
i
,
t(z
1
, null), t(z
2
, 6), t(z
3
, null)), а продукция описывается парой pr
8
Tr
=<q
8
Tr
, r
8
Tr
>, где
q
8
Tr
= P
f
(t
in
(х
i
), y
1
, f
24
) ∧ P
E
(y
1
, ФИО) ∧ P
f
(t
in
(х
i
, ФИО), y
2
, f
25
) ∧ P
E
(y
2
, 1) ∧¬ P
par
(η
i
, t(z
1
,
null), t(z
2
, 6), t(z
3
, null), t(z
4
, null)) ↔ (
∃
x
i
:X) ),),((
r
chis
tФИОxtP ∧ P
par
(η
i
, t(z
1
, null), t(z
2
, 6),
t(z
3
, null));
r
8
Tr
= add[P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null)) ∧ ( g
′
~
, фамилия)].
Во втором случае проверяется факт принадлежности лексемы x
i
атрибуту имя, в
котором продукция pr
9
Tr
состоит из:
q
9
Tr
= P
f
(t
in
(х
i
), y
1
, f
24
) ∧ P
E
(y
1
, ФИО) ∧ P
f
(t
in
(х
i
, ФИО), y
2
, f
25
) ∧ P
E
(y
2
, 2) ∧¬ P
par
(η
i
, t(z
1
,
null), t(z
2
, 6), t(z
3
, null), t(z
4
, null)) ↔ (
∃
x
i
:X) ),),((
r
chis
tФИОxtP ∧ P
par
(η
i
, t(z
1
, null), t(z
2
, 6),
t(z
3
, null), t(z
4
, null));
r
9
Tr
= add[P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null)) ∧ ( g
′
~
, имя)].
В третьем случае проверяется факт принадлежности лексемы x
i
атрибуту отчество,
которому соответствует продукция pr
10
Tr
:
q
10
Tr
= P
f
(t
in
(х
i
), y
1
, f
24
) ∧ P
E
(y
1
, ФИО) ∧ P
f
(t
in
(х
i
, ФИО), y
2
, f
25
) ∧ P
E
(y
2
, 3) ∧¬ P
par
(η
i
, t(z
1
,
null), t(z
2
, 6), t(z
3
, null), t(z
4
, null)) ↔ (
∃
x
i
:M) ),),((
r
chis
tФИОxtP ∧ P
par
(η
i
, t(z
1
, null), t(z
2
, 6),
t(z
3
, null));
r
10
Tr
= add[P
par
(η
i
, t(z
1
, null), t(z
2
, 6), t(z
3
, null)) ∧ ( g
′
~
, отчество)].
Если доказательство гипотезы прошло успешно, то добавляется новая вершина
g
′
~
,
перед вершиной g, для анализа которой осуществляется переход на доказательство второй
гипотезы верхнего уровня.
Третья гипотеза нижнего уровня. Эта гипотеза предполагает, что лексема x
i
является
составной частью определения некоторого понятия тогда и только тогда, когда имеет место
один из двух случаев: лексема х
i
находится в отношении номинации t
r
nom
с термом t(z
1
,
…,z
k
) или лексема х
i
находится в отношении номинации t
r
nom
с переменной y и термом t(z
1
,
…,z
k
).
Для первого случая множество предикатов Г (3.13) включает в себя подмножество
предикатов номинации Г
51
и условие применимости q
11
Tr
∈pr
11
Tr
:
Г =
Γ
51
∧ q
11
Tr
={P
s
(x, t(z
1
, …,z
k
), t
r
nom
)}∧q
11
Tr
,
(3.13)
а входная ситуация d
0
задается в виде:
d
0
= P
s
(x
i
, t(z
1
, …,z
k
), t
r
nom
).
(3.14)
70
Продукция в этом случае представляется в виде pr
11
Tr
:
q
11
Tr
= P
s
(x
i
, t(z
1
, …,z
k
), t
r
nom
) ↔ (
∃
x
i
:X) P
s
(x
i
, t(z
1
, …,z
k
), t
r
nom
);
r
11
Tr
= add[(
1
~
g
′
, z
1
) ∧(
2
~
g
′
, z
2
) ∧ …
∧
(
k
g
′
~
, z
k
); elim (g)].
Для второго случая:
Этому случаю соответствует продукция pr
12
Tr
:
q
12
Tr
= P
s
(x
i
, y, r(verb),t(z
1
, …,z
k
), t
r
nom
)↔ (
∃
x
i
:X) P
s
(x
i
, y, r(verb),t(z
1
, …,z
k
), t
r
nom
);
r
12
Tr
= add[(
1
~
g
′
, y) ∧(
2
~
g
′
,z
1
) ∧(
3
~
g
′
,z
2
)
∧
…
∧
(
1
~
−
′
k
g , z
k
); elim (g)].
Если доказательство гипотезы прошло успешно, то программа r
удаляет вершину g,
перед ней добавляет новых k вершин, а затем переходит на первую добавленную вершину
для проверки второй гипотезы верхнего уровня.
Четвертая гипотеза нижнего уровня. Эта гипотеза утверждает, что лексема x
i
,
расположенная в вершине g, является синонимом понятию логической модели данных или
понятию проблемной среды. Для поиска синонима формируется множество входных
дизъюнктов
Γ
=
Γ
6
∧q
13
Tr
={
),,(
r
ans
tyxP
}
∧q
13
Tr
, состоящее из предикатов с отношениями
подобия
r
an
t
и условия применимости q
13
Tr
, а входная ситуация задается в виде предиката
подобия d
0
= P
s
(x
i
, y, t
r
an
). Данной гипотезе соответствует продукция pr
13
Tr
:
q
13
Tr
= P
s
(x
i
, y, t
r
an
) ↔ ( ∃ x
i
:X) P
s
(x
i
, y, t
r
an
); r
13
Tr
= add[(x
i
, y)].
В результате успешного доказательства гипотезы понятие x
i
заменится на
соответствующий синоним y. Затем произойдет переход на проверку всех предыдущих
гипотез, начиная с первой гипотезы верхнего уровня. Доказательство будет продолжаться
до тех пор, пока одна из гипотез не окажется истинной или пока не будет перебран весь
список синонимов текущей лексемы.
Таким образом, граф
G
′
~
, полученный в результате доказательства гипотез, и
исходный граф G являются гомеоморфными. Граф
G
′
~
будет содержать в вершинах
термины логической модели данных или термины языка SQL, с приписанными к каждой
вершине
g
′
~
векторами η
i
.
3.2.1.3. Преобразование графа зависимостей терминов логической модели в граф
зависимостей терминов физической модели – преобразование
3
Ψ
′
′
Построенный граф G
′
~
может иметь вершины с одинаковыми значениями. Так,
например, если две вершины
1
,
+ii
gg ∈G исходному графу имели значение «домашний» и
«телефон» соответственно, то при доказательстве третьей гипотезы нижнего уровня в
соответствующие вершины
Ggg
ii
′
∈
′′
+
~
~
,
~
1
будет записано одинаковое значение, например,
«Дом_телефон». Для удаления дублирующих вершин
Gg
′
∈
′
~
~
необходимо проверить
ситуацию, которая утверждает, что вектор
η
i
эквивалентен вектору
η
i+1
тогда и только
тогда, когда имеет место закономерность, описываемая конъюнкцией следующих фактов:
- вершина
i
g
′
~
имеет значение x
i
- P
s
(
i
g
′
~
, x
i
);
Г =
Γ
52
∧ q
12
Tr
={P
s
(x, y, r(verb),t(z
1
, …,z
k
), t
r
nom
)} ∧q
12
Tr
;
(3.15)
d
0
= P
s
(x
i
, t(z
1
, …,z
k
), t
r
nom
) ∨ P
s
(x
i
, y, r(verb),t(z
1
, …,z
k
), t
r
nom
).
(3.16)