Динамические базы данных

Соpтиpовка списков

Сортировка представляет собой переупорядочивание элементов списка определенным образом. Назначением сортировки является упрощение доступа к нужным элементам. Гораздо легче искать что-либо в отсортированном списке, нежели в неотсортированном.

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

Второй из методов, метод вставки, особенно удобен для реализации на Прологе.

/* Программа: Сортировка списка целых чисел в порядке возрастания. */

domains

number = integer

list = number*

predicates

sort(list,list)

insert(number,list,list)

order(number,number)

clauses

sort([],[]).

sort([X|Tail],Sorted_list):- insert (Tail,Sorted_Tail), insert(X,Sorted_Tail,Sorted_list).

insert(X,[Y|Sorted_list],[Y|Sorted_list1]):- order(X,Y),!, insert(X,Sorted_list,Sorted_list1).

insert(X,Sorted_list,[X|Sorted_list]).

order(X,Y):- X>Y.

Goal sort([4,7,3,9],S).

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

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

Динамические БД состоят из фактов, которые можно добавлять и удалять во время выполнения программы. Для хранения таких фактов в программу вводится специальная секция database. Можно объявлять предикаты динамической БД в секциях database программы и использовать их таким же образом, как и предикаты, описанные в секциях predicates.

Для добавления новых фактов в базу данных в Прологе используются предикаты asserta и assertz, а предикаты retract и retractall служат для удаления существующих фактов.

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

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

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

Для того, чтобы различать предикаты с фактами, которые записаны в программу от тех, которые помещены в динамическую БД к имени последних обычно добавляется буква 'd'. Hапpимеp, brother – dbrother.

Для того, чтобы ввести в программу факты, существует три основных способа:

- включение фактов в секцию clauses;

- пополнение во время выполнения программы с помощью предикатов asserta и assertz;

- загрузка файла с фактами БД с помощью предиката consult.

Стандартные предикаты asserta, assertz, retract, retractall, consult, save могут иметь один или два агрумента.

Необязательный второй аргумент представляет собой имя БД. Если вы не дадите имени внутренней базе данных, то по умолчанию ей присваивается стандартное имя dbasedom.

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

asserta(<факт>) - (i)

asserta(<факт>, dbaseName) - (i,i)

assertz(<факт>) - (i)

assertz(<факт>, dbaseName) - (i,i)

Предикат retract удаляет первый факт в базе данных, который совпадает с фактом <факт>. При поиске с возвратом предикат retract возвращает альтернативные решения и удаляет все совпадающие факты, пока они имеются. Предикат retractall удаляет из базы данных все факты, совпадающие с образцом <факт>.

retract(<факт> [,databaseName]) - (i,i)

retractall(<факт> [,databaseName]) - (i,i)

Предикат consult считывает из файла факты, описанные в секции database, и вставляет их в конец соответствующей БД. Отметим, что предикат consult может считывать файлы только в том формате, который создает save.

consult(fileName) - (i)

consult(fileName, databaseName) - (i,i)

Файлы не должны содержать:

- прописных символов;

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

- комментариев;

- пустых строк;

- символов без двойных кавычек.

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

save(fileName) - (i)

save(fileName, databaseName) - (i,i)

database