Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы. Найханова Л.В - 29 стр.

     Начальное             состояние               системы              продукций          должно   содержать       конъюнкцию
                                       n
терминальных фактов ∧ Pi0 (e1 ,..., e mi ) , которое будем называть входной ситуацией, и
                                      i =1
обозначать d0. Программа r продукции pr будет активизирована в том случае, когда
условие применимости будет истинным. Для доказательства истинности условия
применимости для текущей ситуации будем использовать модифицированный метод
линейной резолюции Лавленда, Ковальского и Кюнера [132-133]. Чтобы применить данный
метод, необходимо сформировать множество дизъюнктов Γ. Множество Γ формируется из
двух групп формул. Первая группа включает формулы, описывающие закономерности
предметной области. Во вторую группу включаются дизъюнкты, полученные в результате
преобразования формулы, задающей условие применимости q продукции pr, в
скулемовскую стандартную форму (ССФ).
     В результате скулемизации получается множество дизъюнктов Γ, в котором в
дизъюнктах могут присутствовать скулемовские функции g ( xr ,..., xs ) , позволяющие
исключить (элиминировать) кванторы существования
         k                                                                          
      Γ=  ∨   Pl ( x1 ,..., x i, g ( x r ,..., x s ), x j .., x hl ) | r ≥ 1, s ≤ i  .                                (1.5)
         l =1                                                                       
     При выполнении линейной резолюции входные дизъюнкты С0 выбираются из
                                                                                                                    n
множества фактов, задающих текущую ситуацию d0. Конъюнкция фактов ∧ Pi0 (e1 ,..., e mi ) ,
                                                                                                                i =1
задающая исходную ситуацию, может быть представлена как множество фактов
          {
      d0= Pi0 (e1 ,..., e mi ) | i − количество фактов, mi − длина кортежа i − того факта .                     }       (1.6)
       Таким образом, С0 – это элемент множества d0, являеющийся первым центральным
дизъюнктом при построении дерева вывода для доказательства истинности условия
применимости некоторой i-той продукции для выбранного факта. Боковые дизъюнкты B
выбираются из множества Γ. Условием выбора является наличие в дизъюнкте P∈Γ литеры,
контрарной самой левой литере центрального дизъюнкта С. Затем дизъюнкты С и B
должны быть унифицированы. Для этого будем использовать модифицированный алгоритм
унификации. Два дизъюнкта С, B унифицируемы, если для них существует унификатор.
Введем необходимые для рассмотрения алгоритма определения.
       Определение 6. Пусть θ ={t1/x1,…,tn/xn} и λ={u1/y1,…,um/ym} – две подстановки. Тогда
композиция         θ•λ    есть    подстановка,   которая     получается     из     множества
{t1/x1,…,tn/xn,u1/y1,…,um/ym} вычеркиванием всех элементов tjλ/xj, для которых tjλ = xj, и всех
элементов ui/yi, таких, что yi∈{x1,…,xn}.
       Определение 7. Унификатор σ для пары выражений W=(С,B) будет наиболее общим
унификатором (НОУ) ⇔ для каждого унификатора θ для С, B существует такая
подстановка λ, что θ = σ•λ.
       Определение 8. Множество рассогласований Φ пары W получается выявлением
первой (слева) позиции аргумента, в которой не для всех выражений из W стоит один и тот
же символ.
       Алгоритм унификации. На вход алгоритма унификации подается пара W= (С, B):
       Шаг 1. Инициализация входных данных: k = 0, Wk = W, σk = ε.
       Шаг 2. Вычисление частичных функций. Если в выражениях С или B присутствует
                                                                             29