Разложение соединения без потерь

В проектировании баз данных разложение соединения без потерь представляет собой разложение отношения на отношения таким образом, что естественное соединение двух меньших отношений возвращает исходное отношение. Это является центральным для безопасного удаления избыточности из баз данных с сохранением исходных данных. ^[1] Соединение без потерь также можно назвать неаддитивным. ^[2] ${\displaystyle r}$ ${\displaystyle r_{1},r_{2}}$

Определение

Отношение на схеме разлагается без потерь на схемы и если , то есть является естественным объединением его проекций на меньшие схемы. Пара является разложением без потерь-объединения или, как говорят, имеет без потерь объединение относительно набора функциональных зависимостей , если любое отношение , которое удовлетворяет, разлагается без потерь на и . ^[3] ${\displaystyle r}$ ${\displaystyle R}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle \pi _{R_{1}}(r)\bowtie \pi _{R_{2}}(r)=r}$ ${\displaystyle r}$ ${\displaystyle (R_{1},R_{2})}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle r(R)}$ ${\displaystyle F}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$

Разложения на более чем две схемы можно определить таким же образом. ^[4]

Критерии

Разложение имеет соединение без потерь относительно тогда и только тогда, когда замыкание включает или . Другими словами, должно выполняться одно из следующих условий: ^[4] ${\displaystyle R=R_{1}\cup R_{2}}$ ${\displaystyle F}$ ${\displaystyle R_{1}\cap R_{2}}$ ${\displaystyle R_{1}\setminus R_{2}}$ ${\displaystyle R_{2}\setminus R_{1}}$

• ${\displaystyle (R_{1}\cap R_{2})\to (R_{1}\setminus R_{2})\in F^{+}}$
• ${\displaystyle (R_{1}\cap R_{2})\to (R_{2}\setminus R_{1})\in F^{+}}$

Критерии для множественных подсхем

Несколько подсхем имеют соединение без потерь, если есть способ, которым мы можем многократно выполнять соединения без потерь, пока все схемы не будут объединены в одну схему. Как только у нас есть новая подсхема, созданная из соединения без потерь, нам не разрешено использовать любую из ее изолированных подсхем для соединения с любой из других схем. Например, если мы можем выполнить соединение без потерь для пары схем, чтобы сформировать новую схему , мы используем эту новую схему (а не или ), чтобы сформировать соединение без потерь с другой схемой (которая, возможно, уже объединена (например, )). ^{[ неопределенно ]} ${\displaystyle R_{1},R_{2},...,R_{n}}$ ${\displaystyle R_{i},R_{j}}$ ${\displaystyle R_{i,j}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{j}}$ ${\displaystyle R_{k}}$ ${\displaystyle R_{k,l}}$

Пример

• Пусть будет схемой отношений с атрибутами A , B , C и D. ${\displaystyle R=\{A,B,C,D\}}$
• Пусть — множество функциональных зависимостей. ${\displaystyle F=\{A\rightarrow BC\}}$
• Разложение на и не имеет потерь при F , поскольку и у нас есть функциональная зависимость . Другими словами, мы доказали, что . ^{[5] [6]} ${\displaystyle R_{1}=\{A,B,C\}}$ ${\displaystyle R_{2}=\{A,D\}}$ ${\displaystyle R_{1}\cap R_{2}=A}$ ${\displaystyle A\rightarrow BC}$ ${\displaystyle (R_{1}\cap R_{2}\rightarrow R_{1}\setminus R_{2})\in F^{+}}$

Ссылки

1. Pohler, K (2015). «Разложение без потерь-объединений: применение в количественных вычислительных метриках». Международный журнал прикладной компьютерной науки . 21 (4): 190–212.
2. Эльмасри, Рамез (2016). Основы систем баз данных (Седьмое изд.). Хобокен, Нью-Джерси: Пирсон. п. 461. ИСБН 978-0133970777.
3. Майер, Дэвид (1983). Теория реляционных баз данных (PDF) . Computer Science Press. стр. 101. ISBN 0-914894-42-0. Получено 16 августа 2024 г.
4. Ullman, Jeffrey D. (1988). Principles of Database and Knowledge-base Systems (PDF) (1-е изд.). Computer Science Press. стр. 397. ISBN 0-88175188-X. Получено 16 августа 2024 г.
5. "Разложение без потерь-соединения". Cs.sfu.ca . Получено 2016-02-07 .
6. "www.data-e-education.com - Lossless Join Decomposition". Архивировано из оригинала 2014-02-21 . Получено 2014-02-12 .