О топологии путей нормализации в реляционном каркасе
Исследованы пути нормализации в универсальном каркасе реляционных баз данных (БД) и топологии этих путей. Доказана теорема замкнутости путей нормализации в реляционном каркасе. Теорема позволяет применять реляционный каркас как уникальный носитель схем БД, нормализованных до высоких форм, а также ан...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/50116 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О топологии путей нормализации в реляционном каркасе / Б.Е. Панченко, И.Н. Писанко // Систем. дослідж. та інформ. технології. — 2011. — № 3. — С. 102-107. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860116921989464064 |
|---|---|
| author | Панченко, Б.Е. Писанко, И.Н. |
| author_facet | Панченко, Б.Е. Писанко, И.Н. |
| citation_txt | О топологии путей нормализации в реляционном каркасе / Б.Е. Панченко, И.Н. Писанко // Систем. дослідж. та інформ. технології. — 2011. — № 3. — С. 102-107. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Исследованы пути нормализации в универсальном каркасе реляционных баз данных (БД) и топологии этих путей. Доказана теорема замкнутости путей нормализации в реляционном каркасе. Теорема позволяет применять реляционный каркас как уникальный носитель схем БД, нормализованных до высоких форм, а также анализировать существующие и внедренные БД на предмет их аномалий и влияния на приложения в процессе эксплуатации.
Досліджено шляхи нормалізації в універсальному каркасі реляційних баз даних (БД) і топологію цих шляхів. Доведено теорему замкненості шляхів нормалізації в реляційному каркасі. Теорема дозволяє використовувати реляційний каркас в якості універсального носія схем БД, нормалізованих до високих форм, а також аналізувати існуючі та впроваджені БД на предмет їх аномалій та впливу на програмне застосування в процесі експлуатації.
In the normalization ways in the universal frame of the relational databases and the topology of these ways are investigated. Theorem about closure of normalization ways in a relational frame has been proved. The theorem allows using a relational frame as a unique database schemes carrier, normalized to the higher forms. It also allows analyzing the existing and embedded databases for their anomalies and the impact on the software usage during the operation.
|
| first_indexed | 2025-12-07T17:36:21Z |
| format | Article |
| fulltext |
© Б.Е. Панченко, И.Н. Писанко, 2011
102 ISSN 1681–6048 System Research & Information Technologies, 2011, № 3
TIДC
МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ
УПРАВЛІННЯ І ТЕОРІЯ ІГОР
УДК 004.652
О ТОПОЛОГИИ ПУТЕЙ НОРМАЛИЗАЦИИ В
РЕЛЯЦИОННОМ КАРКАСЕ
Б.Е. ПАНЧЕНКО, И.Н. ПИСАНКО
Исследованы пути нормализации в универсальном каркасе реляционных баз
данных (БД) и топологии этих путей. Доказана теорема замкнутости путей
нормализации в реляционном каркасе. Теорема позволяет применять реляци-
онный каркас как уникальный носитель схем БД, нормализованных до высо-
ких форм, а также анализировать существующие и внедренные БД на предмет
их аномалий и влияния на приложения в процессе эксплуатации.
ВВЕДЕНИЕ
Получение безаномальных логических схем является одной из ключевых
задач проектирования логической структуры реляционных баз данных (БД).
Известно, что аномалии вставки, модификации и удаления кортежей связа-
ны с наличием зависимостей (функциональных, многозначных, а также за-
висимостей соединения) между подмножествами столбцов таблиц БД
[1, 2, 3]. Такие зависимости выражают ограничения, накладываемые на зна-
чения, хранимые в кортежах таблиц. В свою очередь, эти ограничения яв-
ляются формальным отображением семантики, присущей конкретным
предметным областям. Для предметных областей с нетривиальной семанти-
кой, характеризуемых многообразными и сложными ограничениями на хра-
нимые данные, избыточность представления данных в таблицах является
типичным недостатком, обуславливающим аномалии логических схем БД.
Традиционная методика устранения таких аномалий состоит в деком-
позиции проблемных таблиц БД. Согласно Дейту, всякая БД есть хранили-
ще истинностных высказываний (фактов) о так называемых «сущностях»
заданной предметной области и их взаимосвязях [2]. Поэтому декомпозиция
является не чем иным как представлением некоторого хранимого высказы-
вания в виде эквивалентной совокупности других (более простых) высказы-
ваний. При этом эквивалентность между исходным высказыванием с семан-
тическим ограничением, с одной стороны, и совокупностью высказываний
без семантического ограничения, с другой стороны, обеспечивается целым
рядом определений и теорем о декомпозиции без потерь [3, 4]. Таким обра-
зом, посредством декомпозиции происходит нормализация представления
семантически сложного факта в БД за счет его разбиения на более простые
факты, рассматриваемые в их совокупности. При этом для сложных фактов
О топологии путей нормализации в реляционном каркасе
Системні дослідження та інформаційні технології, 2011, № 3 103
с семантическими ограничениями, как правило, имеется более чем один ва-
риант такого разбиения. Можно заметить некоторую аналогию между ука-
занным процессом разбиения фактов БД и функциональной декомпозицией.
Традиционно схемой реляционной БД является некая фиксированная
совокупность реляционных схем jR , т.е. именованных множеств атрибутов
и ключей [3]. Для построения такой схемы вводится совокупность атрибу-
тов ix и однозначно соотносимых с ними множеств значений — доменов
)( ixD [4]. При этом совокупности самих атрибутов ассоциируются с «объ-
ектами» или «сущностями», а совокупности значений атрибутов — с экзем-
плярами объектов или сущностей. Это является первым шагом к отображе-
нию семантики предметной области в схеме БД. Заметим, что и множество
ix и совокупность множеств )( ixD являются общими для схем jR в том
смысле, что отдельный атрибут может принадлежать нескольким схемам.
Наконец, экземпляр каждой реляционной схемы jR представляется в виде
совокупности кортежей pK — упорядоченных последовательностей зна-
чений атрибутов ix схемы jR , т.е. )(...)(...)( 1 Kip xDxDxDK ××××⊂ ,
ji Rx ∈ .
В работах [5, 6] показано, что на операторе роста L может быть по-
строена универсальная логическая модель данных (УЛМД), отображающая
специфику произвольной предметной области (ПО) из N сущностей на мно-
жество реляционных отношений, полное количество которых )(NS опреде-
ляется формулой:
( ) ( ) 12
!!
!
11
−=
−
== ∑∑
==
N
N
m
N
m
m mNm
NSNS . (1)
На рисунке изображена общая схема ключевого каркаса реляционной
УЛМД. Очевидно, что большинство отношений не будут актуальными в
контексте конкретных постановок. Но их актуализация в любой момент яв-
Рисунок. Ключевой каркас реляционной УЛМД для N сущностей-объектов
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2011, № 3 104
ляется модификацией структуры конкретного хранилища.
Из этого следует, что модификация схемы хранилища сводится к двум
типам операций актуализации: аннулирование отношения (реляционной
таблицы) и аннулирование произвольного множества неключевых атрибу-
тов в произвольной группе отношений. При этом целостность хранилища
сводится, прежде всего, к целостности ключевых атрибутов и их строгого
соответствия в различных, но логически связанных отношениях.
ПОСТАНОВКА ЗАДАЧИ
Цель работы — исследовать схемы БД, получаемые на универсальном ре-
ляционном каркасе (в дальнейшем, просто каркасе), на принадлежность той
или иной нормальной форме (НФ). Для этого рассмотрим пути нормализа-
ции каркаса.
Рассмотрим некоторое отношение }{ kC и его экземпляр ][ kC с зави-
симостями kΦ . Пусть ,...},,,,{ 54321 KKKKKK = — упорядоченная сово-
купность традиционных НФ универсального реляционного каркаса. Пусть
дана индексированная совокупность реляционных схем }{ kC , …,2,1=k
)(, NS… , образующих каркас отношений [6] для множества из N сущнос-
тей в смысле [5] в некоторой произвольной предметной области. Внесение
реального контента в каркас отношений (т.е. заполнение реляционных схем
сведениями о значениях реальных экземпляров) приводит к формированию
совокупности экземпляров отношений. Обозначим текущий экземпляр от-
ношения }{ kC символом ][ kC . Для каждого из экземпляров ][ kC имеет
смысл говорить о множестве kΦ функциональных либо многозначных за-
висимостей между атрибутами (или множествами атрибутов) соответству-
ющего отношения }{ kC . Как правило, множество зависимостей kΦ считае-
тся независимым от экземпляра ][ kC , т.е. любая модификация ][ kC не
меняет kΦ . Это характерное условие, подразумевающее статичность схемы
реляционной БД и соответствующих путей нормализации отношений, в да-
льнейшем будет снято при рассмотрении динамических схем.
Пример 1. Пусть для источника },,,{ dcbaA = ( 4=N ) сформирован
каркас [6], состоящий из 15124 =− отношений }{ kC , а также образованы
соответствующие экземпляры ][ kC этих отношений. Множество зависимо-
стей kΦ может состоять, например, из: функциональных зависимостей ме-
жду атрибутами отношений 1-го уровня (для действия 1
AL ), т.е. из aa → ,
cc → , которые всегда будут тривиальными; из зависимостей вида ba → ,
dc →→ между атрибутами отношений 2-го уровня (для действия 2
AL ); из
зависимостей вида cab → , bda →→ между атрибутами отношений 3-го
уровня (для действия 3
AL ) и т.д. Важно, что все элементы множества зави-
симостей kΦ между атрибутами (и множествами атрибутов) отношения
можно перечислить комбинаторными методами, вводя тем самым полное
множество зависимостей kΦ и его подмножество kk Φ⊆Φ~ , актуальное для
конкретного экземпляра ][ kC отношения }{ kC .
О топологии путей нормализации в реляционном каркасе
Системні дослідження та інформаційні технології, 2011, № 3 105
Рассмотрим некоторое отношение }{ kC и его экземпляр ][ kC с зави-
симостями kΦ . Пусть ,...},,,,{ 54321 KKKKKK = — упорядоченная сово-
купность традиционных НФ, а также всех возможных их модификаций.
Предположим, что ψ — множество классических критериев, относящих
nC к НФ из совокупности K :
( )nn Cψψ = , Kn ∈ψ . (2)
Учитывая взаимосвязь ...321 ⊂⊂⊂ KKK между НФ из совокупности
K , обозначим через kk ψmax=Ψ наибольшую НФ, в которой находится
экземпляр ][ nC отношения }{ nC .
Рассмотрим некоторое «начальное» подмножество )0(D каркаса отно-
шений. Следует отметить, что )0(D является элементом каркаса схем БД.
Состоянием схемы )0(D назовем совокупность }{ kΨ НФ экземпляров ][ kC
всех отношений )0(DCk ∈ . Ясно, что НФ, в которой будет находиться схема
)0(D (и, в общем случае, весь каркас отношений), определяется величиной
}{max kΨ . Именно поэтому, все отношения схемы БД приводятся (как пра-
вило, путем декомпозиции) к одной, наибольшей НФ. Хотя целесообраз-
ность достижения схем отдельных отношений критериям высоких НФ оста-
ется вопросом дискуссионным.
В результате такой нормализации мы получаем последовательность
элементов каркаса схем БД, которую можно интерпретировать как путь
нормализации [6]. Формально путь нормализации ),...,,( 10 kjjjQ представ-
ляет собой последовательность индексов схем БД, которая описывает пере-
ход от начального элемента )0(D к конечному элементу )(kD каркаса схем
БД, причем этот переход осуществляется только декомпозицией отношений,
принадлежащих элементам пути нормализации. Конечный элемент )(kD
пути нормализации мы будем называть решением. Далее, топологией путей
нормализации для заданной начальной схемы )0(D будем называть сово-
купность решений )(kD , которые можно получить путем декомпозиции при
заданных зависимостях }{ kΦ между атрибутами отношений. Ясно, что то-
пология будет определяться как )0(D , так и }{ kΦ .
ТЕОРЕМА О ЗАМКНУТОСТИ ПУТЕЙ НОРМАЛИЗАЦИИ
Рассмотрим теорему замкнутости: для заданных источника A и совокуп-
ности }{ kΦ зависимостей между атрибутами в экземплярах ][ kC каркаса
отношений существует путь нормализации )()0( ... kDD →→ , решение ко-
торого находится в требуемой НФ }{max kΨ из совокупности K . Это не-
посредственно следует из полноты каркасов отношений и схем БД [6].
Пример 2. Вновь рассмотрим источник },,,{ dcbaA = ( 4=K ), для ко-
торого сформирован каркас из пятнадцати отношений }{ kC . Пусть )0(D —
начальная схема реляционной БД, содержащая среди прочих единственное
Б.Е. Панченко, И.Н. Писанко
ISSN 1681–6048 System Research & Information Technologies, 2011, № 3 106
отношение }{abcdC = 4-го уровня (т.е. синтезированное действием 4
AL ),
)0(DC ∈ . Пусть семантика ПО такова, что для экземпляра ][C выполняется
следующее множество функциональных и многозначных зависимостей Φ :
dabc → , ba →→ , ca →→ . Следует выяснить, каким может быть решение
)1(D для простейшего, одношагового пути нормализации.
Поскольку все атрибуты из A являются атомарными, то 1)( KC =ψ , т.е.
C находится в 1НФ. Далее, для функциональной зависимости dabc →
множество атрибутов cba является суперключом, поэтому =)(Cψ
},,,{ 4321 KKKK= , т.е. C находится также в 2НФ, 3НФ и НФБК. Посколь-
ку для каждой из многозначных зависимостей ba →→ и ca →→ в отно-
шении C ни a ни b не являются суперключами, 5)( KC ≠ψ , т.е. C не на-
ходится в 4НФ. Поэтому 4K=Ψ . Для дальнейшего увеличения Ψ на
единицу, т.е. для получения 4НФ, можно было бы потребовать, чтобы в от-
ношениях искомого решения )1(D отсутствовали нетривиальные многоз-
начные зависимости, такие как ba →→ и ca →→ .
Заметим, что многозначная зависимость может существовать для от-
ношений не ниже 3 -го уровня (т.е. синтезированных действиями 3≥m
AL ), т.е.
когда отношение имеет минимум три атрибута. В силу насыщения операто-
ра роста наибольшим уровнем является 4-й, где и находится отношение C .
Ясно, что решение )1(D , для которого 5K=Ψ (4НФ), не должно содержать
отношения C . Можно попробовать редуцировать схему )1(D до совокуп-
ностей отношений, порождаемых действиями 3<m
AL , а именно применить
так называемое ограничение каркаса отношений сверху. Выполняя декомпо-
зицию отношения C , получаем
}{}{}{}){}{}({}{}{ adacabadacacdababcd ∪∪=∪∪ ,
т.е. производится замена отношения 4-го уровня на совокупность отноше-
ний 2-го уровня, которые и будут присутствовать в решении )1(D . При этом
для отношений }{ab и }{ac многозначные зависимости ba →→ и ca →→
будут уже тривиальными, т.е. критерий 4НФ будет выполняться. ■
ВЫВОДЫ
Из примера 2 видно, что исходное отношение C 4-го уровня }{abcd после
декомпозиции на совокупность отношений 2-го уровня уже не содержит
функциональной зависимости dabc → , т.е. информация об этой зависимо-
сти для }{}{}{ adacab ∪∪ теряется. Если под сохранностью информации
понимать обеспечение соединения без потерь [3, 4] и, одновременно, обес-
печение сохранения зависимостей, то такую декомпозицию можно считать
декомпозицией с потерей информации. Имеем тройку критериев, которые в
случае корректной декомпозиции должны быть выполнены одновременно:
возможность восстановления кортежей (обеспечение соединения без по-
терь), сохранение имеющихся зависимостей, а также соответствие крите-
О топологии путей нормализации в реляционном каркасе
Системні дослідження та інформаційні технології, 2011, № 3 107
риям «целевой» нормальной формы (в примере 2 это 4НФ) [7]. Если между
критериями из этой совокупности возникает противоречие, т.е. если невоз-
можно одновременно выполнить хотя бы два критерия из трех, декомпози-
ция будет некорректной. При получении желаемой нормальной формы такая
некорректность может быть выражена либо искажениями при соединении
дочерних отношений, либо искажениями в зависимостях между атрибутами.
Известно, что для «высоких» нормальных форм — НФБК, 4НФ, как в при-
мере 2, а также 5НФ указанная тройка критериев может быть выполнена не
во всех случаях: такая ситуация изложена в [3] для НФБК, в [7] для 4НФ, а
также в [8] — для 4НФ и 5НФ. Искажения при соединении считаются недо-
пустимыми, поэтому искажения в зависимостях рассматриваются в качестве
приемлемого, хотя и нежелательного «артефакта» при нормализации реля-
ционных схем.
Отметим, однако, что ключевой каркас, приведенный на рисунке, по-
лучен в [5] с использованием теоремы о шунтировании многозначной зави-
симости. Ключевой каркас является частным случаем реляционного каркаса,
описанного в [6]. Частный случай обеспечивается уникальным множеством
суррогатных ключевых атрибутов набора сущностей. Как отмечалось в [5],
ключевой каркас строго соответствует критериям 4НФ. Проделав над мно-
жеством ключевых атрибутов процедуры, аналогичные изложенным выше,
несложно из реляционного каркаса получить ключевой. На множестве сур-
рогатных ключевых атрибутов он по-прежнему будет полным и единствен-
ным.
В заключение можно предположить, что дальнейший анализ топологии
путей нормализации, использующий особенности структуры универсально-
го каркаса схем реляционных БД, позволит выработать единый универсаль-
ный метод определения решений для задач синтеза и/или модификации ло-
гических структур реляционных БД.
ЛИТЕРАТУРА
1. Codd E.F. The Relational Model For Database Management, Version 2, Reading
Mass. — NY: Addison-Wesley Publishing Co, 1990. — 538 p.
2. Дейт К.Дж. Введение в системы баз данных. — 7-е изд. — М.: Вильямс, 2001.
— 1072 с.
3. Мейер Д. Теория реляционных баз данных. — М.: 1987. — 608с.
4. Ульман Дж. Основы систем баз данных. — М.: Финансы и статистика, 1983. —
334 с.
5. Панченко Б.Е. О синтезе универсальной логической модели данных // Вестн.
СумГУ. Сер. Технические науки. — 2009. — № 2. — С. 60–66.
6. Панченко Б.Е., Писанко И.Н. О полноте и единственности универсального
каркаса в реляционной модели данных // Системні дослідження та інфор-
маційні технології. — 2010. — № 3. — С. 25–35.
7. Carver A., Halpin T. Atomicity and normalization // Proceedings of the 13-th Inter-
national Workshop on Exploring Modelling Methods for Systems Analysis and
Design, June, 29, from CEUR–WS archive. — Montpellier, France. — 2008. —
337. — P. 40–54.
8. Silberschatz A., Korth H.F., Sudarshan S. Database system concepts // PRC edition,
McGraw-Hill Higher Education Press, 2006. — 1129 р.
Поступила 01.06.2009
|
| id | nasplib_isofts_kiev_ua-123456789-50116 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T17:36:21Z |
| publishDate | 2011 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Панченко, Б.Е. Писанко, И.Н. 2013-10-05T11:49:56Z 2013-10-05T11:49:56Z 2011 О топологии путей нормализации в реляционном каркасе / Б.Е. Панченко, И.Н. Писанко // Систем. дослідж. та інформ. технології. — 2011. — № 3. — С. 102-107. — Бібліогр.: 8 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50116 004.652 Исследованы пути нормализации в универсальном каркасе реляционных баз данных (БД) и топологии этих путей. Доказана теорема замкнутости путей нормализации в реляционном каркасе. Теорема позволяет применять реляционный каркас как уникальный носитель схем БД, нормализованных до высоких форм, а также анализировать существующие и внедренные БД на предмет их аномалий и влияния на приложения в процессе эксплуатации. Досліджено шляхи нормалізації в універсальному каркасі реляційних баз даних (БД) і топологію цих шляхів. Доведено теорему замкненості шляхів нормалізації в реляційному каркасі. Теорема дозволяє використовувати реляційний каркас в якості універсального носія схем БД, нормалізованих до високих форм, а також аналізувати існуючі та впроваджені БД на предмет їх аномалій та впливу на програмне застосування в процесі експлуатації. In the normalization ways in the universal frame of the relational databases and the topology of these ways are investigated. Theorem about closure of normalization ways in a relational frame has been proved. The theorem allows using a relational frame as a unique database schemes carrier, normalized to the higher forms. It also allows analyzing the existing and embedded databases for their anomalies and the impact on the software usage during the operation. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Методи оптимізації, оптимальне управління і теорія ігор О топологии путей нормализации в реляционном каркасе Про топологію шляхів нормалізації в реляційному каркасі About topology of normalization ways in the relation frame Article published earlier |
| spellingShingle | О топологии путей нормализации в реляционном каркасе Панченко, Б.Е. Писанко, И.Н. Методи оптимізації, оптимальне управління і теорія ігор |
| title | О топологии путей нормализации в реляционном каркасе |
| title_alt | Про топологію шляхів нормалізації в реляційному каркасі About topology of normalization ways in the relation frame |
| title_full | О топологии путей нормализации в реляционном каркасе |
| title_fullStr | О топологии путей нормализации в реляционном каркасе |
| title_full_unstemmed | О топологии путей нормализации в реляционном каркасе |
| title_short | О топологии путей нормализации в реляционном каркасе |
| title_sort | о топологии путей нормализации в реляционном каркасе |
| topic | Методи оптимізації, оптимальне управління і теорія ігор |
| topic_facet | Методи оптимізації, оптимальне управління і теорія ігор |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50116 |
| work_keys_str_mv | AT pančenkobe otopologiiputeinormalizaciivrelâcionnomkarkase AT pisankoin otopologiiputeinormalizaciivrelâcionnomkarkase AT pančenkobe protopologíûšlâhívnormalízacíívrelâcíinomukarkasí AT pisankoin protopologíûšlâhívnormalízacíívrelâcíinomukarkasí AT pančenkobe abouttopologyofnormalizationwaysintherelationframe AT pisankoin abouttopologyofnormalizationwaysintherelationframe |