Внутренние (динамические) базы данных
В этой лекции мы начнем изучать работу с базами данных в Прологе.
С одной стороны, Пролог-программы не зря называют базами знаний. На Прологе легко реализуются реляционные базы данных, наиболее распространенные в настоящее время. Любая таблица реляционной базы данных может быть описана соответствующим набором фактов, где каждой записи исходной таблицы будет соответствовать один факт. Каждому полю будет соответствовать аргумент предиката, реализующего таблицу. Многие дистрибутивы Пролога содержат в качестве примера реализацию базовой части языка SQL. Можно сказать, что структура реляционных баз данных включается в структуру Пролог-программ.
С другой стороны, Турбо Пролог, на который мы все-таки ориентируемся в нашем курсе, имеет встроенные средства для работы с двумя типами баз данных: внутренними и внешними. Внутренние базы данных так называются потому, что они обрабатываются исключительно в оперативной памяти компьютера, в отличие от внешних баз данных, которые могут обрабатываться на диске или в памяти. Так как внутренние базы данных размещаются в оперативной памяти компьютера, конечно, работать с ними существенно быстрее, чем с внешними. С другой стороны, емкость оперативной памяти, как правило, намного меньше, чем емкость внешней памяти. Отсюда следует, что объем внешней базы данных может быть существенно больше объема внутренней базы данных. И если предполагается, что база может оказаться довольно большой, то следует использовать именно внешние базы данных.
Изучение внешних баз данных выходит за рамки данного курса.
В этой лекции мы займемся изучением внутренних или, как их еще называют, динамических баз данных.
Внутренняя база данных состоит из фактов, которые можно динамически, в процессе выполнения программы, добавлять в базу данных и удалять из нее, сохранять в файле, загружать факты из файла в базу данных. Эти факты могут использовать только предикаты, описанные в разделе описания предикатов базы данных.
DATABASE [ — <имя базы данных>] <имя предиката>(<имя домена первого аргумента>,..., < имя домена n-го аргумента>) ...
Если раздел описания предикатов базы данных в программе только один, то он может не иметь имени. В этом случае он автоматически получает стандартное имя dbasedom. В случае наличия в программе нескольких разделов описания предикатов базы данных только один из них может быть безымянным. Все остальные должны иметь уникальное имя, которое указывается после названия раздела DATABASE и тире. Когда объявлен раздел описания предикатов базы данных, компилятор внутренне объявляет соответствующий домен с таким же именем, как у этого раздела; это позволяет специальным предикатам обрабатывать факты как термы.
Описание предикатов базы данных совпадает с их описанием в разделе описания предикатов PREDICATES. Однако эти предикаты можно задействовать в качестве параметров встроенных предикатов, с которыми мы познакомимся чуть позже. Кроме того, факты, использующие эти предикаты, могут добавляться и удаляться во время выполнения программы.
Обратите внимание на то, что в базе данных могут содержаться только факты, а не правила вывода, причем факты базы данных не могут содержать свободных переменных. Это еще одно существенное отличие Турбо Пролога от классического Пролога, в котором во время работы программы можно добавлять и удалять не только факты, но и правила. Заметим, что в Visual Prolog, который является наследником Турбо Пролога, в названии раздела описания предикатов внутренней базы данных слово DATABASE заменено синонимом FACTS, что еще больше подчеркивает, что во внутренней базе данных могут храниться только факты, а не правила.
Давайте познакомимся со встроенными предикатами Турбо Пролога, предназначенными для работы с внутренней базой данных. Все рассматриваемые далее предикаты могут использоваться в варианте с одним или двумя аргументами. Причем одноаргументный вариант используется, если внутренняя база данных не имеет имени. Если же база поименована, то нужно использовать двухаргументный предикат, в котором второй аргумент — это имя базы.
Начнем с предикатов, с помощью которых во время работы программы можно добавлять или удалять факты базы данных.
Для добавления фактов во внутреннюю базу данных может использоваться один из трех предикатов assert, asserta или assertz. Разница между этими предикатами заключается в том, что предикат asserta добавляет факт перед другими фактами (в начало внутренней базы данных), а предикат assertz добавляет факт после других фактов (в конец базы данных). Предикат assert добавлен для совместимости с другими версиями Пролога и работает точно так же, как и assertz. В качестве первого параметра у этих предикатов указывается добавляемый факт, в качестве второго, необязательного — имя внутренней базы данных, в которую добавляется факт. Можно сказать, что предикаты assert и assertz работают с совокупностью фактов, как с очередью, а предикат asserta — как со стеком.
Для удаления фактов из базы данных служат предикаты retract и retractall. Предикат retract удаляет из внутренней базы данных первый с начала факт, который может быть отождествлен с его первым параметром. Вторым необязательным параметром этого предиката является имя внутренней базы данных.
Для удаления всех предикатов, соответствующих его первому аргументу, служит предикат retractall. Для удаления всех фактов из некоторой внутренней базы данных следует вызвать этот предикат, указав ему в качестве первого параметра анонимную переменную. Так как анонимная переменная сопоставляется с любым объектом, а предикат retractall удаляет все факты, которые могут быть отождествлены с его первым аргументом, все факты будут удалены из внутренней базы данных. Если вторым аргументом этого предиката указано имя базы данных, то факты удаляются из указанной базы данных. Если второй аргумент не указан, факты удаляются из единственной неименованной базы данных. Заметим, что предикат retractall может быть заменен комбинацией предикатов retract и fail следующим образом:
retractall2(Fact):– retract(Fact), fail. retractall2(_).
Для сохранения динамической базы на диске служит предикат save. Он сохраняет ее в текстовый файл с именем, которое было указано в качестве первого параметра предиката.
Если второй необязательный параметр был опущен, происходит сохранение фактов из единственной неименованной внутренней базы данных. Если было указано имя внутренней базы данных, в файл будут сохранены факты именно этой базы данных.
Факты, сохраненные в текстовом файле на диске, могут быть загружены в оперативную память командой consult. Первым параметром этого предиката указывается имя текстового файла, из которого нужно загрузить факты. Если второй параметр опущен, факты будут загружены в единственную неименованную внутреннюю базу данных. Если второй параметр указан, факты будут загружены в ту внутреннюю базу данных, чье имя было помещено во второй параметр предиката. Предикат будет неуспешен, если для считываемого файла недостаточно свободного места в оперативной памяти или если указанный файл не найден на диске, или если он содержит ошибки (ниже будет разъяснено чуть подробнее, какими они бывают).
Заметим, что сохраненная внутренняя база данных представляет собой обычный текстовый файл, который может быть просмотрен и/или изменен в любом текстовом редакторе. При редактировании или создании файла, который планируется применить для последующей загрузки фактов с использованием предиката consult, нужно учитывать, что каждый факт должен занимать отдельную строку. Количество аргументов и их тип должны соответствовать описанию предиката в разделе database. В файле не должно быть пустых строк, внутри фактов не должно быть пробелов, за исключением тех, которые содержатся внутри строк в двойных кавычках, других специальных символов типа конца строки, табуляции и т.д. Давайте на примере разберемся со всеми этими предикатами.
Пример. Напишем программу, реализующую компьютерный вариант телефонного справочника. Основное назначение этой не очень сложной программы — находить по фамилии человека его телефонный номер или, наоборот, по телефонному номеру — фамилию владельца телефона. У пользователя нашей программы должна быть возможность добавлять информацию в базу данных, а также удалять и изменять устаревшую информацию.
Приступим к реализации нашего проекта. Внутренняя база данных будет содержать факты, описывающие единственный предикат, имеющий два аргумента. Первым аргументом предиката будет фамилия человека, а вторым — его телефонный номер. Для упрощения программы будем считать, что соответствие между фамилиями и номерами телефонов взаимооднозначное, то есть каждой фамилии соответствует не более одного телефонного номера, и наоборот.
Сделаем так, чтобы при запуске программы появлялось меню, из которого пользователь мог выбрать, какое действие с телефонной базой он хотел бы осуществить. Реализуем пять операций:
- Получение информации о телефонном номере по фамилии человека.
- Получение информации о фамилии абонента по телефонному номеру.
- Добавление новой записи в телефонную базу.
- Изменение существующей в телефонной базе записи.
- Удаление записи из телефонной базы.
Нужно учесть, что пользователь может ошибиться и нажать клавишу, не соответствующую ни одной из пяти указанных операций. После выполнения каждой из операций программа должна вернуться обратно в меню, чтобы у пользователя не было необходимости запускать программу заново, если ему нужно выполнить еще одно действие.
Кроме того, у пользователя должна быть возможность выйти из программы, не совершая никаких действий. При выходе из программы факты телефонной базы должны быть сохранены из оперативной памяти в файл на диске, а оперативная память очищена от ненужных фактов.
Эти действия выполняет следующее правило (символ '0' означает, что пользователь нажал соответствующую клавишу):
m('0'):– save("phones.ddb "), /* сохраняем телефонную базу в файл */ retractall(_)./* удаляем все факты из внутренней базы данных */
В начале работы программы факты из телефонной базы, хранящейся в файле на диске, должны загружаться во внутреннюю базу данных, в случае, если такой файл существует.
Предикат, предназначенный для выполнения этих действий, выглядит следующим образом:
start:– existfile("phones.ddb"),!, /* если существует файл с телефонной базой */ consult("phones.ddb "), /* , то загружаем факты во внутреннюю базу данных */ menu. /* и вызываем меню */ start:– menu. /* если такого файла еще нет, просто вызываем меню */
Если пользователь выбрал первую операцию, должен быть выдан телефонный номер абонента (если в телефонной базе имеется соответствующий факт) или сообщение о том, что в телефонной базе нет такой информации.
Это реализуют два приведенных ниже предиката.
m('1'):– write("Введите фамилию"), nl, /* выводим приглашение ввести фамилию */ readln(Name), /* читаем введенную фамилию в переменную Name */ name_phone(Name, Phone), /* вызываем предикат, который помещает в переменную Phone телефонный номер, соответствующий фамилии Name или сообщение об отсутствии информации */ write("Номер телефона: ",Phone), /* выводим значение переменной Phone */ readchar(_), /* ждем нажатия любой клавиши */ menu. /* возвращаемся в меню */ name_phone(Name,Phone):– phone(Name,Phone),!. name_phone(_,"Нет информации о телефонном номере"). /* если нужного факта во внутренней базе данных не нашлось, то вместо телефонного номера возвращаем соответствующее сообщение */
Если пользователь желает выполнить вторую операцию, то должна быть выведена фамилия абонента, если в нашей телефонной базе имеется соответствующий факт. Иначе выводится сообщение о том, что у нас нет такой информации.
Соответствующие предикаты будут выглядеть следующим образом:
m('2'):– write("Введите номер телефона"),nl, readln(Phone), phone_name(Name, Phone), write("Фамилия абонента: ",Name), readchar(_), menu. /* вызываем меню */ phone_name(Name,Phone):– phone(Name,Phone). phone_name("Нет информации о владельце телефона",_). /* если нужного факта во внутренней базе данных не нашлось, то вместо фамилии абонента возвращаем соответствующее сообщение */
Если пользователем была выбрана третья операция, то нужно дать ему возможность ввести фамилию и номер абонента, после чего добавить соответствующий факт в базу данных.
Это будет выглядеть следующим образом:
m('3'):– write("Введите фамилию"),nl, readln(Name), write("Введите номер телефона"),nl, readln(Phone), assert(phone(Name,Phone)), /* добавляем факт во внутреннюю базу данных */ menu. /* вызываем меню */
Если пользователь желает выполнить четвертую операцию, то нужно дать ему возможность ввести фамилию абонента и его новый телефонный номер, после чего удалить устаревшую информацию из телефонной базы (с помощью предиката retract) и добавить туда новую информацию (используя встроенный предикат assert).
Соответствующее этим рассуждениям предложение:
m('4'):– clearwindow, write("Введите фамилию"),nl, readln(Name), write("Введите новый номер телефона"),nl, readln(Phone), retract(phone(Name,_)), /* удаляем устаревшую информацию из внутренней базы данных */ assert(phone(Name,Phone)), /* добавляем новую информацию в телефонную базу */ menu. /* вызываем меню */
Если пользователем была выбрана пятая операция, то нужно узнать у него, например, номер (или фамилию) абонента, после чего удалить соответствующую информацию из внутренней базы данных, воспользовавшись предикатом retract.
Запишем это предложение:
m('5'):– write("Укажите номер телефона, запись о котором нужно удалить из телефонной базы"), nl, readln(Phone), retract(phone(_,Phone)), /* удаляем соответствующий факт из внутренней базы данных */ menu. /* вызываем меню */
Приведем полный текст программы.
DOMAINS /* раздел описания доменов */ name, number = String /* фамилию абонента и телефонный номер будем хранить в виде строк */ file=f /* файловый домен будем использовать для считывания с диска и записи на диск нашей телефонной базы */ DATABASE /* раздел описания предикатов внутренней базы данных */ phone(name, number) PREDICATES /* раздел описания предикатов */ name_phone(name, number) /* этот предикат находит номер телефона по фамилии абонента */ phone_name(name, number) /* этот предикат находит фамилию абонента по номеру телефона */ m(char) /* этот предикат реализует выполнение соответствующего пункта меню */ menu /* этот предикат реализует вывод меню и обработку выбора пользователя */ start /* этот предикат проверяет наличие файла с телефонной базой на диске и либо загружает факты из нее во внутреннюю базу данных, если такой файл существует, либо создает этот файл, если его не было */ CLAUSES /* раздел описания предложений */ name_phone(Name,Phone):– phone(Name,Phone),!.
name_phone(_,"Нет информации о телефонном номере"). /* если соответствующего факта во внутренней базе данных не нашлось, вместо телефонного номера возвращаем соответствующее сообщение */ phone_name(Name,Phone):– phone(Name,Phone). phone_name("Нет информации о владельце телефона",_). /* если соответствующего факта во внутренней базе данных не нашлось, вместо фамилии абонента возвращаем соответствующее сообщение */ menu:– clearwindow, /* очистка текущего окна */ write("1– Получение телефонного номера по фамилии "),nl, write("2 — Получение фамилии абонента по номеру телефона "),nl, write("3 — Добавление новой записи в телефонную базу."),nl, write("4 — Изменение номера абонента"),nl, write("5 — Удаление записи из телефонной базы"),nl, write("0 — Выйти"),nl, readchar(C), /* читаем символ с клавиатуры */ m(C). /* вызываем выполнение соответствующего пункта меню */ m('1'):– clearwindow, write("Введите фамлию"), nl, readln(Name), name_phone(Name, Phone), write("Номер телефона: ",Phone), readchar(_), menu. m('2'):– clearwindow, write("Введите номер телефона"),nl, readln(Phone), phone_name(Name, Phone), write("Фамилия абонента: ",Name), readchar(_), menu. m('3'):– clearwindow, write("Введите фамилию"),nl, readln(Name), write("Введите номер телефона"),nl, readln(Phone), assert(phone(Name,Phone)), /* добавляем факт во внутреннюю базу данных */ menu. m('4'):– clearwindow, write("Введите фамилию"),nl, readln(Name), write("Введите новый номер телефона"),nl, readln(Phone), retract(phone(Name,_)), /* удаляем устаревшую информацию из внутренней базы данных */ assert(phone(Name,Phone)), /* добавляем новую информацию в телефонную базу */ menu. m('5'):– clearwindow, write("Укажите номер телефона, запись о котором нужно удалить из телефонной базы"), nl, readln(Phone), retract(phone(_,Phone)), /* удаляем соответствующий факт из внутренней базы данных */ menu.
m('0'):– save("phones.ddb "), /* сохраняем телефонную базу в файл */ retractall(_)./* удаляем все факты из внутренней базы данных */ m(_):– menu. /* если пользователь по ошибке нажал клавишу, отличную от тех, реакция на которые предусмотрена, ничего плохого не произойдет, будет отображено меню еще раз */ start:– existfile("phones.ddb"),!, /* если файл с телефонной базой существует */ consult("phones.ddb "), /* загружаем факты во внутреннюю базу данных */ menu. /* вызываем меню */ start:– openwrite(f,"phones.ddb"), /* если файла с телефонной базой не существует, создаем его */ closefile(f), menu. /* вызываем меню */ GOAL /* раздел внутренней цели*/ Start
Листинг 13.1. Программа, реализующая компьютерный вариант телефонного справочника.
Пример. Другой распространенный вариант использования внутренних баз данных — это повышение эффективности программ за счет добавления уже вычисленных фактов в базу данных. При попытке вычислить предикат сначала проверяется, нет ли в базе данных уже вычисленного значения, и если оно там уже есть, то просто берется это значение. Если же ответа еще нет, он вычисляется обычным способом, после чего добавляется в базу данных для повторного использования. Эта техника еще называется мемоизация или табулирование.
Давайте разработаем табулированную версию предиката, вычисляющего число Фиббоначи по его номеру. В пятой лекции мы уже рассматривали предикат, вычисляющий числа Фиббоначи. Выглядел он следующим образом:
fib(0,1):–!. /* нулевое число Фиббоначи равно единице */ fib(1,1):–!. /* первое число Фиббоначи равно единице */ fib(N,F) :– N1=N–1, fib(N1,F1), /* F1 это N–1-е число Фиббоначи */ N2=N–2, fib(N2,F2), /* F2 это N–2-е число Фиббоначи */ F=F1+F2. /* N-е число Фиббоначи равно сумме N–1-го числа Фиббоначи и N–2-го числа Фиббоначи */
Чем плох этот вариант предиката, вычисляющего числа Фиббоначи? Получается, что при вычислении очередного числа происходит многократное перевычисление предыдущих чисел Фиббоначи, что не может не приводить к замедлению работы программы.
Изменим нашу программу следующим образом: добавим в нее раздел описания предикатов внутренней базы данных. В этот раздел добавим описание одного-единственного предиката, который будет иметь два аргумента. Первый аргумент — это номер числа Фиббоначи, а второй аргумент — само число.
Сам предикат, вычисляющий числа Фиббоначи, будет выглядеть следующим образом. Базис индукции для первых двух чисел Фиббоначи оставим без изменений. Для шага индукции добавим еще одно правило. Первым делом будем проверять внутреннюю базу данных на предмет наличия в ней уже вычисленного числа. Если оно там есть, то никаких дополнительных вычислений проводить не нужно. Если же числа в базе данных не окажется, вычислим его по обычной схеме как сумму двух предыдущих чисел, после чего добавим соответствующий факт в базу данных.
Попробуем придать этим рассуждениям некоторое материальное воплощение:
fib2(0,1):–!. /* нулевое число Фиббоначи равно единице */ fib2(1,1):–!. /* первое число Фиббоначи равно единице */ fib2(N,F):– fib_db(N,F),!. /* пытаемся найти N-е число Фиббоначи среди уже вычисленных чисел, хранящихся во внутренней базе данных */ fib2(N,F) :– N1=N–1, fib2(N1,F1), /* F1 это N–1-е число Фиббоначи */ N2=N–2, fib2(N2,F2), /* F2 это N–2-е число Фиббоначи */ F=F1+F2, /* N-е число Фиббоначи равно сумме N–1-го числа Фиббоначи и N–2-го числа Фиббоначи */ asserta(fib_db(N,F)). /* добавляем вычисленное N-е число Фиббоначи в нашу внутреннюю базу данных*/
Заметьте, что при каждом вызове подцели fib2(N2,F2) используются значения, уже вычисленные при предыдущем вызове подцели fib2(N1,F1).
Попробуйте запустить два варианта предиката вычисляющего числа Фиббоначи для достаточно больших номеров (от 30 и выше) и почувствуйте разницу во времени работы. Минуты — работы первого варианта и доли секунды — работы его табулированной модификации.
Справедливости ради стоит заметить, что существует другой вариант ускорения работы предиката, вычисляющего числа Фиббоначи, без использования баз данных.
Будем искать сразу два числа Фиббоначи.То, которое нам нужно найти, и следующее за ним. Соответственно, предикат будет иметь третий дополнительный аргумент, в который и будет помещено следующее число. Базис рекурсии из двух предложений сожмется в одно, утверждающее, что первые два числа Фиббоначи равны единице.
Вот как будет выглядеть этот предикат:
fib_fast(0,1,1):–!. fib_fast(N,FN,FN1):– N1=N–1,fib_fast(N1,FN_1,FN), FN1=FN+FN_1.
Если следующее число Фиббоначи искать не нужно, можно сделать последним аргументом анонимную переменную или добавить описанный ниже двухаргументный предикат:
fib_fast(N,FN):– fib_fast(N,FN,_).
