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

       Определение 2. Подстановка θ – это конечное множество вида {t1/v1,…,tn/vn}, где
каждая vi – переменная, а ti – терм, отличный от vi, при этом все vi различны. Подстановка,
которая не содержит элементов, называется пустой и обозначается ε.
       Определение 3. Пусть θ ={t1/v1,…,tn/vn} – подстановка и Е – выражение. Тогда Еθ –
выражение, полученное из Е заменой одновременно всех вхождений переменной vi (1≤i≤n)
в Е на ti. Еθ называют примером Е.
        Тогда запись dθ является примером d и означает результат одновременной замены
каждого вхождения переменной vi, в d на соответствующий терм ti.
        Определим основные преобразования ситуации, к которым относятся исключение и
добавление фактов. Для фиксированного d ′ ∈ D :
        1. Операция исключения: elim[d'] : D →D; elim[d'](d) = d\ d'
       2. Операция добавления: аdd[d'] : D →D;      add[d'](d) =d ∪ d'
        Определим множество программ R преобразования ситуации следующим образом.
Во-первых, будем считать элементами R программы add[d'], elim[d'] при любых d ′ ∈ D , во-
вторых, если две программы r1, r2 ∈ R , то программа (r1, r2), определенная равенством
(r1, r2)(d) = r2(r1(d)), ∀d ∈ D , также элемент R.
       Определение 4. Программу r+, содержащую только операции типа add[d'] ( ∀d ′ ∈ D ),
назовем позитивной. Заметим, что out(r+) = ∅ и, если d2 = r+(d1), то d 2 ⊇ d1 .
      Через rθ, где θ = {t1/x1, ... , tm /xm} — произвольная подстановка, обозначим программу
r, во всех операциях которой аргументы-переменные xi заменены на сопоставленные им
в θ термы ti, i = 1...m.
      Определение 5. Продукцией назовем пару , в которой q — ситуация, называемая
условием применимости продукции, r - программа, r ∈ R , называемая действием, причем q
и r связаны соотношением var(q) ⊇ out(r).
      Здесь var(q) - это множество имен переменных, входящих в условие
применимости q, а Out(r) - множество имен переменных, входящих в программу r.
      Системой продукций назовем конечное множество пар Рr = {}. Будем говорить,
что d2 непосредственно выводимо из d1 при помощи продукции pr = , d1 →
                                                                            pr
                                                                               d2 ,
если найдется такая подстановка θ, что d1 ⊇ qθ, а d2=r(qθ)∪(d1\qθ).
      Если найдется последовательность продукций рr1, рr2, ..., prk, pri ∈ Pr, i = 1..k, k≥0 и
                                                    pr1              pri               prk
состояний базы        d0, d1, …, dk таких, что d 0 
                                                    → d1 ...d i −1 
                                                                     → d i ...d k −1 → d k ,            то
                                             pr1... prk          *
говорим, что dk выводимо из d0, и пишем d 0                   → d k , a pr1, рr2, ..., prk
                                                → d k или d 0 
назовем последовательностью применимых к d0 продукций.
     При разработке системы продукций необходимо предусмотреть в них различные
ситуации, которые могут возникнуть при решении задачи. В продукциях возможные
ситуации описываются посредством условия применимости в виде предикатов
(Θt1 : Dt1 )...(Θtm : Dt m ) Pi (t1 ,..., tm ) , где t1 ,..., t m - термы предикатного символа Рi, некоторые из
которых вычисляются посредством функциональных преобразований (частичных функций
 f ∈ F ), Θ - оператор, задающий квантификацию формулы и принимающий значение ∀ и
∃,   Dt j - задает область интерпретации терма tj, связанных логическими операциями
∧,∨, ≡, ¬, ⊃ .

                                                     28