Главная » SQL, Базы данных » ДОКАЗАТЕЛЬНО-ТЕОРЕТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ БАЗ ДАННЫХ

0

Как описано в разделе 24.4, выражение представляет собой терм в следующей форме.

Al AND A2 AND . . . AND Am ⇒  Bl OR B2 OR … OR Bn

Здесь все компоненты А и в являются термами в такой форме.

r   (  xl,   х2,   . . .,   xt  )

Здесь r— предикат, a xl, х2, …, xt — фактические параметры этого предиката.)

В соответствии с работой [24.7], могут рассматриваться два описанных ниже важных частных случая этой общей конструкции.

1.   m  =   0, n  =   1

В данном случае рассматриваемое выражение может быть упрощенно представлено следующим образом.

⇒    В1

Иным образом, после удаления символа импликации это выражение  принимает следующий  вид.  r  (  xl,  х2,  …,  xt  )  Здесь  r  —  некоторый  предикат,  имеющий определенное  множество  фактических  параметров  xl,  х2,  .  .  .,  xt.  Если  все параметры  х  являются  константами, то  данное  выражение представляет собой основную аксиому, т.е. утверждение, которое  определенно является истинным. В терминах   баз  данных   такое   утверждение   соответствует   кортежу5    некоторой переменной   отношения   R.   Предикат   r   соответствует   смысловому   значению переменной отношения R, как описано в главе 6и в    других главах данной книги. Например, в базе данных поставщиков и деталей имеется переменная  отношения SP, смысловым значением которой является то, что указанный  поставщик (s#) поставляет  указанную  деталь  (р#)  в  указанном   количестве   (QTY).  Обратите внимание на то, что это смысловое значение  соответствует открытой правильно построенной формуле, поскольку оно включает ссылки на свободные переменные (s#, Р# и QTY). В отличие от этого, кортеж (SI, P1, 300), в котором все фактические параметры являются  константами, представляет  собой основную  аксиому,  или замкнутую    правильно   построенную   формулу,   которая   недвусмысленно показывает, что поставщик S1 поставляет деталь Р1 в количестве 300.

m >   0, п  =    1

В этом случае выражение принимает следующую форму.

Al   AND  A2   AND   …   AND  Am   ⇒ В

Эта форма может рассматриваться как дедуктивная аксиома; она дает (возможно неполное) определение предиката справа от символа импликации в терминах тех предикатов, которые находятся слева от этого символа (в качестве примера можно привести определение предикатаGRANDMOTHERJDF ИЗ предыдущего раздела).

Еще один вариант состоит в том, что такое выражение может рассматриваться как определение ограничения целостности (а используя  терминологию главы 9, его можно рассматривать по своему назначению как ограничение переменной отношения). Для примера предположим, что  переменная отношения поставщиков S имеет только два атрибута, s# и CITY. В таком случае приведенное ниже выражение представляет  ограничение, согласно которому атрибут CITY является функционально зависимым от S#. S ( s, cl ) AND S ( s, с2 )  ⇒ cl = с2  Обратите

внимание на то, что в данном примере используется встроенный предикат "=".

5 Или значению в некотором домене.

Как показывает приведенное выше описание, кортежи в отношениях {основные аксиомы), производные отношения (дедуктивные аксиомы) и ограничения целостности, вместе взятые, могут рассматриваться как частные случаи общей  конструкции — выражения. Теперь попытаемся определить, как все эти идеи могут привести к созданию доказательнотеоретического представления базы данных, о котором упоминалось в разделе 24.2.

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

■     Основополагающие домены содержат значения, или константы, которые согласно принятому предположению обозначают некоторые объекты "реального мира" (точнее, обозначают их в некоторой интерпретации, в том смысле этого понятия, который определен в разделе 24.4). Таким образом, они соответствуют предметной области.

■     Переменные отношения (точнее, заголовки переменных отношения) представля ют собой множество предикатов, или открытых правильно построенных формул, которые должны интерпретироваться в этой предметной области. Например, заго ловок переменной отношения SP определяет предикат "Поставщик s# поставляет деталь Р# в количестве QTY".

■     Каждый кортеж в заданной переменной отношения представляет собой конкрети зацию соответствующего предиката; это означает, что он представляет собой вы сказывание (замкнутую правильно построенную формулу, поскольку не содержит переменных), которое, безусловно, является истинным в данной предметной об ласти.

■     Ограничения целостности являются открытыми правильно построенными форму лами, интерпретируемыми в той же предметной области. Поскольку данные в базе не нарушают (т.е. не должны нарушать!) эти ограничения, то соответствующие ог раничения обязательно принимают значение TRUE при подстановке текущих зна чений из базы данных вместо их формальных параметров.

■     Кортежи и ограничения целостности могут совместно рассматриваться как мно жество аксиом, определяющих некоторую логическую теорию (неформально вы ражаясь, теория в логике представляет собой множество аксиом). А поскольку все эти аксиомы в данной интерпретации являются истинными, то по определению сама интерпретация является моделью указанной логической теории в том смысле, который указан в разделе 24.4. Обратите внимание на то, что, как упоминалось в том же разделе, модель может не быть уникальной; это означает, что любая кон кретная база данных может иметь несколько возможных интерпретаций, притом что все они с точки зрения логики будут в равной степени действительными.

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

смысловых значений, по крайней мере, в принципе6. Более того, обработка  запроса в модельно-теоретическом представлении по существу представляет собой процесс вычисления некоторой открытой правильно построенной формулы для определения того, подстановка каких значений вместо свободных переменных в этой ППФ повлечет за собой то, что ППФ примет значение TRUE в рамках этой модели.

На этом описание модельно-теоретического представления заканчивается.  Но  для того чтобы иметь возможность применять правила логического вывода, описанные в разделах 24.3 и 24.4, необходимо встать на иную позицию, которая заключается в том, что база данных явно рассматривается как некоторая логическая теория, т.е. как множество аксиом. В таком случае смысловым значением базы данных становится именно коллекция, состоящая из всех истинных утверждений, которые могут быть дедуктивно выведены из этих аксиом. Таким образом, смысловым значением базы данных становится множество теорем, которые могут быть доказаны на основании указанных аксиом. В этом и состоит доказательно-теоретическое представление. В данном представлении вычисление запроса преобразуется в процесс доказательства теоремы (во всяком случае, он является таковым с концептуальной точки зрения, а в целях повышения эффективности в системе, по всей вероятности, будут использоваться более общепринятые методы обработки запроса, как показано в разделе 24.7).

Примечание. Из сказанного в приведенном выше абзаце следует, что одно из различий между модельно-теоретическим и доказательно-теоретическим представлениями (на интуитивном уровне восприятия) состоит в том, что в модельно-теоретическом представлении база данных может иметь много смысловых значений, а в доказательно-теоретическом представлении она обычно имеет одно и только одно смысловое значение. Исключениями из этого правила  являются такие ситуации: во-первых, как было указано выше, в модельно-теоретическом варианте каноническое смысловое значение действительно является единственным значением, и, во-вторых, в любом варианте такое утверждение, что в доказательно-теоретическом представлении имеется только  одно смысловое значение, вообще говоря, становится неправильным, если база  данных включает какие-либо аксиомы с отрицаниями [24.5], [24.6].

В неформальном изложении общие сведения об аксиомах для данной конкретной базы данных (доказательно-теоретическое представление) приведены ниже [24.10].

1.  Основные аксиомы, соответствующие значениям в доменах и кортежам в базовых переменных отношения. Эти аксиомы составляют то, что иногда называют экстен сиональной базой данных (extensional database), в отличие от интенсиональной базы данных (intensional database), которая описана в следующем разделе.

2.  Аксиомы дополнения для каждой переменной отношения, согласно которым отсут ствие в рассматриваемой переменной отношения кортежа, допустимого по всем прочим признакам, может интерпретироваться как свидетельство того, что выска зывание, соответствующее этому кортежу, является ложным. (В действительности,

6  Но поскольку принято предположение, что база данных явно не содержит какой-либо отрицательной информации (например, высказывания в форме "NOT S# (S9) ", которое  означает, что S9 — это не номер поставщика), то должно также существовать "минимальное" или каноническое смысловое значение, представляющее собой пересечение всех возможных  моделей  [24.6]. Более того, в данном случае такое каноническое смысловое значение будет таким же, как и смысловое значение, предписанное базе данных в соответствии с доказательно-теоретическим представлением, о чем речь пойдет чуть позже.

такие аксиомы дополнения, вместе взятые, входят в состав предположения о замкнутости мира, которое уже рассматривалось в главах 6 и 9.) Например, тот факт, что переменная отношения поставщиков S не включает кортеж (S6, White, 45, Rome), означает, что является ложным такое высказывание: "Существует поставщик S6, работающий по контракту, имеющий имя white, статус 45 и находящийся в Риме".

3.  Аксиома уникальности имен, которая означает, что каждая константа отличима от всех других (т.е. имеет уникальное имя).

4.  Аксиома замыкания домена, которая означает, что не существует других констант,

отличных от тех, которые находятся в доменах базы данных.

5.  Множество аксиом (по существу, стандартных) для определения встроенного пре диката равенства. Эти аксиомы необходимы, поскольку все такие аксиомы, как аксиомы дополнения, уникальности и замыкания домена, используют предикат равенства.

В завершение этого раздела приведено краткое итоговое описание основных различий между этими двумя представлениями (модельно-теоретическим и  доказательно-теоретическим). Прежде всего, следует отметить, что с практической точки зрения различия между ними могут оказаться не столь уже значительными! (По крайней мере, если речь идет о современных СУБД.) Тем не менее, эти различия указаны ниже.

■     В результате применения аксиом для доказательно-теоретического представления (не считая основных аксиом) становятся явными некоторые допущения, которые при использовании интерпретации, основанной на модельно-теоретическом представ лении, были лишь неявными [24.10]. Обычно идет на пользу явная формулировка принятых допущений; более того, такие дополнительные аксиомы необходимо за давать явно для того, чтобы иметь возможность применять общие методы доказа тельства, такие как метод резолюции, описанный в разделах 24.3 и 24.4.

■     Заслуживает внимание то, что в списке аксиом нет упоминания об ограничениях целостности.  Причина такого упущения состоит в том, что (в доказательнотеоретическом представлении) после введения таких ограничений система преоб разуется в дедуктивную СУБД (см. раздел 24.6).

■     Доказательно-теоретическое представление обладает определенным изяществом (которое отсутствует в модельно-теоретическом представлении), поскольку оно обеспечивает единообразное восприятие многих конструкций, которые обычно рассматриваются как более или менее различные: базовые данные, запросы, огра ничения целостности (несмотря на сказанное в предыдущем пункте), виртуальные данные и т.д. Вследствие этого появляется возможность создания более единооб разных интерфейсов и более единообразных реализаций.

■     Кроме того, доказательно-теоретическое представление создает естественную ос нову для решения некоторых проблем, при столкновении с которыми в традици онных реляционных системах всегда возникали сложности. В частности, к ним относится обработка дизъюнктивной информации (например,"Поставщик S6 нахо дится либо в Париже, либо в Риме"), извлечение из базы отрицательной информа ции (например, "Кто не является поставщиком?") и обработка рекурсивных за просов (см. следующий раздел). Тем не менее, в данном последнем случае, по крайней мере, в принципе, отсутствуют причины, по которым нельзя было бы

расширить обычные реляционные системы для обработки таких запросов (и действительно, в некоторых коммерческих программных продуктах это уже сделано7. Дополнительная информация по этим темам приведена в разделах 24.6 и 24.7.

■   Наконец, как было указано Рейтером [24.10], доказательно-теоретическое  представление "обеспечивает правильную трактовку [дополнений к] реляционной модели для включения семантики реального мира в большем объеме" (как было отмечено в разделе 24.2).

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии