Введение в системы БД (542480), страница 240
Текст из файла (страница 240)
1. МОТНЕК ОГ( 'Капе', 'ВвССу' ) 2, МОТНЕК ОГ( 'Ве11у', 'Св11а' ) Часть Г'. Дополнительные аспекты Кроме того, дана ИГР-формула ("дедуктивная аксиома"), которая, по сути, является предложением Хорна. 3. МОТНЕВ ОР( х, у ) ВНО МОТНЕВ ОР( у, г ) =Ф ОВ)ГНОМОТНЕВ ОР( х, г ) Для упрощения работы с правилом резолюции следует исключить из предложения символ "~" и переписать предложение таким образом.
4. Нот МОТНЕВ ОР( х, у ) ОВ НОТ МОТНЕВ ОР( у, г ) ОВ ОВВНОМОТНЕВ ОР( х, г ) Далее необходимо показать, как доказывается утверждение, что Анна является бабушкой Селии, т.е. как ответить на запрос "Является ли Анна бабушкой Селии?", Для этого нужно начать с отрицания заключения, которое требуется доказать, и принять его как дополнительную предпосылку. 5. НОТ ОВЬНОМОТНЕВ ОР( 'Вдпе', 'Се11а' ) Теперь для применения правила резолюции необходимо систематически подставлять значения для переменных таким образом, чтобы можно было найти два предложения, содержащих %ту-формулу и ее отрицание.
Подобная подстановка вполне законна, поскольку все переменные неявно универсально квантифицированы. Следовательно, индивидуальные (неотрицаемые) %РР-формулы должны быть истинны для всех и для каждой допустимой комбинации значений этих переменных. Замечание Процесс поиска набора подстановок, которые позволяют совместить два предложения таким путем, называется унификацией. Для того чтобы проиллюстрировать описанный выше процесс, обратимся к примеру.
Прежде всего следует обратить внимание на то, что строки в пп. 4 и 5 содержат термы ОВ)гНОМОТНЕВ ОР(х,г) и НОТ ОВВНОМОТНЕВ ОР('аппе', 'Се11а') соответственно. Таким образом, в строке п. 4 нужно подставить значение 'йппе' вместо х и значение 'Се11а'— вместо г. После совмещения получится такой результат. б. НОТ МОТНЕВ ОР( 'Вппе', у ) ОВ НОТ МОТНЕВ ОР( у, 'Се11а' ) Строка п. 2 содержит выражение МОТНЕВ ОР('Мессу', 'Се11а'), поэтому можно подставить значение 'Мессу' вместо у в строке п.
б и после совмещения получить новое выражение. 7. НОТ МОТНЕВ ОР( 'Ьлпе', 'НеС1у' ) Совместив строки в пп. 7 и 1, получим пустое множество предложений ( ), т.е, противоречие. Следовательно, результатом выполнения исходного запроса будет ответ "Да, Анна является бабушкой Селии*'. ° Теперь можно проанализировать, как будет выполняться запрос "Кто является внучкой Анны?". Сложность поставленной задачи заключается, прежде всего, в том, что системе ничего не известно о внучках, она обладает информацией только о бабушках.
В этом случае можно было бы добавить еще одну ледуктивную аксиому, согласно которой г является внучкой х тогда и только тогда, когда х является бабушкой г (предполагается, что в рассматриваемой базе данных не содержатся сведения о мужчинах). Тогда исходный запрос можно перефразировать — "Чьей бабушкой является Анна?" — и использовать тот же набор предпосылок, что и прежде. Глава 23. Логические системы управления базами Данных 913 ). МОТНЕК ОР( 'Аппе', 'Веггу' ) 2.
МОТНЕК ОР( 'Весту', 'Се11а' ) 3. НОТ МОТНЕК ОР( х, у ) Ок НОТ МОТНЕК ОР[ у, г ) ОК ОКАНОМОТНЕК ОР( х, г ) Дополним его четвертой предпосылкой. 4. МОТ ОКАМОМОТНЕК ОР( 'Аппе', г ) ОК КЕЯОЬТ( г ) Интуитивно эта предпосылка может рассматриваться как утверждение о том, что либо Анна не является ничьей бабушкой, либо, наоборот, существует некая особа г, которая отвечает требованиям, предъявляемым к результату (поскольку Анна является бабушкой этой особы г).
Предполагая, что такая особа существует, далее следует ее найти. Сначала подставим значение 'Аппе' вместо х и х вместо г. Совместив строки в пп. 4 и 3, получим следующий результат. 5. НОТ МОТНЕК ОР( 'Алле', у ) ОК НОТ МОТНЕК ОР( у, г ) ОК КЕЯОЬТ( г ) Подставив значение 'Весту' вместо у и совместив строки в пп. 5 и 1, получим следующее. б. МОТ МОТНЕК ОР( 'Весту', г ) ОК КЕЯОЬТ( г ) Наконец подставив значение 'Се11а' вместо г и совместив строки в пп. б и 2, получим такой результат. 7.
КЕЯОЬТ( 'Се11а' ) Следовательно, Анна является бабушкой Селии. ° Замечание. Рассмотрим случай, когда задан дополнительный терм, как, например, показано ниже. МОТНЕК ОР ( 'Весту', 'Ре11а' ) Тогда на последнем этапе можно было бы подставить 'Ое11а' вместо г и получить в результате следующее выражение. КЕЯОЬТ ( 'Ое11а' ) Пользователю, конечно, желательно получить в результате оба имени. Таким образом, необходимо, чтобы в системе тщательно были выполнены операции унификации и резолюции с выводом всех возможных значений.
Однако технические детали организации такой работы системы в данной книге не рассматриваются. 23.5. Базы данных с точки зрения доказательно-теоретического подхода Как говорилось в разделе 23.4, предложением является выражение следующего вида. Л1 АМО Л2 АМО ... АНО Л ~ В1 ОК В2 ОК ... ОК Вл Здесь все Л и В являются термами указанного ниже вида, где х — предикат, а х1, х2, ..., хс — его аргументы. г ( х1, х2, ..., хг ), 914 Часть )'. Дополнительные аспекты В соответствии с (23.12] рассмотрим несколько важных типов этой общей конструкции.
° Случай 1. и = О, п = 1. В данном случае предложение может быть сведено к следующему простому виду. ~ 81 Его можно также записать в другом виде без символа импликации для некоторого предиката г с набором аргументов х1, х2, ..., х0. г ( х1, х2, ..., х0) Если все аргументы являются константами, то предложение представляет собой основную аксиому, т.е.
утверждение, которое однозначно является истинным. В терминах базы данных такое утверждение соответствует кортежу некоторой переменной-отношения Нз. Как неоднократно отмечалось в этой книге, предикат г соответствует "смысловому значению" переменной-отношения Н. Например, в базе данных поставщиков и деталей существует отношение БР, которое означает, что заланный поставщик (80) поставляет указанную деталь (Р$) в определенном количестве (ОТУ).
Обратите внимание, что это значение соответствует открытой чУГгформуле, так как содержит несколько свободных переменных (Яй, Р)) и ОТУ). И наоборот, кортеж ('Я1', 'Р1', 300), в котором все аргументы являются константами, представляет собой основную аксиому, или закрытую ЪУЕЕ-формулу, которая однозначно утверждает, что поставщик с номером '81' поставляет деталь с номером 'Р1' в количестве 300.
° Случай 2. и > 0, л = 1. В этом случае прелложение принимает вид Л1 БНО Л2 БНО ... БНО Л В и может рассматриваться как дедуктивная аксиома. Она дает, возможно, неполное определение предиката справа от знака следования в терминах, которые представлены слева (см. в качестве примера определение предиката ОНАНОНОТНЕН ОР). Кроме того, данное предложение может рассматриваться и как ограничение целостности — ограничение переменной-отношения, если использовать терминологию главы 8. Предположим, что в нашем примере отношение Я содержит только два атрибута: 8$ и С1ТУ.
Тогда приведенное ниже предложение выражает ограничение; атрибут С1ТУ функционально зависит от атрибута 80. Я ( в, с1 ) аНО Я ( в, с2 ) ~ с1 = с2 Здесь следует обратить внимание на использование встроенного предиката "=". Из вышеизложенного можно заключить, что кортежи в отношениях ("основные аксиомы"), выведенные отношения ("дедуктивные аксиомы") и ограничения целостности могут рассматриваться как особые случаи обшей конструкции предложения. Теперь рассмотрим, как эти идеи могут привести к упомянутому ранее "доказательно-теоретическому" представлению базы данных, упоминавшемуся в разделе 23.2. Или значению в некотором домене. 915 Глава 23. Логические сисгпемы управления базами Данных Традиционное представление базы данных может считаться молельно-теоретическим.
Согласно этой точке зрения база данных рассматривается как набор явных именованных переменных-отношений, каждая из которых содержит явный набор кортежей и явный набор ограничений целостности. Рассмотрим, почему такое представление может характеризоваться как.мадачьна-гпеорепгическае. ° Используемые домены содержат переменные значения или константы, которые используются для представления объектов "реального мира" (точнее, в некоторой интерпретации, в смысле, который подразумевался в разделе 23.4). Таким образом, они соответствуют "пространству рассуждений". ° Переменные-отношения (точнее, их заголовки) представляют набор предикатов, или открытых чч'ГГ-формул, которые должны быть интерпретированы в этом пространстве.
Например, заголовок переменной-отношения ЯР представляет предикат "Поставщик Яй поставляет деталь Р1 в количестве ДТг'". ° Каждый кортеж данной переменной-отношения представляет собой экземпляр соответствующего предиката, т.е. однозначно истинное в пространстве рассуждений утверждение (закрытую %ГГ-формулу, которая не содержит никаких переменных). ° Ограничения целостности также являются закрытыми ФГГ-формулами и интерпретируются в том же пространстве. Поскольку данные не нарушают (т.е. не должны нарушать!) ограничений целостности, эти ограничения также всегда являются истинными. ° Кортежи и ограничения целостности вместе могут рассматриваться как набор аксиом, задающих определенную логическую теорию (попросту говоря, под термином "теория" в логике подразумевается набор аксиом).
Поскольку в данной интерпретации все аксиомы истинны, такая интерпретация по определению является моделью этой логической теории в смысле, подразумеваемом в разделе 23.4. Следует заметить, что, как уже отмечалось в настоящем разделе, модель может быть не уникальной, т.е. база данных может иметь несколько возможных интерпретаций, каждая из которых допустима с логической точки зрения.
Следовательно, с молельно-теоретической точки зрения "смысловым значением" базы данных является модель в изложенном выше смысле термина "модель". А поскольку сугцествует несколько возможных моделей, в принципе, существует и несколько возможных смысловых значенийз. Более того, обработка запросов в модельно-теоретическом представлении является по существу процессом вычисления некоторой открытой формулы для определения, какие значения свободных переменных в этой чч'ГГ- формуле сводят ее к значению истина в данной модели. Для того чтобы применить правила вывода, описанные в разделах 23.3 и 23.4, необходимо использовать новую точку зрения, в соответствии с которой база данных явным образом рассматривается как некая логическая теория, т.е, как набор аксиом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
