Найханова Л.С. Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL запросы
Подождите немного. Документ загружается.
- MainUnit осуществляет формирование пар лексем, декодирование векторов
морфологической информации, взаимодействие со словарем, содержит описания основных
ассоциированных процедур для осуществления работы со словарями и с базой правил
системы продукций, вызов модуля управления продукционными правилами из второго блока
программ;
- Syntax содержит вычислительные процедуры синтаксического анализа и процедуры
удаления и добавления, соответствующие программам r
i
S
∈Pr
S
;
- ViewUnit – обеспечивает вывод дерева связи на экран, работу в форме вывода дерева
синтаксического разбора;
- SyntaxTest – отвечает за создание форм, которые постоянно присутствуют в программе,
обеспечивает работу всего приложения.
Программа проблемного анализа осуществляет преобразование графа синтаксического
разбора в граф зависимостей терминов физической модели данных и формирование SQL-
запроса. База знаний проблемного анализатора содержит множество предикатов описания
понятий проблемной среды и метаописания базы данных. База правил системы продукций
Pr
Tr
включает в себя множество правил распознавания и преобразования графов
зависимостей, множество правил формирования SQL-запроса. Программа состоит из шести
модулей:
- Norm содержит ассоциированные процедуры и функции приведения лексем,
расположенных в вершинах графа зависимостей, в начальную форму;
- LogMod включает в себя функциональные процедуры, предназначенные для
сопоставления лексем, с понятиями проблемной области и метаописания базы данных и
формирования соответствующего вектора;
- GrafMod содержит ассоциированные процедуры добавления и удаления вершин графа,
процедуры вывода дерева;
- Vekt содержит функциональные процедуры формирования векторов, соответствующие
программам r
i
Tr
∈Pr
Tr
;
- Quer содержит функциональные и вычислительные процедуры, осуществляющие
формирование графа SQL-запроса и преобразование его в SQL-запрос;
- ProblAn – модуль, который осуществляет вызов ассоциированных процедур и функций
из других модулей программы, отображает результаты анализа, вызов модуля управления
продукционными правилами второго компонента.
Описание второго блока программ
Второй компонент состоит из трех модулей: Cont, Dizn и Unif. Модуль Cont выполняет
функции «администратора» системы - управление продукционными правилами, сопряжение
программ друг с другом и включает в себя следующие основные процедуры:
- quart – процедура выбора типа предиката для представления входных данных в виде
исходной ситуации d
0
;
- trec – процедура проверки результатов логического вывода;
- lodg – процедура активации функциональных предикатов;
- gamm – процедура формирования множества предикатов Г
i
;
- rel – процедура вызов методов из других модулей.
Модуль Dizn предназначен для преобразования условия применимости продукции во
множество дизъюнктов, для осуществления которого введены следующие процедуры:
- rename – ассоциированная процедура замены исходных данных на промежуточные
переменные;
- knf – ассоциированная процедура приведения условия применимости к
конъюнктивной нормальной форме (КНФ);
- pnf – ассоциированная процедура приведения условия применимости из КНФ в
предваренную нормальную форму (ПНФ);
- ssf – ассоциированная процедура приведения условия применимости из ПНФ в
скулемовскую стандартную форму (ССФ);
- dename – ассоциированная процедура обратной замены промежуточных данных на
исходные.
Модуль Unif осуществляет построение логического вывода на основе множества
дизъюнктов и входной ситуации. Данный программный модуль включает в себя следующие
основные процедуры:
- rezolution - ассоциированная процедура построения дерева вывода методом поиска в
ширину;
- newroute - ассоциированная процедура вычисления последовательности дизъюнктов
(маршрута), которую необходимо проверять на следующем шаге поиска в ширину;
- provres - ассоциированная процедура проверки поиска решения в процессе
прохождения очередного маршрута;
- delsamelit - ассоциированная процедура удаления в промежуточном дизъюнкте,
выводимом на очередном шаге поиска в ширину, повторно повторяющейся литеры;
- unification - ассоциированная процедура выполнения алгоритма унификации для
текущей пары предикатов, проверки необходимости продолжения алгоритма унификации или
необходимости выполнения операции «композиция».
Описание функционирования программ
Схема функционирования программ показана на рисунке Е.1 и заключается в
следующем.
На вход морфологического анализатора подается естественно-языковой запрос
пользователя. Морфологический анализатор осуществляет разбиение запроса на множество
лексем Х. Далее х
i
лексема подается для доказательства на вход модуля управления
продукционными правилами вместе с Pr
j
M
продукцией. В случае успешного доказательства
истинности q
j
M
условия применимости на текущей исходной ситуации морфологический
анализатор активизирует процедуры программы r
j
M
и осуществляет переход к рассмотрению
следующей лексемы. В случае, когда все множество лексем рассмотрено, морфологический
анализатор передает на вход синтаксического анализатора множество лексем Х с
соответствующими им векторами морфологической информации, представленными в виде
множества векторов V.
Синтаксический анализатор для нормализации лексем естественно-языкового
предложения подает на вход модуля управления продукционными правилами пару или тройку
лексем и продукцию Pr
1
S
, которая относится к первой группе синтаксических связей. Далее
после перебора всех лексем и доказательства всех продукций первой группы осуществляется
141
140
выявление синтаксической связи между двумя лексемами множества Х с учетом полученных
синтаксических групп. Для этого синтаксический анализатор подает на вход модуля
управления продукционными правилами продукцию, которая относится ко второй группе
синтаксических правил. В случае успешного доказательства истинности q
j
S
условия
применимости на текущей исходной ситуации синтаксический анализатор активизирует
процедуры программы r
j
S
и осуществляет переход к рассмотрению следующей пары лексем.
На последнем этапе осуществляется формирование графа синтаксического разбора
G
′
′
и
переход к проблемному анализу.
На вход проблемного анализатора поступает множество дуг, представленных
множеством пар лексем D. Трансляция естественно-языкового запроса в SQL-запрос
осуществляется в несколько этапов. Задачей первого этапа является нормализация лексем, то
есть приведение их к начальной форме, к форме, в которой описаны понятия проблемной
среды и метаописание базы данных. На втором этапе осуществляется построение графа
G
′
~
,
изоморфного графу
G
′′
. Для этого каждая нормализованная лексема и соответствующая
данному этапу продукция Pr
i
Tr1
подаются на вход модуля управления продукционными
правилами. В случае успешного доказательства условия применимости q
i
Tr1
на входной
ситуации d
0
выполняется формирование соответствующего вектора
η
для каждой вершины
графа согласно процедурам программы r
i
Tr1
. На третьем этапе происходит преобразование
графа зависимостей терминов логической модели в граф зависимостей терминов физической
модели. При этом на вход модуля управления продукционными правилами подается вершина
графа
G
′
~
и продукция из множества продукций, принадлежащих Pr
i
Tr2
. В случае успешного
доказательства каждой вершине x
j
приписывается вектор
τ
l
. На последнем этапе проблемного
анализа осуществляется формирование SQL-запроса. В первую очередь выявляется тип связи
между парой вершин {(
ji
gg
~
,
~
)|
Ggg
ji
~
~
,
~
∈
}, для чего доказываются ситуации, описанные
продукциями множества Pr
i
Tr3
. В результате успешного доказательства происходит
обновление вектора
τ
l
и формирование графа G , путем добавления новых вершин в граф
G
~
.
Последним шагом данного этапа является формирование самого SQL – запроса посредством
доказательства продукций Pr
i
Tr4
.
Модуль управления продукционными правилами осуществляет для Pr
i
t
продукции
выбор типа предиката для представления исходной ситуации d
0
. В случае необходимости
активизирует функциональные предикаты и формирует множество предикатов Г
w
, обращаясь
к базе данных текущего анализатора. Далее модуль управления продукционными правилами
подает текущую продукцию q
i
t
на вход системы перевода для формирования множества
дизъюнктов
Γ
. Во множество
Γ
включаются дизъюнкты, полученные в результате
преобразования формулы, задающей условие применимости q
i
t
продукции Pr
i
t
, в
скулемовскую стандартную форму.
142
Рис. Е.1. Схема взаимодействия программных блоков
Для доказательства истинности условия применимости и для активации программы r
i
t
продукции Pr
i
t
полученное в результате приведения множество дизъюнктов
Γ
, входная
ситуация
0
d
и множество предикатов Г
w
поступают на вход системы логического вывода,
которая осуществляет построение дерева вывода и в качестве результата выдает ответ
«истина» или «ложь», который далее поступает на вход модуля управления продукционными
правилами. В случае отрицательного ответа модуль запрашивает следующую продукцию для
доказательства исходной ситуации d
0
, а в случае положительного ответа передает текущему
анализатору команду на активацию процедур программы r
i
t
.
Описание вычислительных экспериментов
Морфологический
анализатор
База правил
системы продукций
МА
База знаний
МА
Синтаксический
анализатор
Pr
i
M
Модуль управления
продукционными
правилами
Преобразователь q
i
в
стандартную форму
Система логического
вывода
Результат
вывода
S=Г
j
∧
q
i
t
∧
0
d
q
i
t
и d
0
База правил
системы продукций
РА
Проблемный анализатор
База знаний
ПА
Множество
лексем Х с МИ
Множество
пар D
ЕЯ - запрос
База правил
системы продукций
CА
База знаний
CА
SQL - запрос
Входные данные
Продукция - Pr
i
t
Pr
i
S
Pr
i
T
r
Лексема - x
j
Пара лексем – x
l
, x
h
Дуга – {x
e
, x
r
}
q
i
ложно
q
i
истинно - r
i
t
143
Для доказательства истинности выдвигаемого подхода рассмотрим анализ естественно-
языкового запроса пользователя к базе данных «Контингент учащихся».
К условиям проведения эксперимента относятся следующие требования:
- запрос должен относиться к проблемной области «Контингент учащихся вуза»;
- запрос должен удовлетворять ограничениям, изложенным в разделе 1.5.
На вход системе подается естественно-языковой запрос: «Выдать список студентов 630
группы». На рисунке Е.2 показано главное окно ввода естественно-языкового запроса, в
котором в нижнем окне отражены результаты его обработки.
Рис. Е.2. Окно ввода естественно-языкового запроса и вывода результатов
Активация программ продукций морфологического анализатора позволяет получить
морфологическую информацию о каждой лексеме. Для данного примера результаты
проведения морфологического анализа показаны на рисунке Е.3. В дальнейшем
морфологический анализатор формирует для каждой лексемы вектор морфологической
информации V = <v
1
, v
2
, v
3
, v
4
, v
5
, v
6
, v
7
, v
8
>, где v
1
– часть речи, v
2
– признак одушевленности,
v
3
– род, v
4
– число, v
5
– падеж, v
6
– лицо, v
7
– время, v
8
– признак для имени собственного.
144
Рис. Е.3. Результаты морфологического анализа
Результаты морфологического анализа поступают на вход синтаксического анализатора.
Для активации условий применимости, соответствующих правилам синтаксического анализа,
анализатор перебирает все пары лексем естественно-языкового запроса. В результате
активации программ продукций синтаксического анализа строится граф синтаксического
разбора. Для данного примера результаты проведения синтаксического анализа показаны на
рисунке Е.4.
Рис. Е.4. Результаты синтаксического анализа
145
Результаты синтаксического анализа поступают на вход проблемного анализатора. В
результате последовательных преобразований программа выводит промежуточные
результаты анализа, а в итоге формирует соответствующий входному естественно-языковому
запросу SQL-запрос. На рисунке Е.5 показаны результаты первых двух этапов проблемного
анализа. На первом этапе осуществляется нормализация лексем путем обращения к базе
знаний морфологического анализа, а на втором – распознавание и классификация лексем,
расположенных в вершинах графа синтаксического разбора. На основании этого строится
граф зависимостей Q’ в терминах логической модели данных. При этом каждой вершине
графа зависимостей Q’ приписывается вектор n, который содержит необходимые для
дальнейших преобразований свойства и характеристики вершин.
Следующий этап связан с преобразованием графа зависимостей Q’ в граф зависимостей
терминов физической модели данных Q, при котором формируется вектор t с описанием
дополнительных свойств вершин. Формирование графа SQL-запроса связано с поиском связей
между вершинами графа Q, которая определяется взаимосвязью таблиц в модели данных.
При этом осуществляется обновление вектора t. На последнем этапе, согласно правилам
анализа графа SQL-запроса, формируется SQL-запрос (рис. Е.6).
Рис. Е.5. Результаты первых двух этапов
проблемного анализа
Рис.Е.6. Результаты последних этапов
проблемного анализа
Таким образом, приведенные результаты подтверждают достоверность разработанных в
работе методов.
146
Лариса Владимировна Найханова
Инга Сергеевна Евдокимова
МЕТОДЫ И АЛГОРИТМЫ ТРАНСЛЯЦИИ
ЕСТЕСТВЕННО-ЯЗЫКОВЫХ ЗАПРОСОВ К БАЗЕ ДАННЫХ
В SQL-ЗАПРОСЫ
Монография
Редактор Т.А. Стороженко
Подписано в печать 4.10. 2004 г. Формат 60х84 1/8
Усл.п.л. 18,5. Печать операт., бум. писч.Тираж 100 экз. С. 148.
Издательство ВСГТУ, г. Улан-Удэ, ул. Ключевская, 40, в, строение 1.