Понятие модели данных.

Липецкий государственный технический университет Кафедра прикладной математики БАЗЫ ДАННЫХ Лекция 3 ПОНЯТИЕ МОДЕЛИ ДАННЫХ. Автор лекций – Погодаев А.К. Составитель презентаций – Хабибуллина Е.Л. Липецк - 2016 3. ПОНЯТИЕ МОДЕЛИ ДАННЫХ 3.5. Реляционная модель данных. Операции реляционной алгебры .5. Реляционная модель данных. Операции реляционной алгебры Отношение – представляющее собой подмножество декартова произведения доменов. Домен – множество элементов, которое может описывать некоторые свойства объекта. Декартовым произведением доменов называется множество всех кортежей длины k, состоящих из k элементов – по одному из каждого домена. D  D1  D2  ...  Dk . Отношением R на множествах D1, D2, … Dk называют подмножество декартова произведения R  D , где элементами отношения являются кортежи. Арность (порядок) k кортежа определяет арность отношения. А А1 а e k В B1 b f l B2 c g m С C1 d h n (домены) (атрибуты) (кортежи) 3.5. Реляционная модель данных. Операции реляционной алгебры Согласно α-алгебре, разработанной Коддом, в основе операций над данными лежит 5 основных и 4 дополнительных операции. 1) Объединение (R  S). Представляет собой множество кортежей, которые принадлежат R и S, либо им обоим. Операция предполагает, что отношения имеют одну арность. 2) Разность (R – S). Множество кортежей, принадлежащих R, но не принадлежащих S. Одинаковая арность. 3) Декартово произведение (R  S). Результат включает все комбинации кортежей R и S. Одинаковая арность не обязательна. 4) Проекция πi1,…,im(R). Результат отношения – выбранное подмножество атрибутов, в котором кортежи-дубликаты устраняются. i1,…,im – атрибуты, по которым формируется результат. 5) Селекция σF(R). F – формула, образованная константами, названиями элементов отношения, арифметическими операторами сравнения, логическими операторами. Селекция – множество кортежей, принадлежащих R, таких что при подстановке соответствующих элементов отношения в формулу F становится истинной. 3.5. Реляционная модель данных. Операции реляционной алгебры Дополнительные операции представляют собой комбинацию основных операций. 6) Пересечение R S  R  (R  S). 7) Частное R  S   1,..,nk (R)   1,..,nk ( 1,..,nk (R)  S)  R). n – арность R, k – арность S, n > k. S  R. 8) Θ – соединение. R ij S   i(n j ) (R  S). Здесь Θ – арифметический оператор сравнения, i, j – элементы R и S. 9) Естественное соединение. R S   i 1,...,im ( R. A1 S . A1...R. Ak S . Ak (R  S)). i1, …, im – список всех атрибутов отношения (R x S), за исключением S.A1, …, S.Ak. Aj – имена столбцов R и S. 3.6. ПРАВИЛА ПОСТРОЕНИЯ ФОРМУЛ РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ С ПЕРЕМЕННЫМИ-КОРТЕЖАМИ   Формулы в реляционном исчислении имеют вид t ( i ) /  (t ) , где t(i) – переменная-кортеж фиксированной длины i, или t (R) /  (t ) , где t(R) – переменная-кортеж со схемой отношения R; φ – формула, построенная из атомов и совокупности операторов. Формула строится по следующим правилам. Атомы формулы φ могут быть трех видов: 1. R(s). Здесь R – имя отношения, а s – переменная-кортеж той же арности, что и R. Атом означает, что кортеж s принадлежит отношению R. 2. s*i+ θ u*j+. Здесь θ – арифметический оператор сравнения, а атом в целом означает, что i-тый компонент переменной-кортежа s находится в отношении θ с j-тым компонентом u. 3. а θ u*j+. Атом означает, что некоторое число а находится в отношении θ с j-тым компонентом переменной-кортежа u. Как и в алгебре высказываний, существуют свободные и связанные вхождения переменных в формулу. Входящая в формулу переменная называется связанной, если ее вхождению предшествуют кванторы , . В противном случае переменная называется свободной. 3.6. ПРАВИЛА ПОСТРОЕНИЯ ФОРМУЛ РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ С ПЕРЕМЕННЫМИ-КОРТЕЖАМИ 1. Каждый атом есть формула. Все переменные-кортежи, входящие в атом, являются свободными в этой формуле. 2. Если φ1 и φ2 – формулы, то φ1 ^ φ2, φ1 v φ2, φ1, φ2 – тоже формулы. 3. Если φ – формула, то (s)(φ), (s)(φ) – также формулы. 4. Формулы при необходимости могут заключаться в скобки. При этом принят следующий приоритет выполнения операций: арифметические операции, операции сравнения, кванторы, логические операторы (отрицание, конъюнкция, дизъюнкция). 5. Единственной свободно входящей в формулу φ переменной является переменнаякортеж t, множество значений которой собственно и определяется этой формулой. Все остальные входящие в формулу переменные-кортежи должны быть связаны кванторами. 6. Ничто другое не является формулой. 3.7. Основные формулы 1) Объединение (R(n)  S(n)). Представляет собой множество кортежей, которые принадлежат R и S, либо им обоим. t (n)  / R (t )  S (t ) . 2) Разность (R(n) – S(n)). Множество кортежей, принадлежащих R, но не принадлежащих S.   t ( n ) / R (t )  S (t ) . 3) Декартово произведение (R(n)  S(m)). Результат включает все комбинации кортежей R и S. t ( n m ) / u ( n )  R : (t [1]  u[1]  ...  t [n ]  u[n ])       (m)  v  S : (t [n  1]  v [1]  ...  t [n  m]  v [m])      3.7. Основные формулы 4) Проекция πi1,…,ik(R(n)). Результат отношения – выбранное подмножество атрибутов, в котором кортежи-дубликаты устраняются. i1, …, ik – атрибуты, по которым формируется результат. t /  u (k ) (n )   R : (t [1]  u[i1]  ...  t [k ]  u[i k ]) . 5) Селекция σF(R(n)). F – формула, образованная константами, названиями элементов отношения, арифметическими операторами сравнения, логическими операторами. Селекция – множество кортежей, принадлежащих R, таких что при подстановке соответствующих элементов отношения в формулу F становится истинной. t (n)  / R (t )  F . 3.8. Теорема о композиции реляционных выражений. Формулы дополнительных операций Если Е – выражение реляционной алгебры, то существует эквивалентная ему правильная формула реляционного исчисления с переменными-кортежами. Дополнительные операции: 1. Пересечение R ( n ) S ( n )  R ( n )  (R ( n )  S ( n ) ). t 2. Θ – соединение. R ( n ) (n)  / R (t )  S (t ) . S ( m )   i ( n  j ) (R  S ). Здесь Θ – арифметический оператор i j сравнения, i, j – элементы R и S. t ( n m ) / u ( n )  R : (t [1]  u[1]  ...  t [n ]  u[n ])       (m)  v  S : (t [n  1]  v [1]  ...  t [n  m]  v [m])  (u[i ] v [ j ])     3.8. Теорема о композиции реляционных выражений. Формулы дополнительных операций 3. Естественное соединение. R(n ) S ( l )   i 1,...,im ( R. A1S. A1...R. Ak S. Ak (R  S )). i1, …, im – список всех атрибутов от- ношения (R x S), за исключением S.A1, …, S.Ak. Aj – имена столбцов R и S.   t ( m ) / u ( n )  R : (t [1]  u[i1]  ...  t [k ]  u[i k ])       (l )   v  S : ( t [ k  1]  v [ i ]  ...  t [ m ]  v [ i ])    k 1 m    u [ A ]  v [ A ]  u [ A ]  v [ A ]  ...  u [ A ]  v [ A ] 1 1 2 2 k k     4. Частное R ( n )  S ( k )   1,..,n k (R )   1,..,n k ( 1,..,n k (R )  S )  R ). n – арность R, k – арность S, n > k. S  R. Частное строится на основе теоремы о преобразованиях. 1)  1,2,...,nk ( R) t ( nk )  /  u ( n )   R(u )  (t[1]  u[1])  (t[2]  u[2])  ...  (t[n  k ]  u[n  k ])  2)  1,2,...,nk ( R)  S   (n) (n) ( k )  R (u )  S (v )  (t[1]  u[1])  (t[2]  u[2])  ...  (t[ n  k ]  u[ n  k ])   t /  u  v    (t[n  k  1]  v[1])  (t[n  k  2]  v[2])  ...  (t[n]  v[k ])        ( R)  S   R 3)  1,2,...,nk  ( n )  R(t )  R(u )  S (v)  (t[1]  u[1])  (t[2]  u[2])  ...  (t[ n  k ]  u[ n  k ])   (n) (k ) t /  u  v      (t[n  k  1]  v[1])  (t[ n  k  2]  v[2])  ...  (t[ n]  v[ k ])     1,2,...,nk ( R)  S   R 4) 1,2,...,nk t ( nk ) /  w( n )  u ( n )  v ( k ) [ R( w)  R(u )  S (v)  ( w[1]  u[1])  ...  ( w[n  k ]  u[n  k ])     ( w[n  k  1]  v[1])  ...  ( w[n]  v[k ])  (t[1]  w[1])  ...  (t[ n  k ]  w[ n  k ])]   ( R)   1,2,...,nk  1,2,...,nk ( R)  S   R 5) 1,2,...,nk t ( nk ) /  p ( n )  w( n )  u ( n )  v ( k )  : R ( p )  t[1]  p[1]  ...  t[n  k ]  p[n  k ]       R( w)  R(u )  S (v)  ( w[1]  u[1])  ...  ( w[n  k ]  u[n  k ])      ( w [ n  k  1]  v [1])  ...  ( w [ n ]  v [ k ])  ( t [1]  w [1])  ...  ( t [ n  k ]  w [ n  k ])        