КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Простые базы данных
Программирование баз данных
Имеются два основных применения логических программ: построение логической базы данных и работа со структурами данных. Логическая база данных строится из множества фактов и правил. Покажем, как множество фактов может определять отношения, так же как в реляционных базах данных. Мы покажем, как правила могут определять сложные реляционные вопросы, также как в реляционной алгебре. Таким образом, функциональные зависимости, связанные с реляционными базами данных, могут выражаться логическими программами, составленными из фактов и правил весьма ограниченного вида. Начнем с повторного рассмотрения программы 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 Вентиль ИЛИ
Дата добавления: 2014-01-07; Просмотров: 1031; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |