Expansion of codd algebra operations with recursive objects.pdf Реляционная база данных с математической точкизрения - это конечный набор конечных отношений про-извольной арности над заранее определенными множе-ствами элементарных данных. Другими словами, реля-ционная база данных (точнее, любое ее состояние) - этоконечная модель (для заданных отношений) в смыслематематической логики. Над отношениями модели мо-жно осуществлять различные операции, исследованиекоторых становится областью приложений математи-ческой логики и современной алгебры.Все данные, согласно реляционной модели, рас-сматриваются как хранимые в таблицах, в которых ка-ждая строка имеет один и тот же формат. Каждая стро-ка в таблице представляет некоторый объект реальногомира или соотношение между объектами.Реляционный подход к представлению модели дан-ных, разработанный Коддом в 1970 г., получил огром-ную известность благодаря простоте основных идей истрогому формальному теоретическому фундаменту.Реляционная модель описывается в понятиях классиче-ской алгебры, математической логики, теории форма-льных систем и теории графов. Данное обстоятельствообеспечивает развитие эффективных формальных ме-тодов проектирования баз данных. Со времени появле-ния первых работ Кодда [1] по реляционной моделиданных круг задач по созданию баз данных расширял-ся, что повлекло за собой разработку новых методовмоделирования реляционных баз данных и усовершен-ствование классической реляционной модели данных.В настоящее время существует несколько основныхнаправлений исследований в области реляционногоподхода. Одно из направлений состоит в расширениисферы его применения путем модификации теоретиче-ской базы реляционной теории, что позволяет исполь-зовать новые свойства и понятия для создания болееполного и естественного описания предметной области.Традиционная (классическая) алгебра Кодда позво-ляет манипулировать обычными плоскими таблицами.Однако пользователям часто приходится иметь дело ссодержательно рекурсивными понятиями, для которыхалгебра Кодда не работает, следовательно, возникаетпотребность в доопределении этой алгебры.Рекурсивным называется объект, формальное определе-ние которого содержит ссылку на себя. Это есть эквисоеди-нение особого вида. Заметим, что кортеж не может ссылать-ся на самого себя ни непосредственно, ни опосредованно.Расширим реляционную алгебру, переопределивпонятие таблицы следующим образом:Определение. Рекурсивная таблица - это фиксиро-ванный (неограниченный) набор кортежей (неограни-ченной длины), отвечающих следующим условиям:− C = - это кортеж-тип, гдевсе атрибуты-имена ai - попарно различны; при этом Сназывается основным кортежем или основой;− таблица Т, составленная конечным набором по-парно различных основных кортежей-значений, назы-вается основной таблицей;− обобщенной таблицей основной таблицы Т называ-ется конечная совокупность рекурсивных кортежей-зна-чений Cr основной таблицы, определяемых основнымкортежем-типом С таблицы Т, следующим образом:а) кортежи-значения Cr обобщенной таблицы по-парно различны;б) каждый кортеж Cri - суть mi-кратно (mi ≥1) по-вторенный набор атрибутов-значений , таких, что aik∈Dk(1≤k≤n)основного кортежа С и для любых ij никакие два под-кортежа и не совпадают;в) в любом кортеже обобщенной таблицы ссылоч-ный атрибут когда-нибудь принимает значение null (пу-стую ссылку).Пусть в обобщенной таблице Т стандартным образомопределены ключевой набор К и индексный набор I, такие,что, D(K) = D(I); KI = 0; определено отображение R:IK,причем, очевидно, неподвижной точкой транзитивного за-мыкания R* является значение null ссылочного атрибута.Тогда рекурсивным эквисоединением таблицы Т поотношению R называется операция, результатом кото-рой выступает обобщенная таблица Tr, такая, что длякаждого её кортежа - значения Cr, состоящего более чемиз двух подкортежей основной таблицы :а) I(cm) = null;б) I(ck−1) = K(ck), где k < m.Итак, мы расширили традиционную алгебру Кодда,переопределив понятие таблицы.В классической интерпретации реляционная алгеб-ра представляет собой совокупность операций над от-ношениями (таблицами). В статье, опубликованной вжурнале Communication of the ACM [2], Кодд опреде-лил множество таких операций и доказал, что это мно-жество обладает свойством реляционной замкнутости.Полная алгебра состоит из двух групп операций:1. традиционных операций над множествами (объе-динение, пересечение, вычитание и декартово произ-ведение);2. специальных реляционных операций (проекция,соединение и деление).Все операции предложенного выше набора облада-ют очевидной и простой интерпретацией.При выполнении операции объединения двух от-ношений R и S, обозначаемой как R∪S, производитсяотношение, включающее все кортежи, входящие хотябы в одно из отношений-операндов.Операция пересечения двух отношений R и S, обо-значаемая как RS, производит отношение, включаю-щее все кортежи, входящие в оба отношения-операнда.Отношение, являющееся разностью двух отноше-ний R и S, обозначаемое как R\S, включает все кортежи,входящие в отношение − первый операнд R, такие, чтони один из них не входит в отношение, являющеесявторым операндом S.При выполнении прямого произведения двух отноше-ний R и S, обозначаемого как R×S, производится отноше-ние, кортежи которого являются конкатенацией (сцепле-нием) кортежей первого R и второго S операндов.Результатом ограничения отношения R по некото-рому условию Cond является отношение, включающееподкортежи отношения R, удовлетворяющие этомуусловию Cond. Синтаксис операции: R where Cond.При выполнении проекции отношения R на задан-ный набор его атрибутов S производится отношение,кортежи которого производятся путем взятия (с учетомвозможных повторяющихся кортежей) соответствую-щих значений из кортежей отношения R. Синтаксисоперации: ƒ [s] (R).При соединении двух отношений R и S, обозначае-мом как R►◄S, по некоторому условию образуетсярезультирующее отношение, кортежи которого явля-ются конкатенацией кортежей первого и второго отно-шений и удовлетворяют этому условию.У операции реляционного деления два операнда −бинарное R и унарное отношения S. Результирующееотношение R : S состоит из одноатрибутных кортежей,включающих значения первого атрибута кортежейпервого операнда, таких, что множество значений вто-рого атрибута (при фиксированном значении первогоатрибута) совпадает с множеством значений второгооперанда.Операция переименования производит отношение,тело которого совпадает с телом операнда, но именаатрибутов изменены. Оператор переименования атри-бутов имеет следующий синтаксис: [R last/R new] , гдеR last − исходные имена атрибутов, R new − новые име-на атрибутов.Поскольку результатом любой реляционной опера-ции является некоторое отношение, можно образовы-вать реляционные выражения, в которых вместо отно-шения-операнда некоторой реляционной операции на-ходится вложенное реляционное выражение.Анализ действия этих операций применительно крекурсивным таблицам показывает, что построенноерасширение алгебры Кодда является замкнутым.Примером может служить реализация структуры любойорганизации, в которой одному служащему подчиняютсянесколько других служащих. На рис. 1 представлен примеррекурсивной зависимости в отношении «Служащий».Рис. 1. Пример рекурсивнойВ теореме доказано, что результат любой алгебраи-ческой операции сам по себе является отношением всмысле введенного выше определения. Именно этосвойство замкнутости и допускает вложенность выра-жений реляционной алгебры; более того, такая вло-женность может достигать любой глубины. Перечис-ленные выше свойства делают алгебру реляционно-замкнутой.Исходя из этого, для преобразования рекурсивныхотношений следует добавить в отношения рекурсивныевнешние ключи. Описанный процесс преобразованиякаждого из этих конструкций в атрибуты реляционныхтаблиц гарантирует, что они будут зависеть только отключевых атрибутов. Следовательно, каждая получен-ная рекурсивная модель данных гарантированно будетиметь четвертую нормальную форму. Таким образом,разработанный аппарат может использоваться в каче-стве теоретической базы при построении новых струк-тур баз данных с использованием современных средствпроектирования.

Скачать электронную версию публикации