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

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

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

Начнем с повторного рассмотрения программы 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 (In 1, In 2, Out)? относительно программы 2.2. Имеется решение { In 1 = n3, In 2 = n5, 0ut = п 1}. Это решение подтверждает, что факты действительно описывают вентиль «И», и указывает входы и выход вентиля.

resistor (power, n 1).

resistor (power, n 2).

transistor (n 2, ground, n l).

transistor (n 3, n 4, n 2).

transistor (n 5, ground, n 4).

inverter (Input,Output) ¬

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

inverter (Input, Output) ¬

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

nand-gate (Input 1 ,Input 2 ,Output)

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

nand_gate (Input l, Input 2, Output) ¬

transistor (Input 1, X, Output),

transistor (Input 2, ground, X),

resistor (power, Output).

and_gate (Input 1 ,Input 2 ,Output)

Output является логическим «И» Input 1 и Input 2.

and_gate (Input l, Input 2, Output) ¬

nand_gate (Input 1, Input 2, X),

inverter (X, Output).

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

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