4-7.3 Представления

Выражение реляционной алгебрь! можно интерпретировать как программу , которая вычисляет отношение R и печатает или как-то иначе воспроизводит его в виде результата. Однако возможна и другая интерпретация реляционного выражения. Его допустимо рассматривать как формулу, определяющую отношение, которое не строится до тех пор, пока эта формула не применяется к реальным отношениям, В терминологии БД такие формулы называются представлениями. Им обычно присваиваются имена, которые используются в других реляционных выражениях так, словно представления являются реальными отношениями.

Правила Datalog тоже иллюстрируют различие между запросом и представлением. Напомним, что предикаты или отношения, определяемые этими правилами, считаются интенциональными, т.е. выражают определения отношения, которые не должны существовать в экстенсиональной, или хранимой в памяти, форме. Представление эквивалентно интенциональному предикату. Точно так же, как интенциональные предикаты используются в телах правил, представление реализуется в качестве аргумента алгебраического выражения. Точно так же, как набор правил Datalog применяется к БД, состоящей из хранимых в ней отношений, представление вычисляется в случае необходимости.

4.7.4 Пустые значения

Часто возникает необходимость приписать значение компоненту кортежа, но при этом оно нам неизвестно. Например, можно знать, что Кевин Кестнср - кинозвезда, но при этом не знать даты его рождения. В то же время каждый кортеж отношения MovleStar имеет компонент birthdate. Как же зафиксировать его значение * Именно в таком случае применяется специальное значение NULL, называемое пустым знанете.к. В некотором смысле NULL ничем не отличается от других значений, но, в то же время, оно не является реальным значением. В частности, при соединении отношений два компонента NULL не считаются равными друг другу. Например, если кортежи, представляющие двух кинозвезд одного фильма, имеют в своих компонентах birthday значение NULL, это не значит, гто даты рождения этих кинозвезд должны совпадать.

Существует множество интерпретаций нулевых значений. Приведем наиболее распространенные из них.

1. Значение неизвестно: известно, что здесь есть какое-то значение, но неизвестно, какое именно. Примером такой интерпретации является неизвестная дата рождения, о чем только что шла речь.

2. Значение не применимо: нет значения, которое в данном случае имело бы смысл. Например, если отношение MovieStar имеет атрибут spouse (супруг, супруга), кортеж, представляющий кинозвезду, обязательно имеет в этом атрибуте нулевое значение, и не потому, что неизвестно имя супруга или супруги, а потому, гго их просто не существует.

3. Значение скрыто: у нас нет полномочий знать используемое здесь значение. Например, засекреченный номер телефона может быть представлен в компоненте phone значением NULL.

4.8 Итоги

+ Реляционная алгебра. Эта алгебра - важная форма языка запросов для реляционной модели. Главными ее операторами являются объединение, пересечение, разность, выбор, проекция, декартово произведение, натуральное соединение, тета-соединение и переименование

4.9 Литература к главе 4

Реляционная алгебра составляет предмет исследований ставшей уже классической статьи [4], посвященной реляционном модели. Но у языков запросов такого единого источника нет. В одной из своих ранних статей по реляционной модели [5] Кодд ввел форму первопорядковой логики - ратциоиное исчисление. Это исчисление - язык выражений, во м1югом сходный с реляционной алгеброй и фактически равный ей по своей выразительной силе, что и доказывается в [5].

Появление Datalog, который выглядит скорее как набор правил, было навеяно языком программирования Prolog. Однако Datalog выразительнее peJHiuHOHHoro исчисления, поскольку содержит рекурсии. Книга [6] в основном посвящена развитию логики как языка запросов, а в [2] эти же идеи рассматриваются в контексте CHCTcvi БД. Оригинальная статья [8] посвящена примененм.ю запросов для выраже-ни.ч ограничений.

Мысль о том, что стратифицированный подход позволяет сделать правильный ЕЬ[Сор фиксированной точки, сформулирована в [3], а идея применения такого под-ода к оценке правил Daialog реализована в fl, 7 и Щ. Дополнительную информацию о стратифицированном отрицании, о связи между реляционной алгеброй. Daialog и реляционным исчислением, а также вычислений правил Datalog с отрицанием и без от(ншаиия можно найти в J91.

1. Apt, К. R., Н. RIair and А. Walker, Towards а theory of declarative knowledge , in Ftmndatious of Deductive Databases and Logic Programming (J. Minker, ed.) pp. S9-I48, Morgan-Kaufmann, San Fiancisco, 198S.

* Daialog. Эта форма логики - важный тип языка запросов для реляционной модели. В Daialog записываются правила, в которых предикат или отношение определяется в терминах тела, состоящего из подцелей. Голова и подцели правила являются атомами, а атом состоит из (возможно, отрицательного) предиката, применяемого к некоторому числу аргументов. Все запросы, представимые в реляционной алгебре, можно записать и в Datalog.

+ Рекурсивный Daialog. Правила Datalog могут быть рекурсивны.ми, что позволяет определять отношение в его собственных термииа.х. Смысл рекурсивных прав1ы Datalog определяется наименьшей фиксированной точкой - наименьшим множеством кортежей для определяемого отношения, делающим голову npaeiuia в Т0Ч1ЮСТИ равной тому, что следует из его тела.

Стратифицированное отрицание. Когда рекурсия включает в себя отрицание, наименьшая фиксированная точка может не быть уникальной, а правилам Datalog в отдельных случаях невозможно придать приемлемый смысл. Требование стратифицированного отрицания запрещает применение отрицания внутри рекурсии. Для каждого правила Datalog такого типа существует одна наименьшая фиксированная точка (возможно, несколько таких точек). Эти точки определяют общепринятый смысл данных правт1.

* Отношения как мульти.тожества. В коммерческих системах БД отношения действительно являются мультимножествами, в которые один и тот же кортеж может входить много раз. Операции реляиионной алгебры на множествах можно раоцростраиить и на мультимножества, однако некоторые алгебраические законы для мультимножеств не действуют.

ф- Отношения в ксммерческих системах. Помимо мультимножесгпенной модели отнои1ениЙ, коммерческие системы используют операции, отсутствующие в реляционной алгебре или Datalog: введение, удаление и изменение кортежей п отношениях, агрегацию отношений и пустые значения в кортежах.

4.9 Литература к главе 4 197

2. Bancilhon, F. and R. Ramakrishnan, An amateurs introduction to recursive query-processing strategies , ACM SIGMOD Intl. Conf. on Management of Data, pp. 16-52, 1986.

3. Chandra, A. K. and D. Hare!, Structure and complexity of relational queries , J. Computer and System Sciences 23:1, pp. 99-128.

4. Codd, E. F., A relational model for large shared data banks . Comm. ACM 13:6, pp. 377-387, 1970.

5. Codd, E. F., Relational completeness of database sublanguages , in Database Systems (R. Riistin, ed.) Prentice Hall, Engelwood Cliffs, NJ, 1972.

6. Callaire, H. and J. Minker, Logic and Databases, Plenum Press, New York, 1978.

7. Naqvi, S., Negation as failure for first-order queries , Proc. Fifth ACM Symp. on Principles of Database Systetns, pp. 114-122, 1986.

8. Nicolas, J.-M., Logic for improving integrity checking in relational databases . Acta Informatica 18:3, pp. 227-253, 1982.

9. Ullman, J. D., Principles cf Database and Knowledge-Base Systems, Volume!, Computer Science Press, New York, 1988,

10. Van Gelder, A., Negation as failure using tight derivation for general logic programs , in Foundations of Deductive Databases and Logic Programming (J. Minker, ed.) pp. 149-176, Morgan-Kaufmann, San Francisco, 1988.