Введение в системы БД (542480), страница 244
Текст из файла (страница 244)
1чЕ 1хг СОМР На следующей итерации переменная-отношение йЕя окажется пустой и выполнение цикла завершится. На этом заканчивается краткий обзор стратегий рекурсивного выполнения запросов. В опубликованной литературе можно найти множество более сложных подходов, однако их описание явно выходит за рамки этой книги, в которой преслелуется совсем другая цель. Более детально изучить эти подходы и получить все необходимые для их понимания основные сведения можно, обратившись к 123.! 61-[23.43). 23.8. Резюме На этом завершается краткое введение в СУБД, основанные на логике. Хотя рассмотренные здесь идеи еше не получили широкого распространения в научном мире, некоторые из них уже нашли свою реализацию в коммерческих продуктах, в частности это относится к некоторым методам оптимизации.
Определенные потенциальные преимушества этой сравнительно новой концепции, представляющей значительный интерес, описаны в различных разделах данной главы. Однако здесь не было упомянуто еше одно преимущество: логика может быть использована как основа для поистине полной интеграции между базами данных и языками программирования общего назначения. Другими словами, вместо не совсем элегантного подхода с применением "внедряемого подъязыка данных" (который используется во многих современных СУБД, поддерживающих язык ЯЯЬ) этот полход предполагает наличие единого языка, основанного на логике. В таком случае "данные являются данными" независимо от того, хранятся ли они в совместно используемой базе данных или локально по отношению к некоторому приложению.
(Конечно, на пути к этой цели потребуется преодолеть множество препятствий; и прежде всего весьма важно убедить специалистов в области информационных технологий в том, что логика может служить основой для создания языков программирования общего назначения.) Подытожим сведения, представденные в данной главе. Она начиналась с краткого обзора исчисления высказываний и исчисления предикатов с введением некоторых основных понятий, перечисленных ниже. 930 Часть К Дополнительные аспекты ° Интерпре~ация набора 1нГГ-формул — это комбинация пространства рассуждений, отображения индивидуальных констант из этих Ъ'ГГ-формул на объекты в этом пространстве и набора заданных значений для предикатов и функций, содержащихся в этих %ГГ-формулах.
° Модель для набора %ГГ-формул — это интерпретация, для которой все %ГГ- формулы в наборе истинны. В общем случае для данного набора %ГГ-формул может существовать любое количество моделей. ° Доказательство — это демонстрация того, что данная %ГГ-формула д (заключение) является логическим следствием некоторого заданного набора 'ххГГ-формул Г1, 12, ..., бл (предпосылок).
В качестве примера рассматривался один из методов доказательства под названием резолюция и унификация. Затем обсуждался доказательно-теоретический подход к базам данных. При таком подходе база данных рассматривается как комбинация экстенсиональной и интенсиональной баз данных. Экстенсиональная база данных содержит основные аксиомы, т.е. данные базы (говоря обобщенно), а интенсиональная — ограничения целостности и дедуктивные аксиомы, т.е, представления (опять же, говоря обобщенно). В этом случае "смысловое значение" базы данных определяется набором теорем, которые должны быть выведены из аксиом, а выполнение запроса становится, по крайней мере концептуально, процессом доказательства теоремы. Дедуктивной СУБД называется СУБД, в которой поддерживается подобный доказательно-теоретический подход. Одно совершенно очевидное отличие языка )Зага!ой от традиционных реляционных языков — возможность поддержки рекурсивных аксиом, а значит, и рекурсивных запросов.
При этом не существует никаких принципиальных ограничений на расширение соответствующим образом традиционной реляционной алгебры и исчисления (см. обсуждение оператора ТСьОЯЕ в главе б)ь. Также рассматривались некоторые простые методы выполнения таких запросов. В заключение отметим, что в начале главы было перечислено несколько терминов, например логическая СУБД, дедуктивная СУБД и т.д., которые часто встречаются в современной научной литературе (а также в рекламных материалах).
Для прояснения смысла этих терминов ниже приводится их краткое описание, Хотя следует заметить, что единого мнения по этому поводу не существует и в разных публикациях можно встретить совершенно разные определения. ° Рекурсивная обработка запросов Этот тип обработки предусматривает анализ н отчасти оптимизацию запросов, которые по определению являются рекурсивными (см. раздел 23.7).
° База знаний. Этот термин иногда используется для так называемой интенсиональной базы данных, которая содержит правила (ограничения целостности и дедуктивные аксиомы), тогда как экстенсиональная база данных состоит из собственно данных базы. Однако многими авторами термин "база знаний" употребляется для обозначения комбинации экстенсиональной и интенсиональной баз данных, за исключением и В В этой связи интересно отметить, чтп в реляционных СУБД всв жв необходимо (хатл и нвлвна) выполнять рекурсивную обработку, поскольку в каталоге может садержатьсл рекурсивна структурираваннал информация Например, определения одних представлений мсгут быть выражены на основе определений других представлений 931 Глава 23. Погические системы управления базами данньп того, что (как, например, утверждается в (23.10)) "база знаний часто содержит сложные объекты, такие как классические отношения" (см.
часть Ч1, где рассматриваются "сложные объекты" ). Наконец в системах на основе естественных языков этот термин имеет совсем другое специфическое значение, поэтому, видимо, лучше вообше избегать его использования. ° Знания. То, что содержится в базе знаний. Исходя из такого определения для объяснения термина "знания" необходимо вернуться к предыдущему абзацу. ° Система управления базой знаний. Программное обеспечение, которое управляет базой знаний.
Данный термин обычно используется как синоним дедуктивной СУБД (см. ниже). ° Дедуктивная СУБД СУБД, в которой предусмотрена поддержка доказательно- теоретического подхода. В частности, в таких СУБД можно вынес~и дополнительную информацию из экстенсиональной базы данных с помошью инференциальных (т.е. дедуктивных) правил, которые хранятся в интенсиональной базе данных. В дедуктивной СУБД почти всегда поддерживаются рекурсивные правила, а это значит, что возможно выполнение рекурсивных запросов.
° Дедуктивная база данных (использовать этот термин нежелательно). База данных, управляемая дедуктивной СУБД. ° Экспертная СУБД. Синоним дедуктивной СУБД. ° Экспертная база данных (использовать этот термин нежелательно). База данных, которая находится под управлением экспертной СУБД. ° Инференциальная СУБД. Синоним дедуктивной СУБД. ° Сиаиема, основанная на логике. Синоним дедуктивной СУБД.
° Логическая база данных (использовать этот термин нежелательно). Синоним дедуктивной базы данных. ° Логика как модель данных. Модель данных состоит из обьектов, правил целостности и операторов. В дедуктивной СУБД все они представлены в одной и той же форме — как аксиомы логического языка типа Оага)од. Действительно, как обьясняется в разделе 23.6, база данных в такой системе может рассматриваться как логическая программа, содержашая аксиомы всех трех видов.
Следовательно, можно утверждать, что в такой системе абстрактная модель данных является логической. Упражнения 23.!. Используя метод резолюции, определите, являются ли приведенные ниже метаутверждения правильными доказательствами в исчислении высказываний. а) А ~ В, С ~ В, 0 ~ ( А ОК С ), Р )- В б) ( А =ь В ) АКО ( С ~ 0 ), ( В =ь Е АВО 0 =ь Г ), КОТ ( и ййо Г ), А =ь С )- ВОТ А в) ( А ОК В ) ~ О, 0 =ь ВОТ ( Е ОК и ), ВОТ ( В ККО С ККО Е ) ~ Кот ( и ~ Вот ( с кио н ) ) 23.2. Преобразуйте следуюшие %г г-формулы в стандартную форму. 932 Часть у'. Дополнительные аспекты а) РОНАЬЬ х ( РОНАЬЬ у (р(х,у) =ьЕХТЯТЯг(а(х, г) ) ) ) б) ЕХ1БТЯ х ( ЕХ1ЯТБ у ( р ( х, у ) =ь РОНАЬЬ г ( а ( х, г ) ) ) ) в) ЕХ1ЯТБ х ( ЕХ1ЯТЯ у ( р ( х, у ) =» ЕХ1ЯТЯ г ( а ( х, г ) ) ) ) 23.3. Ниже приводится достаточно стандартный пример логической базы данных.
ИАИ ( 'Абаи' ) ИОМАИ ( 'Ече' ) ИАМ ( 'Са1п' ) МАИ ( 'АЬе1' ) МАИ ( 'ЕпосЬ' ) 'Абаи', 'Са1п' ] 'Абаи', 'АЬе1' ) 'Ече', 'Са1п' ) 'Ече', 'АЬе1' 'Са1п', 'ЕпосЬ' ) РАНЕИТ ( РАНЕИТ ( РАНЕИТ ( РАНЕИТ ( РАНЕИТ ( РАТНЕН ( х, у ) ~ РАНЕИТ ( х, у ) АИО ИАМ ( х ) ИОТНЕН ( х, у ) ~ РАНЕИТ ( х, у ) АИО ИОИАИ ( х ) Б1ВЬТИО ( х, у ) е= РАНЕИТ ( г, х ) АИЭ РАНЕИТ ( г, у ) ВНОТНЕН ( х, у ) е= Б1ВЬ1ИО ( х, у ) АИО ИАИ ( х ) Б1ЯТЕН ( х, у ) ~ Б1ВЬ|ИБ ( х, у ) АИО ИОИАИ ( х ) 933 Глава 23.
Логические системы управления базами Данных АИСЕБТОН ( х, у ) е= РАНЕИТ ( х, у ) АИСЕБТОН ( х, у ) ~ РАНЕИТ ( х, г ) АИО АИСЕЯТОН ( г, у ) Используйте метод резолюции, чтобы ответить на следующие запросы. а) Кто является матерью Каина ('Са1п')? б) Кто является братом или сестрой (Я(Ы(пЕ) Каина? в) Кто является братом (Вгогйег) Каина? г) Кто является сестрой (Я(згег) Каина? д) Кто является наследником (Апсемог) Еноха ('ЕпосЬ')? 23.4. Дайте определение терм инам интерпретацвя и модель. 23.5. Напишите набор аксиом языка Рага!оЕ только для части определений базы данных поставщиков, деталей и проектов. 23.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
