Простые базы данных

Программирование баз данных

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

Начнем с повторного рассмотрения программы 1.1, библейской базы данных и ее расширения правилами, задающими семейные отношения. В самой базе данных имеются четыре основных предиката: отец/2, мать/2, мужчина/1 и женщина/1. Мы примем соглашение из теории баз данных и снабдим каждое отношение реляционной схемой, которая указывает роль каждой позиции в отношении (каждого аргумента в цели). Реляционными схемами для этих четырех предикатов будут соответственно отец(Отец, Ребенок), мать(Мать, Ребенок), мужчина(Человек) и женщина(Человек). Принятые мнемонические имена говорят сами за себя.

Будем придерживаться типографского соглашения о курсивном выделении реляционных схем. В правилах переменным даются содержательные имена, в то время как в вопросах – имена Х или Y. Многословные имена используются по-разному для переменных и предикатов. В случае переменной каждое слово начинается с прописной буквы, например: ПлемянницаИлиПлемянник; в случае имен функций и предикатов слова соединяются нижней чертой, например: конфликт_расписания.

Новые отношения строятся из этих основных отношений с помощью определения подходящих правил. Соответствующими реляционными схемами для отношений, введенных в предыдущей главе, являются сын(Сын, Родитель), дочь(Дочь, Родитель), родитель(Родитель, Ребенок) и внук(Внук, ДедИлиБабушка). С точки зрения логики несущественно, какие отношения определяются с помощью фактов, а какие – с помощью правил. Например, если соответствующая база данных содержит факты родитель, мужчина и женщина, то правила, определяющие отношения сын и дочь, остаются в силе. Для отношений, более не определяемых фактами, например отец и мать, следует ввести новые правила. Подходящими правилами будут

отец(Папа, Ребенок) ¬ родитель(Папа, Ребенок), мужчина(Папа).

мать(Мама, Ребенок) ¬ родитель(Мама, Ребенок), женщина(Мама).

Интересные правила могут появиться при превращении отношений, неявно присутствующих в базе данных, в явные. Например, поскольку нам известны отец и мать ребенка, то нам известно, у каких пар был потомок, или известны, в терминах Библии, прародители. Это отношение не задано явно в базе данных, однако простое правило может выявить эту информацию. Реляционная схема – прародители(Мужчина, Женщина).

прародители(Мужчина, Женщина) ¬

отец(Мужчина, Ребенок), мать(Женщина, Ребенок).

Правило означает: «Мужчина и Женщина являются прародителями, если есть ребенок, отцом которого является Мужчина, а матерью – Женщина».

Другим примером извлечения информации из более простых сведений является отношение «быть детьми одних родителей» – братья и сестры. Дадим правило для брат(Брат, ДетиОднихРодителей).

брат(Брат, ДетиОднихРодителей) ¬

родитель(Родитель, Брат),

родитель(Родитель, ДетиОднихРодителей),

мужчина(Брат).

Однако такое правило означает: «Брат является братом ДетейОднихРодителей, если Родитель является родителем Брата и ДетейОднихРодителей и Брат является мужчиной».

Определение отношения брат приводит к некоторой проблеме. Вопрос брат(Х, Х)? выполняется для любого ребенка Х мужского пола, что не согласуется с нашим пониманием отношения брат.

Для того чтобы исключить подобные утверждения из значения программы, введем предикат ¹ (Терм1, Терм2). Удобнее записывать этот предикат в обычном (инфиксном) виде. Таким образом. Терм1¹ Терм2 истинно, если Терм1 и Терм2 различны. Ограничимся пока примером термов, являющихся константами. В принципе этот предикат может быть определен с помощью таблицы Х ¹ Y для каждой пары различных индивидов X и Y из интересующей области. Рис. 2.1 представляет собой такую таблицу для программы 1.1.

авраам ¹ исаак. авраам ¹ аран. авраам ¹ лот.

авраам ¹ милка. авраам ¹ иска. исаак ¹ аран.

исаак ¹ лот. исаак ¹ милка. исаак ¹ иска.

аран ¹ лот. аран ¹ милка. аран ¹ иска.

лот ¹ милка. лот ¹ иска. милка ¹ иска.

Рис 2.1 Определение неравенства.

Новое правило для отношения брат:

брат(Брат, ДетиОднихРодителей) ¬

родитель(Родитель, Брат),

родитель(Родитель, ДетиОдних Родителей),

мужчина(Брат),

Брат ¹ ДетиОднихРодителей.

Чем больше отношений уже введено, тем проще определять новые сложные понятия. Программа 2.1 определяет отношения дядя(Дядя, ПлемянницаИлиПлемянник), дети_одних_родителей(ДетиОднихРодителей1, ДетиОднихРодителей2) и родственник(Родственник1, Родственник2).

Другое отношение, неявно содержащееся в семейной базе данных, – является ли женщина матерью. Это отношение определяется с помощью отношений мать/2. Новой реляционной схемой является мать(Женщина), которая определяется правилом

мать(Женщина) ¬ мать(Женщина, Ребенок)

Это означает: «Женщина является матерью, если у нее есть Ребенок». Заметим, что одно и то же предикатное имя мать используется для описания двух разных отношений мать. Предикат мать имеет в этих двух случаях различное число аргументов, т. е. различную арность. В общем случае одно и то же предикатное имя с различными арностями описывает различные отношения.

дядя(Дядя, Субъект) ¬

брат(Дядя, Родитель), родитель(Родитель, Субъект).

дети_одних_родителей(ДетиОднихРодителей1, ДетиОднихРодителей2) ¬

родитель(Родитель, ДетиОднихРодителей1),

родитель(Родитель, ДетиОднихРодителей2), ДетиОднихРодителей1 ¹ ДетиОднихРодителей2.

родственник(Родственник1, Родственник2) ¬

родитель(Родитель1, Родственник1),

родитель(Родитель2, Родственник2),

дети_одних_родителей(Родитель1, Родитель2).

Программа 2.1.Определение семейных отношений.

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

База данных, приведенная в программе 2.2, представляет собой упрощенное описание логического вентиля «И», изображенного на рис. 2.2. Факты изображают связи между отдельными резисторами и транзисторами, входящими в схему. Реляционная схема резистора – resistor(Вывод1, Вывод2), Канального транзистора – transistor(Затвор, Исток, Сток).

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

Рис. 2.2-Логическая схема.

Правила, относящиеся к функциональным компонентам схемы, описывают работу отдельных групп резисторов и транзисторов Схема описывает вентиль «И», в котором выходной сигнал является логическим «и» двух входных сигналов. Один из способов построения такого вентиля состоит в последовательном соединении вентиля «И-НЕ» и инвертора. Такой способ и использован в данной схеме. Реляционные схемы для этих трех компонентов – and_gate(Input1, Input2, Output), nand_gate(Input1, Input2, Output) и inverter(Input, Output).

Чтобы понять программу 2.2, давайте разберем правило для инвертора. Оно утверждает, что инвертор строится из транзистора с заземленным истоком и резистора, один вывод которого присоединен к источнику питания. Затвор транзистора является входом инвертора, а свободный вывод резистора следует соединить со стоком транзистора, – это соединение образует выход инвертора. Общие переменные используются для описания общих соединений.

Рассмотрим вопрос and_gate(In1, In2, Out)? относительно программы 2.2. Имеется решение {In1 = n3, In2 = n5, 0ut = п1}. Это решение подтверждает, что факты действительно описывают вентиль «И», и указывает входы и выход вентиля.

resistor(power, n1).

resistor(power, n2).

transistor(n2, ground, nl).

transistor(n3, n4, n2).

transistor(n5, ground, n4).

inverter (Input,Output) ¬

Output является инверсией Input.

inverter(Input, Output) ¬

transistor(Input,ground,Output), resistor(power,Output).

nand-gate(Input1,Input2,Output)

Output является логическим «И-НЕ» Input1 и Input2.

nand_gate(Inputl,Input2,Output) ¬

transistor(Input1,X,Output),

transistor(Input2, ground,X),

resistor(power, Output).

and_gate(Input1,Input2,Output)

Output является логическим «И» Input1 и Input2.

and_gate(Inputl,Input2,Output) ¬

nand_gate(Input1, Input2,X),

inverter(X,Output).

Программа 2.2. Схема логического вентиля «И».

Рис 2.3 Вентиль ИЛИ