Разработка языка запросов в бинарной модели знаний и транслятора этого языка в язык SQL (бакалаврская работа) (544460), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

“(/L: Alpha/, M: Beta, /N: Gamma/)” =

{(L: x, M: y, N: z) | x Alpha, y Beta, z Gamma}

{(L: x, M: y) | x Alpha, y Beta}

{(M: y, N: z) | y Beta, z Gamma} { M: y | y Beta}.

Конструктор списков LIST.

Этот конструктор по данному типу значений строит новый тип, элементами которого служат всевозможные списки, составленные из элементов исходного типа. Мы выбираем синтаксис списков такой, как в Прологе. Например, выражения [], [0,1,2], [[],[0,1,2],1,0], [[[0]]] и т.п. являются элементами типа значений LIST(Nat).

Alpha à LIST(Alpha),

“LIST(Alpha)” – множество всех списков, использующих элементы типа Alpha в качестве атомов.

С конструктором списков ассоциированы стандартные операции Лиспа:

сar: LIST(Alpha) à Alpha | {nil},

cdr: LIST(Alpha) à LIST(Alpha),

cons: (Alpha | LIST(Alpha), LIST(Alpha)) à LIST(Alpha).

Например, если переменные X, Y и Z приняли соответственно значения 2, [0,[1]], [[1,2],[0,0],3], то будем иметь:

car(Y) = 0, car(Z) = [1,2], car(X) и cdr(X) не определены,

cdr(Y) = [[1]], cdr(Z) = [[0,0],3], cons(X,Y) = [2,[0,1]],

cons(Y,Z) = [[0,[1]],[1,2],[0,0],3].

Операцию cons можно также обозначать :: и использовать в инфиксной нотации, считая, что выражения cons(X,Y) и X::Y эквивалентны, т.е. “cons(X,Y)” = “X::Y”. Таким образом, X::Y обозначает список, получаемый из списка “Y” путем вставки “X” на первое место (т.е. перед первым элементом списка “Y”).

Введем также операцию соединения двух списков, которую обозначим :-: и будем использовать ее в инфиксной нотации. (Эта операция соответствует функции append Лиспа.) Если, например, переменные X и Y прияли соответственно значения [2,[0,1],3] и [[],1,2,[3,0]], то “X:-:Y” = [2,[0,1],3,[],1,2,[3,0]].

Конструктор линейного списка LLIST.

Этот конструктор строит тип данных, элементами которого служат линейные (т.е. неразветвленные) списки, составленные из элементов данного типа данных:

Alpha à LLIST(Alpha),

“LLIST(Alpha)” = {[x₁,x₂,...,x_p] | x_j “Alpha” (1 j p)}.

Тип значений LLIST(Alpha) есть подтип (подмножество) типа значений LIST(Alpha). Поэтому на типе LLIST(Alpha) действуют также операции car, cdr, :: и

:-: . Но так как результатом операции :: может оказаться нелинейный список, нужно область определения этой операции сократить, считая (Alpha,LIST(Alpha)) спецификацией типа – области определения.

Кроме того, элементы линейного списка можно находить при помощи операции «точка». Например, если переменная Х приняла значение [5,5,0,1,3,6], то Х.1=5, Х.3=0, Х.6=6, Х.7 не определено.

Пусть Т – какая-либо спецификация типа данных и А – простое имя, выбранное для обозначения этого типа данных. Тогда предложение TYPE A = T декларирует тип данных, определяемый спецификацией Т.

Примеры 2.2:

1) TYPE Адресат = (ФИО: String, Адрес: (Индекс: Nat,

Город: String, Улица: String, Дом: String,

/Корпус: String/, Квартира: Nat))

Элементом типа Адресат служит, например, кортеж

е =(ФИО:'А.П.Иванов', Адрес:(Индекс:100010,Город:Москва,

Улица:Мясницкая, Дом:13,

Корпус:А, Квартира:17)).

Тогда имеем:

e.ФИО ='А.П.Иванов',

e.Адрес =(Индекс:100021, Город:Москва,

Улица:Мясницкая,Дом:10А, Квартира:17),

е.Адрес.Город = Москва,

e.Адрес.Улица = Мясницкая,

e.Адрес.Дом = 10А,

e.Адрес.Квартира = 17,

e.Адрес.(Город, Улица) = (Москва, Мясницкая).

Замечание. В последнем выражении был использован составной атрибут (Город, Улица).

Если нужно сохранить имена атрибутов, то можно воспользоваться двойной кавычкой:

e."ФИО = ФИО: 'А.П.Иванов',

e."Адрес = Адрес:(Индекс:100000, Город:Москва,

Улица:Мясницкая, Дом:13, Корпус:А,

Квартира:17),

e.Адрес."Город = Город:Москва,

e."Адрес.Город = Адрес:Москва,

e."Адрес."Город = Адрес:Город:Москва,

e.Адрес.("Город,"Улица) = (Город:Москва,Улица:Мяницкая).

2) Предположим, что нам нужно определить тип данных БинДерево (бинарное дерево), элементами которого служат уравновешенные бинарные деревья, концевым вершинам которых приписаны натуральные числа. (Уравновешенное бинарное дерево – это такое корневое дерево, у которого из каждой неконцевой вершины исходят ровно два ребра в направлении от корня). На рис.3.1 даны примеры элементов типа БинДерево.

(а) (б) (в)

0◦ ◦ ◦

/ \ / \

0◦ ◦1 ◦ ◦0

/ \

◦ ◦2

/ \

1◦ ◦ 1

Рис.1.1

Злесь (а) тривиальное одновершинное дерево. Такие деревья можно отождествить с натуральными числами j Nat. Если дерево e не является тривиальным, то оно имеет левое поддерево e.Лев и правое поддерево e.Прав. Например, пусть е₁, е₂ и е₃ обозначают соответственно деревья (а), (б) и (в), показанные на рис.1.1. Тогда имеем:

е₁ = 0, е₂.Лев = 0, е₂.Прав = 1, е₂ = (Лев:0,Прав:1),

е₃.Лев.Лев.Лев = 1, е₃.Лев.Лев.Прав = 1, ₃.Лев.Прав = 2,

е₃.Лев.Лев = (Лев:1,Прав:1), е₃.Прав = 0,

е₃.Лев =((Лев:1,Прав:1),Прав:2),

е₃ = (((Лев:1,Прав:1),Прав:2),Прав:0).

Произвольное бинарное дерево представляется вложенным кортежем с атрибутами Лев и Прав. Ясно, что тип данных БинДерево можно специфицировать с помощью следующего предложения:

TYPE БинДерево = Nat|(Лев:БинДерево,Прав:БинДерево).

Мы могли бы не вводить метки Лев и Прав и определить тип БинДерево с помощью следующего предложения:

TYPE БинДерево = Nat | (БинДерево, инДерево).

Ясно тогда, что дерево e₃ будет теперь представлено следующим кортежем: е₃ = (((1,1),2),0).

Применяя операцию "точка", мы можем получать составляющие поддеревья. Например, имеем:

е₃ .1 = ((1,1),2),0), е₃ .1.1 =(1,1), е₃ .1.1.2 = 1 .

3) Предположим, что нам нужно задать тип значений, элементами которого служат уравновешенные бинарные деревья с натуральными метками на всех вершинах, а не только на концевых. Тогда следует ввести атрибут Центр.

TYPE БинДерево1 = Nat|(Лев: БинДерево1, Центр:Nat, Прав: БинДерево1).

4) Предположим, что нам нужно задать тип значений, элементами которого служат произвольные (а не только бинарные) деревья, вершины которых помечены натуральными числами. Тогда можно воспользоваться коструктором LLIST.

TYPE Дерево = (Nat) | (Nat, LLIST(Дерево)).

Например, бинарное дерево, изображенное на рис.2.2., представляется выражением e=(Лев:(Лев:1,Центр:2,Прав:(Лев:0,Центр:4,Прав:1), Центр:5, Прав:9)

5

/ \

2 9

/ \

1 4

/ \

0 1

Рис.3.2

2.2.3. Спецификация функций

На специфицированных типах можно задавать операции (функции), используя предопределенные операции на примитивных типах значений и операторы, ассоциированные с конструкторами типов. Таким образом, мы получаем так называемые абстрактные типы данных.

Примеры 2.3:

1) Определим на типе значений БинДерево1 функцию, которая по заданному бинарному дереву (с натуральными метками в вершинах) дает зеркальное отражение этого дерева. Эту функцию обозначим отраж(X). Например, дерево (а) рис.1.3 отображается в дерево (б) рис.1.3. Эта функция определяется следующим образом:

FUN отраж: БинДерево1 -> БинДерево1

отраж(X):= X IF X IN Nat.

отраж((Лев:X,Центр:Y,Прав:Z)) :=

(Лев:отраж(Z),Центр:Y,Прав:отраж(X))

END

(а) (б)

2 2

/ \ / \

7 2 2 7

/ \ / \

4 1 1 4

/ \ / \

1 0 0 1

/ \ / \

2 3 3 2

Рис. 2.3.

Рассмотрим вычисление значения функции отраж(e), где

e=(Лев:(Лев:1,Центр:2,Прав:(Лев:0,Центр:4,Прав:1)), Центр:5, Прав:9).

(Кортеж е представляет дерево, изображенное на рис.1.2.)

отраж(e) = отраж((Лев:(Лев:1,Центр:2, Прав:(Лев:0,Центр:4,Прав:1),

Центр:5,Прав:9)) =

% X =(Лев:1,Центр:2,Прав:(Лев:0,Центр:4,Прав:1)), Y =5, Z =9 %

= (Лев:отраж(9),Центр:5,

Прав:отраж((Лев:1,Центр:2,

Прав:(Лев:0,Центр:4,Прав:1))) =

= (Лев:9,Центр:5,

Прав:отраж((Лев:1,Центр:2,

Прав:(Лев:0,Центр:4,Прав:1))) =

% Х =1, Y =2, Z = (Лев:0,Центр:4,Прав:1) %

= (Лев:9,Центр:5,

Прав:(Лев:отраж((Лев:0,Центр:4,Прав:1)),

Центр:2,Прав:отраж(1)) =

= (Лев:9,Центр:5,

Прав:(Лев:отраж((Лев:0,Центр:4,Прав:1)),

Центр:2,Прав:1) =

% X =0, Y =4, Z =1 %

= (Лев:9,Центр:5,

Прав:(Лев:отраж(1),Центр:4,Прав:отраж(0)),

Центр:2,Прав:1) =

= (Лев:9,Центр:5, Прав:(Лев:1,Центр:4,Прав:0),

Центр:2,Прав:1).

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

5

/ \

9 2

/ \

4 1

/ \

1 0

Рис.3.4.

2) Определим функцию, заданную на элементах типа Дерево, которая для каждого элемента e Дерево дает сумму всех меток, приписанных вершинам дерева e.

FUN сумма:Дерево->Nat

сумма((X)):= X IF X IN Nat.

сумма((X,Y)):= X+сумма(Y).

сумма(X::Y)):= сумма(X)+сумма(Y).

END

Например, для дерева, изображенного на рис.2.6, имеем:

сумма(5,[9,(2,[(4,[1,0]),1])]) = 5+сумма([9,(2,[(4,[1,0]),1])]) =

5+сумма(9)+сумма([(2,[(4,[1,0]),1])]) =

5+9+2+сумма([(4,[1,0]),1]) =

16+сумма((4,[1,0])+сумма(1) =

16+4+сумма([1,0])+1 =

21+сумма(1)+сумма(0) = 2+1+0= 22.

Мы рассмотрели только примеры спецификации операций для абстрактных типов данных, в которых использовались конструкторы := , IN, IF и CASE. В общем случае необходим функциональный язык программирования для определения функций. В БМЗ имеется простой функциональный язык типа языка Hope, [Филд и Харрисон 1991] .

Спецификация в этом языке произвольной функция (с несколькими аргументами, принадлежащими разным типам) выглядит так:

FUN f:(T₁,T₂,…,T_n) -> T

Характеристики

Список файлов ВКР