Про повноту та єдиність універсального каркаса в реляційній моделі даних
Ideas about routes for normalization in the universal framework of relational databases and their topology are introduced. A theorem about the completeness and uniqueness of the relational framework is formulated and proved.
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2010
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/106903 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866301907902922752 |
|---|---|
| author | Panchenko, B. E. Pysanko, I. M. |
| author_facet | Panchenko, B. E. Pysanko, I. M. |
| author_sort | Panchenko, B. E. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-06T12:28:40Z |
| description | Ideas about routes for normalization in the universal framework of relational databases and their topology are introduced. A theorem about the completeness and uniqueness of the relational framework is formulated and proved. |
| first_indexed | 2025-07-17T10:21:44Z |
| format | Article |
| fulltext |
© Б.Е. Панченко, И.Н. Писанко, 2010
Системні дослідження та інформаційні технології, 2010, № 3 25
УДК 004.652
О ПОЛНОТЕ И ЕДИНСТВЕННОСТИ УНИВЕРСАЛЬНОГО
КАРКАСА В РЕЛЯЦИОННОЙ МОДЕЛИ ДАННЫХ
Б.Е. ПАНЧЕНКО, И.Н. ПИСАНКО
Введено представление о путях нормализации в универсальном каркасе реля-
ционных баз данных и о топологии этих путей. Сформулирована и доказана
теорема о полноте и единственности реляционного каркаса.
ВВЕДЕНИЕ
Методики конструирования схемы реляционных баз данных ограничивают-
ся классической парадигмой Кодда [1, 2] со всеми ее расширениями, уточ-
нениями, модификациями и обобщениями, время от времени появляющими-
ся вплоть до настоящего момента [3]. Попытка Дейта и Дарвена [4] создать
формальную «надстройку» над реляционной моделью, отвечающую совре-
менным реалиям и требованиям, остается абстрактным решением, не выхо-
дящим в область практического применения. Уже традиционным стало
построение либо модели «сущность-связь» (ER-модель) [5] либо
т.н. семантической объектной модели (SOM) и последующий «перевод» по-
лучаемых орграфов-схем или соответственно семантических структур в
реляционные схемы [6, 7]. Практика такой «трансляции» считается эф-
фективной не только в методическом плане, но и по затратам времени и
усилий на построение логической структуры баз данных. Вместе с тем эту
практику отличает известная локальность построений, отсутствие универ-
сальности, приводящее к сложностям при модификации структуры базы
данных, вплоть до необходимости тотального редизайна структуры [8, 9].
Локальность ER/SOM-построений заключается, прежде всего, в работе с
фиксированным графом-схемой либо c заданными множествами семан-
тически определенных (или «четких») объектов. Это сказывается на гибко-
сти и модифицируемости таких построений.
Дополнительные затруднения концептуального характера связаны с
нечеткостью ключевых определений «атрибут», «сущность» и «объект», а
также с отсутствием общепринятой аксиоматики. Строгие алгебраические
определения понятий по типу [10, 11], которые для ER/SOM-построений
являются ключевыми, фактически отсутствуют. Это указывает на то, что
ER/SOM-построения не приспособлены для создания универсальных струк-
турных схем, которые были бы формально полны и непротиворечивы. И
ER-модель и SOM-модель дают не столько удобный и эффективный, сколь-
ко привычный и безальтернативный инструментарий для конструирования
логической структуры баз данных.
От гипотетических универсальных построений можно ожидать боль-
шей эффективности как минимум в части модифицируемости логической
структуры баз данных, а само существование базовой универсальной схемы
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 26
(назовем ее α -схемой) является не только интуитивно допустимым, но и
необходимым. В данной работе мы отмечаем лишь некоторые особенности
α -схемы, а также выявляем и анализируем несколько важных соответствий
между свойствами α -схемы и традиционных реляционных схем.
ПОСТАНОВКА ЗАДАЧИ
Пусть }{ ia — конечное множество атомарных сущностей (объектов) в
смысле [9]. Там под атомарностью понимается унарное формирование мно-
жества атрибутов этой сущности (объекта), то есть одноместный предикат,
объединяющий это множество. Тогда n -местным j -предикатом ( )i
n
j aP ,
принимающим истинное значение, ( ) 1=i
n
j aP (многоместным предикатом),
очевидно, моделируется формирование составных (пост-связных) сущно-
стей. Комбинирование атрибутов ia порождает полную совокупность }{ lr
реляционных схем, представляющих собой именованные отношения. В
свою очередь, комбинирование реляционных схем ir порождает полную
совокупность схем }{ jD реляционных баз данных:
}{}{}{ jli Dra ⇒⇒ . (1)
Выражение (1) представляет собой ядро α -схемы. Сразу следует отме-
тить ключевое отличие между α -схемой и ER/SOM-построениями: для за-
данного множества атрибутов в ER/SOM-моделях никогда не задействованы
полные совокупности отношений }{ lr и схем }{ jD , а только их подмноже-
ства. В этом и состоит локальность ER/SOM-моделей. Такая локальность
объясняется тем, что выбор атрибутов и конструирование «начальных» отно-
шений (и их совокупностей) при «трансляции» из ER/SOM-моделей опреде-
ляются семантикой соответствующей предметной области. Другими словами,
ER/SOM-конструкции являются решениями частных задач.
Выбранная начальная схема )0(D , как правило, требует нормализации в
силу наличия функциональных и/или многозначных зависимостей между от-
дельными атрибутами и/или их совокупностями. По сути, нормализация яв-
ляется преобразованием от начальной схемы )0(D базы данных (как сово-
купности реляционных схем) к некоторой конечной схеме )(kD , каждое из
отношений которой удовлетворяет известным критериям нормализации. В
большинстве случаев (для нетривиальных множеств атрибутов и нетриви-
альных зависимостей между ними) нормализация представляет собой мно-
гошаговую процедуру, т.е. вначале нормализуется одно отношение, а затем
другое; при этом вся схема базы данных, естественно, изменяется:
)()1()0( ... kDDD →→→ . (2)
Основной акцент при проектировании логической структуры баз дан-
ных ставится именно на нормализацию, т.е. на получение конечной схемы
)(kD , все отношения которой находятся в требуемой нормальной форме.
О полноте и единственности универсального каркаса в реляционной модели данных
Системні дослідження та інформаційні технології, 2010, № 3 27
Поскольку для α -схемы совокупность }{ jD является полной (т.е. пред-
ставляет собой множество всех возможных комбинаций всех возможных
реляционных схем lr , построенных комбинированием атрибутов ia ), она
уже содержит необходимую конечную схему )(kD . В силу этого полную
совокупность }{ jD можно считать универсальным «реляционным карка-
сом» (relational framework) для любых схем баз данных, которые могут быть
построены на фиксированном множестве атрибутов }{ ia при любых зави-
симостях между атрибутами. Обсуждение понятия «каркас схем баз дан-
ных» (в дальнейшем — просто каркас) и логические предпосылки к его вве-
дению имеется в работах [9, 12]
Объект нашего исследования — каркас }{ jD и его свойства.
Классический способ нормализации — это декомпозиция отношений.
Суть декомпозиции состоит в замене каждой реляционной схемы *r , не
удовлетворяющей критериям требуемой нормальной формы, на другие ре-
ляционные схемы *~}{ rrl , в совокупности эквивалентные исходной схеме
*r , но по отдельности соответствующие критериям нормальной формы.
Всю совокупность схем баз данных в каркасе }{ jD удобно проиндексиро-
вать. Любую нормализацию (2), а значит и соответствующую декомпози-
цию отношений, идентифицируем последовательностью ( )kjjjQ ,...,, 10 ин-
дексов схем баз данных, которую будем далее называть путем
нормализации. Для изучения свойств каркаса }{ jD целесообразно проана-
лизировать «топологию» путей Q . Метод данного исследования — анализ
топологии путей нормализации в каркасе }{ jD .
Каждый путь нормализации определяется двумя факторами: начальной
схемой )0(D базы данных, а также зависимостями в отношениях начальной
схемы (и, возможно, последующих схем). Эти функциональные и/или мно-
гозначные зависимости, как правило, тесно связаны с ключами (элементар-
ными либо композитными), которые можно выделить в экземплярах отно-
шений. Поскольку всякое нетривиальное отношение может содержать
несколько зависимостей (равно как и несколько ключей), для каждой на-
чальной схемы можно предположить наличие нескольких путей нормализа-
ции. Далее, не для всяких начальной )0(D и конечной )(kD схем может су-
ществовать путь нормализации. Все это указывает на то, что для
нетривиальных зависимостей на множестве атрибутов }{ ia топология путей
нормализации в каркасе }{ jD может оказаться достаточно сложной.
Цель работы — исследовать топологию путей нормализации реля-
ционного каркаса. Эта топология относится к структуре, обладающей свой-
ствами полноты и единственности, а именно к каркасу }{ jD . И хотя пол-
нота и единственность каркаса интуитивно очевидны, тем не менее, мы
приведем строгое доказательство этих характеристик.
Нормализация посредством декомпозиции реляционных схем является
широко распространенным методом устранения аномалий в реляционных
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 28
базах. Декомпозиция каждого конкретного отношения строится на основе
данных о зависимостях между атрибутами экземпляра этого отношения, т.е.
может быть применена только локально. Предположим, что зная топологию
путей нормализации (например, особенности влияния мощностей отноше-
ний в каркасе на принадлежность отношений заданным нормальным фор-
мам, связь между множеством зависимостей в некотором отношении и об-
ластью в каркасе, куда приведет декомпозиция этого отношения и т.п.)
удастся существенно упростить процедуры построения и модификации ко-
нечных логических структур реляционных баз данных. Во-первых, за счет
использования новых унифицированных методик дизайна этих структур. И,
во-вторых, за счет эксплуатации тех (топологических) особенностей унифи-
цированной структуры, которые ранее были совершенно незаметны при ре-
шении частных задач. Например, введение адекватной меры Q для путей
нормализации позволяет говорить о выборе оптимальных путей нормализа-
ции схем баз данных.
ПРЕОБРАЗОВАНИЯ
Пусть в экземплярах iR любого из отношений lr каждый атрибут ia при-
нимает значения pia ][ из некоторого непустого множества (домена) iA ,
ipi Aap ∈∀ ][: . Здесь индекс p идентифицирует любое из возможных зна-
чений атрибута в домене iA , причем ( )iApmax характеризует алгебраиче-
скую мощность домена iA , т.е. является его кардинальным числом.
Рассмотрим преобразование }{}{ li ra ⇒ . В отличие от традиционного
синтеза реляционных схем lr как декартовых произведений отдельных до-
менов, преобразование }{}{ li ra ⇒ приводит к построению полной сово-
купности реляционных схем.
Вначале для заданной предметной области формируется множество
атрибутов — }{ ia и множество соответствующих доменов — }{ iA . Как
правило, атрибуты просто перечисляются, а соответствующие им домены
соотносятся с определенными типами, формами, определяющими свойства-
ми. Тем не менее, каждый новый элемент в домене мы индексируем. Атри-
буты и их домены индексируются ( i ) в произвольном порядке. При этом:
pipii aappA ][][: * =≠∃∀ ∗ , (3)
т.е. в каждом домене все значения атрибутов единственны.
Ясно, что в процессе дизайна и сопровождения реляционной базы со-
став множества атрибутов }{ ia , равно как и состав отдельных доменов iA ,
может изменяться. Подобная модификация может быть обусловлена как вы-
делением в предметной области дополнительных атрибутов и новых объек-
тов, так и исключением атрибутов и объектов, ставших неактуальными.
Поэтому удобно говорить о состоянии реляционной базы — совокупности
}{}{ ii Aa , актуальной в некоторый момент времени. Заметим, что схема
О полноте и единственности универсального каркаса в реляционной модели данных
Системні дослідження та інформаційні технології, 2010, № 3 29
реляционной базы «эволюционирует» от состояния к состоянию за счет из-
менения }{ ia , но не }{ iA . Модификация самой базы (а не ее схемы) — до-
бавление новых кортежей, изменение или удаление существующих — мо-
жет привести к изменению кардинальных чисел отдельных доменов iA , а
также к изменению нормальной формы, в которой находится то или иное
отношение. Понятие зависимости между атрибутами (а значит и понятие о
соответствии нормальным формам) относится только к экземплярам реля-
ционных схем, но не к самим схемам. Заметим, что на этой стадии построе-
ния каркаса }{ jD никакие сведения о зависимостях между атрибутами не
учитываются, что существенно упрощает процедуру синтеза.
Далее конструируется полная совокупность }{ lr реляционных схем.
Традиционно отношения интерпретируются как подмножества декартовых
произведений доменов [6]. Указанная интерпретация отношений, несомнен-
но, формально верна. Вероятно, истоки этой интерпретации следует искать
в представлениях об «экземплярах» отношений, в пределах которых и вво-
дятся функциональные либо многозначные зависимости. Действительно, в
подавляющем большинстве реальных ситуаций элементы доменов kA яв-
ляются не перечисляемыми, а типизируемыми. Поэтому построение (как
перечисление) всех кортежей декартовых произведений доменов, как пра-
вило, практически невозможно. Здесь и далее мы будем использовать по-
строения, основанные на комбинировании атрибутов ia , а не их значений в
экземплярах отношений.
Итак, пусть имеются некоторые множества A и B , имеющие карди-
нальные числа Ap и Bp соответственно. Введем оператор L , действующий
следующим образом:
( )BLC Ak =}{ , aBCk ∪= , BAa \∈ . (4)
Оператор L продуцирует индексированную совокупность }{ kC мно-
жеств kC , содержащих все элементы множества B и один из элементов
множества A , не принадлежащий B . Здесь и далее множество A будем на-
зывать источником, множество B — базовым, а оператор L — оператором
роста. Заметим, что базовое множество может представлять собой совокуп-
ность множеств (в этом случае оператор роста действует на каждое из мно-
жеств базовой совокупности).
Пример 1. Для источника }7,6,5,4,3,2,1{=A и базового множества
}8,6,5,3,1{=B получаем
}}8,7,6,5,3,1{},8,6,5,4,3,1{},8,6,5,3,2,1{{}8,6,5,3,1{)( == AA LBL ,
( ) === }}8,7,6,5,3,1{},8,6,5,4,3,1{},8,6,5,3,2,1{{)()(2
AAAA LBLLBL
}}8,7,6,5,4,3,1{},8,7,6,5,3,2,1{},8,6,5,4,3,2,1{{=
( )== )()( 23 BLLBL AAA
}8,7,6,5,4,3,2,1{}}8,7,6,5,4,3,1{},8,7,6,5,3,2,1{},8,6,5,4,3,2,1{{ == AL ,
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 30
( ) )(}8,7,6,5,4,3,2,1{}8,7,6,5,4,3,2,1{)()( 334 BLLBLLBL AAAAA ==== . □
Рассмотрим основные свойства оператора L .
Прежде всего, оператор роста никогда не уменьшает мощность базово-
го множества. Если ∅≠BA \ , то мощность базового множества возрастает
на единицу, что дает мощность любого из множеств kC совокупности
}{ kC , т.е. ( ) 1: +=∀ Bk pCpk . Базовое множество является подмножеством
любого из порожденных kC . Фактически оператор роста обеспечивает «пе-
рекачку» элементов от источника к базовому множеству. В силу того, что
реальный источник предполагается конечным (т.е. Ap является конечным
числом), m -кратное действие )(BLm
A оператора роста всегда приводит к
«насыщению» базового множества. Этот эффект выражается в том, что
BCk → при ∅=BA \ , т.е., когда базовое множество уже содержит источ-
ник ( BA ⊆ ; источник «исчерпан»). Пороговым является значение
)\( BApM = ; при ∅=BA \ получаем 0)( =∅= pM , что указывает на
«насыщение» базового множества для всех Mm ≥ .
В конструктивном отношении важны две особенности оператора L :
во-первых, оператор роста позволяет получить все возможные комбинации
атрибутов ia , и, во-вторых, полная совокупность этих комбинаций оказыва-
ется структурированной. Действительно, каждое m -кратное действие
)(BLm
A порождает совокупности miC }{ множеств iC , имеющих равные
кардинальные числа, но взаимно отличающихся (если множеств iC оказы-
вается более одного) не более чем 1−m элементами. Любую такую сово-
купность miC }{ будем называть m -уровнем. Ясно, что множества iC каж-
дого m -уровня могут быть идентифицированы m числами, например,
индексами элементов ia источника A . Если же структура получаемой сово-
купности miC }{ множеств несущественна, то можно представить ее в виде
}{ kC простым перечислением порожденных множеств.
Пример 2. Пусть элементы рассмотренного выше источника
}7,6,5,4,3,2,1{=A проиндексированы следующим образом: 21 =a , 52 =a ,
13 =a , 34 =a , 65 =a , 46 =a и 77 =a (здесь контент элементов совершен-
но не имеет значения). Для базового множества }8,6,5,3,1{=B получаем
трехуровневую совокупность множеств, а именно:
1) )(BLA порождает тройку
11 }8,6,5,3,2,1{)1( aBCC ∪==≡ ;
62 }8,6,5,4,3,1{)6( aBCC ∪==≡ ;
73 }8,7,6,5,3,1{)7( aBCC ∪==≡ ;
2) )(2 BLA порождает тройку
16614 )6()1(},{}8,6,5,4,3,2,1{)6,1( aCaCaaBCC ∪=∪=∪==≡ ;
О полноте и единственности универсального каркаса в реляционной модели данных
Системні дослідження та інформаційні технології, 2010, № 3 31
17715 )7()1(},{}8,7,6,5,3,2,1{)7,1( aCaCaaBCC ∪=∪=∪==≡ ;
67766 )7()6(},{}8,7,6,5,4,3,1{)7,6( aCaCaaBCC ∪=∪=∪==≡ ;
3) )(3 BLA порождает единственное множество
=∪==≡ },,{}8,7,6,5,4,3,2,1{)7,6,1( 7617 aaaBCC
BABABaCaCaC ∪=∪==∪=∪=∪= )\()6,1()7,1()7,6( 761 ,
после чего наступает состояние «насыщения» базового множества. □
Ясно, что каждое «дочернее» множество может иметь несколько «ро-
дительских» множеств. Мощность BA \ , как правило, велика (т.е. велико
число атрибутов, выделяемых в предметной области), поэтому в большин-
стве случаев граф, отражающий эту взаимосвязь между множествами, не
будет планарным. Весь формализм теории графов (связность, диаметр,
маршруты и т.п.), естественно, применяются для конструируемой совокуп-
ности множеств.
Рассмотрим, как можно использовать оператор роста L при построе-
нии каркаса схем реляционных баз данных и оперировании с этим каркасом.
Пусть базовое множество B является пустым ( ∅=B и 0=Bp ), а ис-
точник A представляет собой индексированную совокупность }{ ia атомар-
ных атрибутов ( Np A = , где N — количество объектов-сущностей, выде-
ляемых в некоторой предметной области). Имеем ABA =\ и
( ) 1}{ AAi LLC ≡∅= , AaC ii ∈= . Таким образом, в случае однократного
применения оператора роста ( 1L ) пустое базовое множество можно не учи-
тывать, рассматривая лишь совокупность атрибутов A . Необходимо отме-
тить, что при многократном действии оператора роста ( 1>mL ) аргументом
будет совокупность множеств, полученных в результате предыдущих дейст-
вий оператора. Следовательно, сам оператор роста определяется индуктив-
но.
В данной работе базовое множество вводится для того, чтобы эф-
фективно объединить логические структуры нескольких баз данных, по-
строенных для взаимно пересекающихся предметных областей. Другую
важную область применения базового множества — модификацию логиче-
ской структуры базы данных при изменении совокупности атрибутов пред-
метной области — также целесообразно рассмотреть в дальнейших работах.
Итак, действие 1
AL для пустого базового множества порождает NS =1
унарных отношений }{ ia , однозначно соотносимых с атрибутами ia из ис-
точника A . Действие 2
AL оперирует с совокупностью }{ ia как с аргумен-
том, порождая элементы 2 -уровня, т.е. все возможные бинарные отноше-
ния. При этом 1
ALB = и NNS )1(
2
1
2 −= . Далее, совокупность бинарных
отношений является аргументом для действия 3
AL , которое порождает эле-
менты 3 -уровня, т.е. все возможные тернарные отношения. Аналогично,
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 32
2
ALB = и NNNS )2)(2(
6
1
3 −−= . Вообще, m -уровень ( Nm ≤ ), который
синтезируется действием m
AL с базовой совокупностью 1−= m
ALB в качестве
аргумента, содержит ( )!!
!
mNm
NSm −
= m -арных отношений. При Nm = по-
лучаем 1=NS , что указывает на «исчерпывание» совокупности атрибутов
A .
Общее число отношений в синтезируемом каркасе составляет
( ) 12
!)(!
!
11
−=
−
== ∑∑
==
N
N
m
N
m
m mNm
NSNS . (5)
Например, 31)5( =S , 1023)10( =S , 1048575)20( =S , 1073741823)30( =S .
Очевидно, что в практически значимых случаях, когда в предметной облас-
ти выделяются десятки и сотни атрибутов объектов, каркас не может быть
реализован целиком. Каркас, как естественным образом структурированная
совокупность множеств атрибутов, является аналогом множества «состоя-
ний» физической системы, в пределах которого разворачивается весь про-
цесс синтеза логической структуры реляционных баз данных. Для логиче-
ской структуры, состоящей из )(NSR ≤ реляционных схем }{ lr , удобно
ввести понятие заполнения Rξ каркаса
12)( −
== NR
R
NS
Rξ . (6)
Как правило, 1<<Rξ , причем вопрос о распределении )(NRξ для
реальных реляционных баз данных пока что остается открытым.
ПОЛНОТА И ЕДИНСТВЕННОСТЬ РЕЛЯЦИОННОГО КАРКАСА
Имеет место следующая теорема полноты и единственности.
Теорема. Каркас, порождаемый оператором роста на конечном множе-
стве атомарных атрибутов, единственен и полон.
Доказательство. Докажем вначале полноту каркаса.
Пусть заданы источник A и базовое множество B . Пусть существует
некоторое множество }{ icC = такое, что BC ⊇ и BAc \∈∃ , но
)(: BLCm m
A≠∀ . Тогда, из определения оператора роста, *
mCBC ∪≠ , где
BACm m \: * ⊆∀ , а значит *
mCc∈∃ . Но это противоречит допущению
BAc \∈∃ . Следовательно, действие )(BLm
A , порождающее множество C ,
действительно существует. Поэтому для каркаса имеем )(NSR = , т.е. его
заполнение 1=Rξ .
Доказательство единственности каркаса основано на его полноте.
Пусть имеется пара каркасов )(}{ BLC m
Ak = и )(}{ * BLC m
Ak = . В силу полноты
каждого из них имеем ∅=}{\}{ *
kk CC и ∅=}{\}{ *
kk CC , следовательно,
О полноте и единственности универсального каркаса в реляционной модели данных
Системні дослідження та інформаційні технології, 2010, № 3 33
}{}{ *
kk CC = , т.е. каркасы идентичны или, другими словами, на конечном
множестве атрибутов сущностей оператор роста порождает единственный
каркас. □
Единственность и полнота совокупности отношений, порождаемых
оператором AL из множества A атрибутов сущностей, выделяемых в пред-
метной области, указывает на исключительное положение каркаса в процес-
се разработки логической структуры баз данных. Действительно, любое от-
ношение на заданном множестве атрибутов принадлежит каркасу. Более
того, результат операций над элементами каркаса также будет элементом
каркаса. Это свойство замкнутости непосредственно следует из свойства
полноты. Поэтому каркас является вполне естественным (хотя и формаль-
ным) компонентом при построении унифицированной схемы синтеза логи-
ческих структур баз данных. Важно отметить, что сам каркас как структу-
рированная совокупность всех возможных множеств атрибутов (в
алгебраическом смысле каркас является булеаном источника A ) предельно
избыточен ( 1=ξ ), поэтому для его эффективного использования необходим
развитый инструментарий «навигации по каркасу», преобразований, редук-
ций, локализаций и оперирования в целом, который будет рассмотрен в
дальнейшем.
Итак, преобразование }{}{ li ra ⇒ в α -схеме (1) заключается в том, что
заданное множество атрибутов порождает структурированную совокупность
отношений. Следующее преобразование α -схемы, а именно }{}{ jl Dr ⇒ ,
состоит в синтезе всех возможных схем реляционных баз данных. Ясно, что
для этого можно использовать оператор роста L (4) с полной совокупностью
отношений в качестве аргумента.
Пусть базовое множество B вновь пусто ( ∅=B и 0=Bp ), а источ-
ником A является индексированная совокупность }{ lr отношений
( 12)( −== N
A NSp — полное число синтезированных отношений). В этом
случае действие 1
AL порождает совокупность схем баз данных, образован-
ных единичными отношениями (фактически это и есть каркас отношений,
рассмотренный выше), действие 2
AL — всеми возможными парами отноше-
ний, действие m
AL — всеми возможными m -компонентными совокупностя-
ми отношений ( Apm ≤ ). Общее число схем реляционных баз данных соста-
вит 1212 12)( −=−= −NNS
DS . Естественно, что всякая реляционная база
данных имеет в основе единственную схему, с необходимостью являющую-
ся элементом каркаса схем. Это объясняется тем, что согласно теореме о
полноте и единственности реляционного каркаса совокупность схем баз
данных, порождаемая оператором роста, также обладает свойствами един-
ственности и полноты.
Пример 3. Пусть в предметной области выделены 3 атомарных атрибу-
та a , b , c . Совокупность этих атрибутов образует источник A . Каркас от-
ношений состоит из 7123 =− отношений, а именно: a , b , c ( 1
AL — унар-
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 3 34
ные отношения), ab , bc , ac ( 2
AL — бинарные отношения), abc ( 3
AL —
единственное тернарное отношение). Каркас схем баз данных состоит из
127127 =− элементов, синтезируемых из 7-элементного каркаса отношений
как аргумента оператора роста L , например, a , abc (для действия 1
AL ),
aca + , acabc + , abac + (для действия 2
AL ), bcaabc ++ , cba ++ ,
bacab ++ (для действия 3
AL ).
ВЫВОДЫ
Между каркасом отношений и каркасом схем баз данных имеется сущест-
венное отличие. Элементом каркаса отношений является отношение как не-
которое множество атрибутов предметной области. Элементом каркаса схем
баз данных является множество отношений как реляционных схем, т.е. не-
которая схема базы данных.
Очевидно, что структура каркаса схем баз данных гораздо богаче
структуры каркаса отношений. Действительно, в каркасе отношений мы
различаем m -уровни, группируя отношения с равными кардинальными
числами; в силу свойства «насыщения» оператора роста можно выделить
только N таких уровней. Элементами каркаса схем баз данных могут быть
отношения разных уровней, причем само количество элементов схемы мо-
жет быть разным.
Каркас схем баз данных также занимает исключительное положение
при построении унифицированной α -схемы. Действительно, любая схема
реляционной базы данных, синтезируемой для заданного множества атрибу-
тов, является элементом этого каркаса. Поэтому решение любой задачи син-
теза или задачи модификации уже содержится в каркасе схем баз данных. В
[9, 12] на основе реляционного ключевого каркаса получена универсальная
логическая модель данных как особое подмножество всех реляционных мо-
делей.
Следует отметить, что до сих пор мы не учитывали зависимости между
атрибутами. Так как эти зависимости целиком определяются семантикой
предметной области, для которой создается (или под которую модифициру-
ется) схема реляционной базы данных, то каркасы отношений и схем со-
вершенно не зависят от какой бы то ни было специфики предметной облас-
ти, являясь универсальными конструкциями. Для нахождения этого
решения предполагается использовать концепцию «путей нормализации».
ЛИТЕРАТУРА
1. Codd E.F. A Relational Model of Data for Large Shared Data Banks // Communica-
tions of the ACM. — 1970. — 13, № 6. — P. 377–387.
2. Codd E.F. Extending the database relational model to capture more meaning // ACM
Transactions on Database Systems. — 1979. — 4, № 4. — P. 397–434.
3. Codd E.F. The Relational Model For Database Management. Version 2. — NY.: Addi-
son-Wesley Publishing Co, 1990. — 538 р.
О полноте и единственности универсального каркаса в реляционной модели данных
Системні дослідження та інформаційні технології, 2010, № 3 35
4. Darwen H., Date C.J. The third manifesto // ACM SIGMOD Records. — 1995. — 24,
№ 1. — P. 39–49.
5. Chen P.P. The Entity-Relationship Model: toward a unified view of data // ACM
Trans on Data base systems. — 1976. — 1, № 1. — P. 9–36.
6. Silberschatz A., Korth H.F., Sudarshan S. Database system concepts // PRC edition,
McGraw-Hill, Boston, 5th edit., 2005. — 1024 p.
7. Simsion G.C., Witt G.C. Data modeling essentials // Morgan Kaufmann Publishers,
3th edit. — 2005. — 532 p.
8. Патент № 63036. Способ расположения данных в компьютерном хранилище,
обеспечивающий модифицируемость ею структуры / Панченко Б.Е. // Про-
мышленная собственность. — 2004. — № 1. — С.3–134.
9. Панченко Б.Е. О шунтировании многозначительных зависимостей в реляцион-
ной модели данных // Проблемы программирования. — 2010. — № 2–3. —
С. 428–433.
10. Курош А.Г. Общая алгебра. — М.: Физматлит, 1979. — 150 с.
11. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. —
М.: Наука, 1991. — 448 с.
12. Панченко Б.Е., Писанко И.Н. Свойства реляционного каркаса на множестве се-
мантически атомарных предикатов // Кибернетика и системный анализ. —
2009. — № 6. — С. 120–129.
Поступила 22.04.2009
|
| id | journaliasakpiua-article-106903 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:21:44Z |
| publishDate | 2010 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/a6/d5524c2868ff87b0e3075a8dbefa13a6.pdf |
| spelling | journaliasakpiua-article-1069032018-04-06T12:28:40Z On the completeness and uniqueness of universal framework in relational model of data О полноте и единственности универсального каркаса в реляционной модели данных Про повноту та єдиність універсального каркаса в реляційній моделі даних Panchenko, B. E. Pysanko, I. M. Ideas about routes for normalization in the universal framework of relational databases and their topology are introduced. A theorem about the completeness and uniqueness of the relational framework is formulated and proved. В работе введено представление о путях нормализации в универсальном каркасе реляционных баз данных и о топологии этих путей. Сформулирована и доказана теорема о полноте и единственности реляционного каркаса. Введено уявлення про шляхи нормалізації в універсальному каркасі реляційних баз даних та про топологію цих шляхів. Сформульовано та доведено теорему про повноту та єдиність реляційного каркасу. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2010-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/106903 System research and information technologies; No. 3 (2010); 25-35 Системные исследования и информационные технологии; № 3 (2010); 25-35 Системні дослідження та інформаційні технології; № 3 (2010); 25-35 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/106903/101906 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Panchenko, B. E. Pysanko, I. M. Про повноту та єдиність універсального каркаса в реляційній моделі даних |
| title | Про повноту та єдиність універсального каркаса в реляційній моделі даних |
| title_alt | On the completeness and uniqueness of universal framework in relational model of data О полноте и единственности универсального каркаса в реляционной модели данных |
| title_full | Про повноту та єдиність універсального каркаса в реляційній моделі даних |
| title_fullStr | Про повноту та єдиність універсального каркаса в реляційній моделі даних |
| title_full_unstemmed | Про повноту та єдиність універсального каркаса в реляційній моделі даних |
| title_short | Про повноту та єдиність універсального каркаса в реляційній моделі даних |
| title_sort | про повноту та єдиність універсального каркаса в реляційній моделі даних |
| url | https://journal.iasa.kpi.ua/article/view/106903 |
| work_keys_str_mv | AT panchenkobe onthecompletenessanduniquenessofuniversalframeworkinrelationalmodelofdata AT pysankoim onthecompletenessanduniquenessofuniversalframeworkinrelationalmodelofdata AT panchenkobe opolnoteiedinstvennostiuniversalʹnogokarkasavrelâcionnojmodelidannyh AT pysankoim opolnoteiedinstvennostiuniversalʹnogokarkasavrelâcionnojmodelidannyh AT panchenkobe propovnotutaêdinístʹuníversalʹnogokarkasavrelâcíjníjmodelídanih AT pysankoim propovnotutaêdinístʹuníversalʹnogokarkasavrelâcíjníjmodelídanih |