Лабораторная работа 7
Способы представления баз данных в Пролог-программах

       Цель работы:
  1. Знакомство с различными способами организации баз данных.
  2. Получение навыков доступа к отдельным целостным информационным элементам баз данных.

1. Введение

       В языке Пролог существует несколько различных способов представления базы данных. К основным из них следует отнести представление базы данных как:
       1) множество фактов, каждый из которых соответствует целостному информационному элементу (т.е. записи) базы данных;
       2) множество фактов, каждый из которых соответствует паре значений атрибут/ключ;
       3) список структур, в котором каждая структура соответствует записи базы данных;
       4) линейная рекурсивная структура, где каждая структура соответствует записи базы данных;
       5) рекурсивная структура в виде двоичного дерева, в которой каждый узел дерева соответствует записи базы данных.

       Выберем предметную область, например, СЛУЖЕБНЫЕ ОТНОШЕНИЯ, в которой сосредоточены взаимосвязи и сведения о сотрудниках, местах их работы и должностях, а также их должностных окладах.

       Для этой предметной области рассмотрим различные варианты структурной организации данных с использованием каждого из пяти названных способов представления базы данных

       Для каждого из возможных представлений попробуем реализовать запрос, позволяющий найти всех сотрудников определенного отдела.

2. Представление отношений в виде фактов

       Модель любой предметной области может быть представлена совокупностью объектов с указанием связей между ними. Используя реляционный подход к построению БД, любой объект может быть интерпретирован как отношение, достаточно полно описывающее некоторый аспект предметной области и устанавливающее функциональную зависимость атрибутов этого отношения от некоторого ключевого атрибута. Для рассматриваемого примера таким отношением может быть
РАБОТА (ИМЯ_СТУЖАЩЕГО, ОТДЕЛ, ДОЛЖНОСТЬ, ОКЛАД),
где в качестве ключа может рассматриваться атрибут - ИМЯ_СЛУЖАЩЕГО. Отношение представляет собой множество кортежей, каждый из которых соответствует определенному экземпляру объекта предметной области и может быть представлен в виде целостного информационного элемента.

       Простейшим способом представления базы данных в языке Пролог служит запись каждого целостного информационного элемента в виде факта, например:
work1 ("Петров", 101, "оператор", 20000).
work1 ("Павлов", 211, "начальник", 71000).
work1 ("Иванов", 101, "менеджер", 71500).
       Запрос work1 (Name, 101,Post,Salary) позволяет отыскать всех служащих 101 отдела.

3. Представление атрибутов в виде фактов

       Вместо того, чтобы записывать факты, содержащие целостные информационные элементы, можно использовать в качестве фактов отдельные атрибуты (т.е. свойства) этих информационных элементов. В случае необходимости Данные атрибуты можно собрать в единое целое при помощи правила. Один из атрибутов должен выступать в роли ключа, объединяющего все остальные свойства. Атрибут ИМЯ_СЛУЖАЩЕГО можно использовать в качестве ключа для БД work(). Первый экземпляр объекта РАБОТА можно представить таким образом: 
office ("Петров". 101).        /* отдел     */
post ("Петров", "оператор").   /* должность */
salary ("Петров", 20000).      /* оклад     */
       Все атрибуты для конкретного служащего, совокупность которых представляет собой определенный экземпляр объекта предметной области, можно объединить при помощи правила:
work2 (Name,Office,Post,Salary) :- office ( Name, Office ), post ( Name, Post), salary ( Name, Salary ).
       Это правило определяет неявную базу данных того же вида, что и приведенная ранее явная база данных work1(). Для этого правила можно воспользоваться предыдущим запросом, который даст те же результаты, что и ранее.

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

       Приведем пример правила, в котором предписывается выдача премии в 1000$ всем служащим отдела 101. Это можно описать с использованием вновь вводимого атрибута "премия", предикат для которого можно определить в виде правила:
prize ( Name, 1000 ) :- office ( Name, 101 ).
       Для некоторых служащих можно ввести дополнительный атрибут "стаж_работы" и некоторый набор фактов, его описывающий:
work_time ( "Петров", 2 ).
work_time ( "Иванов", 1 ).
       Добавление новых атрибутов "премия" и "стаж_работы" никак не повлияет на приведенное выше правило work2().

       Задание 2.
Составьте программу, позволяющую реализовать описанные в данном разделе структуры БД, запросы к ним и возможность их модификации. Сохраните программу в "lab7_1.рго"

4. Представление базы данных в виде списке, структур

       Базу данных можно также считать потоком целостных информационных элементов, что представляется на языке Пролог в виде списка структур. Каждый элемент списка - это целостный информационный элемент:
[ work ( "Петров". 101. "оператор" , 20000) , work ( "Павлов", 211, "начальник", 71000) , work ( "Иванов", 101, "менеджер" , 71500) ]
       Интересно отметить, что при таком подходе к структуре базы данных поток целостных информационных элементов lie нужно включать в текущую программу. Он может существовать лишь как аргумент запроса, входящий в различные подцели, которые обрабатывают этот поток.

       Доступ к отдельному информационному элементу такой БД будет осуществляться с использованием специальной процедуры, содержащей два аргумента. Входным будет второй аргумент процедуры. Он содержит список целостных информационных элементов. Результат выполнения процедуры возвращается через ее первый аргумент - по одному целостному информационному элементу за один ответ на запрос (т.е. по одному экземпляру объекта, или по одной записи).
record ( work(Name.Office.Post.Salary). [work(Name.Office.Post.Salary) п_]).
record ( work(Name,Office,Post,Salary), [work(_,_,_,_) п Tail]) :- record ( work(Name,Office,Post,Salary), Tail).
       Описание процедуры record() аналогично процедуре member(). С использованием процедуры record() можно составить запрос о всех служащих отдела 101. Во втором аргументе этого запроса полностью содержится вся база данных.
Goal:
record(work(Name,101,Post,Salary), [work("",101,"оператор",20000), work("",211,"начальник",71000), work("",101,"менеджер",71500)]).
       Задание 2.
Составьте программу, позволяющую реализовать данный запрос к БД в виде внешней цели.

       Включите БД в виде списка структур в состав программы и выполните к ней аналогичные запросы. Сохраните программу в файле "1аЬ7-2.рго".

       Попробуйте включить в состав программы процедуры модификации содержимого исходной БД (например, добавления и удаления элемента из списка) и сформируйте к программе ряд запросов. Сохраните программу в файле "lab7-3.pro". Тексты программы: запросы и ответы привести в отчете.

5. Представление базы данных в виде линейной рекурсивной структуры

       Еще одним из способов представления в памяти ЭВМ записей баз данных является использование рекурсивных структур, в которых один из ар1ументов каждой записи указывает на следующую запись. Рекурсивные структуры - аналог односвязных списков в других языках программирования, но работать с такими структурами в Прологе легче, так как он берет на себя все действия по обработке указателей.

       Для того, чтобы на Прологе создать рекурсивную структуру, состоящую из записей work() ("служащие"), единственное, что нужно - это ввести в эту структуру дополнительный аргумент, указывающий на следующую запись, в структуре которой также будет содержаться аргумент, указывающий на следующую за ней запись и т.д. Для указания в последней записи отсутствия следующей за ней записи, в качестве дополнительного аргумента вводится "end". Рассмотрим пример линейной рекурсивной структуры Служащий (Имя , Отдел, Должность , Оклад , Указатель нa следующую запись).

       Используя синтаксис языка Пролог, обозначим эту структуру work3(). По аналогии с ранее рассмотренным примером, она будет содержать три записи
work3( "Петров", 101, "оператор", 20000,
work3( "Павлов", 211, "начальник". 71000,
work3( "Иванов", 100, "менеджер". 71500, end))) 
1 запись        2 запись       3 запись             конец записей
       Заметьте, что уровень вложенности у каждой новой записи будет большим, чем v предыдущей. В пятом поле последней записи содержится слово "end", которое означает, что больше записей нет. Следует отметить, что дополнительный аргумент структуры, указывающий на следующие записи базы данных, сам имеет структуру этой записи. Т.е. структура записи определяется сама через себя: Служащий (Имя , Отдел, Должность , Оклад , Служащий).

       База данных, сформированная в виде рекурсивной структуры, должна позволять выполнять запросы и модифицировать данные. Одним из основных требований является возможность доступа к целостному информационному элементу (записи) БД. Рассмотрим вариант процедуры record(), которая модифицирована таким образом, чтобы стала возможной обработка рекурсивной структуры.

       Первым (выходным) аргументом новой процедуры является структура work(), содержащая четыре аргумента и соответствующая записи базы данных. Второй аргумент этой процедуры - это сама БД в виде рекурсивной структуры. Процедура состоит из двух правил. Первое из них строит структуру work() из верхнего уровня рекурсивной структуры данных. Второе правило игнорирует верхний уровень рекурсивной структуры и получает следующий целостный информационный элемент из оставшейся части базы данных (обозначенной переменной NextRecord).
record( work(Name,Office,Post,Salary), work3(Name, Office, Post, Salary, NextRecord)).
record( work(Name,Office,Post, Salary), work3( _,_,_,_, NextRecord)) :- work3 ( work(Name,Office,Post,Salary),NextRecord).
       Используя процедуру record(), можно сформировать внешнюю цель для запроса по отысканию всех служащих 101 отдела, при условии, что вторым аргументом процедуры будет вся база данных.
Goal:
record (work(Name,101,Post,Oкл), work3("Петров",101,"оператор",20000, work3("Павлов",211,"начальник"71000,work3("Иванов",l00, "менеджер",71500,end))).
       Ответ на этот запрос будет получен в виде
Name=Петров,
Post=onepaтop,
Salary=20000
Name=Иванов,
Post=менеджер,
Salary=71500
       Аналогичный вариант запроса реализован как внутренняя цель print_101 программы 16.
/* Программа 16 *)
domains
name = symbol
office = integer
worker = work(name,office)
/* описание рекурсивной структуры */
work3 = work3(name,office,work3) ; end
predicates
print_10l
record( worker, work3 )
goal
print_101 clauses record( work(N,O) , work3(N,0,_) ).
record( work(N,0) , work3(_,_,T) ) :- record( work(N,0) ,T).
print_101:- write(" Сотрудники 101 отдела"),nl.
record ( work(N,101), wоrkЗ("Петров",101, work3("Павлов",211, workЗ("Ивaнов",101,end)))), write(n),nl, fail.
       Эта программа работает с БД work3(), представленной в виде линейной рекурсивной структуры.

       Для упрощения программы в БД work() используется всего два ПОЛЯ (ФАМИЛИЯ и ОТДЕЛ), т.е. информационные элементы work(), содержат всего по две компоненты.

       Процедура record() позволяет выполнять доступ к отдельной записи БД.

       Задание 3.
Тщательно разобравшись со структурой программы 16. измените ее таким образом, чтобы она позволяла работать со структурой БД, описанной в данном разделе и выполнять запросы к ней. Сохраните программу в файле "lab7-4.рго"

6. Представление базы данных в виде двоичного дерева

       Можно еще более усовершенствовать метод представления данных в виде рекурсивной структуры, если преобразовать структуру work3() в структуру типа двоичное дерево. Это достигается путем введения в структуру записи БД еще одного дополнительного аргумента, который указывает на предыдущую запись.

       Смысл использования двоичного дерева заключается в том, чтобы хранить базу данных в отсортированном виде. В рассматриваемом ниже примере база данных отсортирована по атрибуту, описывающему имя служащего и представляется бинарным деревом вида:
       Теперь в структуре информационного элемента будет шесть аргументов: 
     Павлов, …
	/      \
     Иванов, ...         Петров, ...
      /        \           /       \
    end        end        end      end
work4( LeftTree, Name,Office,Post,Salary, RightTree)
       Переменная LeftTree описывает ветвь дерева, которая содержит все целостные информационные элементы, стоящие (по алфавиту) перед текущим элементом. Переменная RightTree описывает ветвь дерева, охватывающую все целостные информационные элементы, расположенные согласно алфавиту, после данного элемента. ~ Ввиду того, что БД отсортирована, целостный информационный элемент, содержащий вес сведения о Павлове, является самым верхним узлом дерева, а саму БД, представленную в виде двоичного дерева, можно записать следующим образом:
work4 ( work4( end, "Иванов", 101,"менеджер",71500, end ), "Павлов",211,"начальник",71000, work4( end,"Петров", 101,"оператор", 20000,end),)
       Версия процедуры record() для доступа к целостному информационному элементу БД, представленной в виде двоичного дерева, будет базироваться на трех правилах:
       - запись принадлежит дереву, если она находится в левом поддереве,
       - запись принадлежит дереву, если она является корнем этого дерева,
       - запись принадлежит дереву, если она находится в правом поддереве. Эту процедуру, используя синтаксис Пролога, можно описать следующим образом:
record ( work(Name,Office,Post,Salary), work4(LeftTree, _,_,_,_, __)):- record ( work(Name, Office, Post, Salary), Let: Tree ).
record { work(Name,Office,Post,Salary), work4( _, Name.Office.Post.Salary, _) ).
record ( work(Name,Office,Post,Salary), work4(_, _,_,_,_, RightTree) ) :- record ( work(Name,Office,Post,Salary), RightTree ).
       Теперь процедура record() определена, и можно написать запрос, позволяющий найти всех служащих отдела 101. Вторым аргументом запроса является целиком вся база данных.
Goal:
record ( work(Name, 101,Post, Salary),
work4 (
work4( end, "Иванов", 101, "менеджер",71500. end ), "Павлов",211,"начальник",71000, work4( end, "Петров", 101,"оператор",20000,end). ) )
       Ответ на запрос будет тот же самый, что и в предыдущих случаях. Одним из интересных свойств представления в виде двоичного дерева является то, что процедура record() всегда будет выдавать целостные информационные элементы, образующие дерево, в отсортированном порядке. Это иллюстрирует запрос
Goal:
record ( OneRecord,
work4 (
work4( end, "Иванов", 101, "менеджер",71500, end ), "Парлов",211,"начальник",71000, work4( end,"Петров", 101 ."оператор", 20000,end),)
OneRecord = work("Иванов"10l,"onepaтop",20000);
OneRecord = work("Павлов",211, "начальник", 71000);
OneRecord = work("Петров",101," менеджер ",71500);
       Задание 4.
Измените программу "1аb7-4.рго" для работы с БД, которая представляется в виде двоичного дерева и позволяет реализовать запросы к ней, описанные в данном разделе.

       Включите содержимое исходной БД в виде двоичного дерева в состав ир01раммы и выполните к ней запросы, аналогичные выше приведенному. Сохраните программу в файле "lab 7-5. pro". Текст программы, запросы и ответы на них привести в отчете.

7. Сравнение разных видов представления базы данных

       Наиболее важным различием между описанными формами представления БД является то, что для доступа к данным в каждом случае требуется свой алгоритм.

       Говоря конкретно, при представлении БД в виде целостных информационных элементов, являющихся фактами, или при представлении атрибутов в виде фактов, доступ к БД должен осуществляться при помощи алгоритма поиска с возвратом (backtracking algorithm), а при использовании рекурсивных структур данных (в том числе, списков и двоичных деревьев) доступ должен реализоваться рекурсивным алгоритмом. Правила и запросы, приведенные в данной работе, служат простыми примерами этих алгоритмов.

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

8. Несколько полезных процедур работы с бинарными деревьями

       Эффективность работы с БД в виде двоичных деревьев во многом определяется знаниями процедур их создана и преобразования. Рассмотрим ряд процедур, оперирующих с двоичными деревьями, описываемыми структурами вида
tree( Left , Root , Right ),
где Left - левое поддерево, каждый элемент которого имеет структуру, аналогичную tree(),
    Root - корень (любая произвольная, определяемая пользователем, структура),
    Right - правое поддерево, состоящее из элементов структуры tree().

       Построение бинарного дереве. Задача создания упорядоченного дерева при добавлении некоторого элемента Х к другому упорядоченному дереву может быть сформулирована следующим образом:
       Граничное условие: Добавление Х к пустому дереву дает tree(end,X,end).
       Рекурсивные условия: При включении Х в tree(Left,Root,Right) надо рассмотреть два случая, для того, чтобы результирующее дерево было упорядоченным.

       1. Если Х меньше, чем Root, то Х добавляется к любому поддереву.
       2. Если Х больше, чем Root, то Х следует добавить к правому поддереву. В обоих случаях значения корня и противоположного поддерева не меняются. Такой формулировке соответствует процедура insert(), которую запишем в виде:
insert( end, X, tree( end, X, end ) ).
insert( tree(Left, Root, Right ), X, tree(LenNew,Root,Right) ) :- X < Root, insert( Left, X, LeftNew ).
insert( tree(Left,Root,Right), X, tree(Left.Root,RightNew) ) :- X > Root, insert( Right, X, RightNew ).
       Построение бинарного дерева из списка. Процедуру insert() можно использовать для построения упорядоченного дерева из списка. Процедура, обеспечивающая преобразование списка в упорядоченное дерево, будет иметь вид:
list_to_tree([], end ).
list_to_tree([HпT],AllTree) :- list_to_tree( T, Tree), insert(Tree, H, AllTree).
       Построение отсортированного списка из дерева. Для решения этой задачи можно воспользоваться упорядоченным бинарным деревом и объединением списков.

       Граничное условие: Пустое бинарное дерево (end) приводит к пустому списку [].

       Рекурсивное условие: Отсортированный список для упорядоченного бинарного дерева tree(Left,Root,Right), где Left имеет отсортированный список L1, a Right имеет отсортированный список L2, получается присоединением [Root пL2] к L1.
tree_to_list( end , [] ).
tree_to_list( tree(Left,Root,Right), List ) :- tree_to_list( Left, L1), tree_to_list( Right, L2), append( L1, [Root п L2], List).
       Рассмотрим пример использования этих процедур в Пролог-программе, работающей с базами данных разных структур и преобразующей эти структуры.
/* Программа 17 */
domains
worker = symbol
listworker = worker*
tree = tree(tree,worker,tree) ; end
predicates
db1( tree )
db2( listworker )
record( worker, tree )
append( listworker, listworker, listworker)
insert( tree, worker, tree)
list_to_tree( listworker, tree )
tree_to_list( tree, listworker)
goal1
goal2
goal3
goal4
goal5
goal6
goal7
goal8
clauses
goal1 :- db1(DB), write(DB).
goal2 :- db1(DB), record(R,DB), write(R), nl, fail.
goal3 :- db1(DB), write("введи элемент "), readln(El), insert(DВ ,E1,DBnew), write(Dbnew).
goal4 :- dbl(DB), write("введи элемент "), readln(El), insert(DB,El,DBnew), record(R,DBnew), write(R), nl, fail.
goal5 :- db2(List), list_to_tree(List,Tree), write(Tree).
goal6 :- db2(List), list_to_tree(List,Tree), record(R,Tree), write(R), nl, fail.
goal7 :- dbl(Tree), tree_to_list(Tree,List), write(List).
goal8 :- db2(List), write(List), nl.
list_to_tree(List,Tree). write(Tree), nl,
tree_to_list(Tree,NewList), write(NewList), nl.
insert( end, X, tree(end, X,end) ).
insert( tree(L,Root,R). X, tree(LNew,Root.R)) :- X < Root.
insert(L,X, Lnew ).
insert( tree(L,Root,R). X, tree(L,Root,RNew)) :- X > Root.
insert( R,X, RNew).
list_to_tree( [] , end ).
list_to_tree([HпT], AllTree) :- list_to_tree( T, Tree ),
insert( Tree, H, AllTree ).
tree_to_list( end , [] ).
tree_to_list(tree(L,Root,R),List) :- tree_to_list( L, L1),
tree_to_list( R, L2),
append( L1, [ Root п L2 ], List ).
record( R, tree(LeftTree, _,_)):- record( R, LeftTree).
record( R, tree( , R,_) ).
record( R, tree( _, _,RightTree)):- record( R, RightTree).
append( [], L2, L2 ).
append( [HпL1], L2. [H п L3]) :- append(L1, L2, L3).
dbl( tree( tree(end,a,end), c, tree(end,e,end) ) ).
db2( [ c, e, a ] ).
       Использование описанных выше процедур позволяет как модифицировать базы данных, так и осуществлять их структурные преобразования. Программа 17 даст возможность исследовать простейшие преобразования над базами данных.

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

       Обе базы задаются непосредственно в программе с помощью предикатов db1() и db2(). Простейшие преобразования над базами иллюстрируются с помощью восьми целей, сформированных непосредственно в программе. Каждая из этих целей может быть вызвана из оболочки Турбо-Пролога как внешняя цель. Рассмотрим назначение каждой из сформированных в программе целей.

       Первая цель (goal1) позволяет просмотреть содержимое первой базы данных заданной в виде бинарного дерева.

       Вторая цель (goal2) позволяет последовательно просмотреть записи первой базы данных, что достигается выделением из БД отдельных информационных элементов с помощью процедуры record().

       Третья и четвертая цели (goal3 и goal4) иллюстрируют возможность модификации первой БД путем добавления в нее нового элемента с сохранением упорядоченности.

       Пятая и шестая цепи (goal5 и goal6) показывают, как база данных, заданная в виде списка, может быть преобразована в структуру типа бинарного дереза.

       Седьмая цель (goal7) иллюстрирует возможность преобразования упорядоченное дерево в отсортированный список.

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

       Задание 5.
Загрузите программу 17. Тщательно разберитесь с описанием структур и предикатов программы, а также назначением ее процедур. Исследуйте программу, выполнив описанные в ней цели. Сформируйте ряд новых целей, позволяющих исследовать преобразование структур баз данных. В программе 17 используется простейшая структура информационных элементов. Измените программу для работы со структурами типа work(). рассмотренных в предыдущих разделах данной лабораторной работы. Сохраните программу в файле "lab7-5.pro". Текст программы, запросы и ответы на них привести в отчете.

       Все процедуры, используемые в программе 17, описаны в данной работе. Исключение составляет процедура слияния двух списков append(), подробное описание которой приведено в предыдущей лабораторной работе, посвященной работе со списками.

9. Содержание отчета по лабораторной работе

       Отчет по лабораторной работе должна содержать:
  1. Тексты программ, сохраненных на диске в соответствии с заданиями.
  2. Запросы, сформированные самостоятельно при изучении данной работы, а также результаты из выполнения.
  3. Результаты выполнения заданий 1, 2, 3, 4. 5 данной лабораторной работы.
  4. Приведите четкое описание каждой из целей, исследованных при работе с программой 17.