Иерархический и сетевой подходы

Для организации поиска нужных записей используются понятия ключа и связи.

Ключ - уникальное имя записи. С помощью ключа производится идентификация каждой конкретной записи, а также упорядочение записей в файле. Упорядочение по ключу может быть либо прямым, либо выполнено с помощью хеш-функции.

Прямое упорядочение предполагает лексикографическое расположение записей: записи могут быть записаны в порядке увеличения ключа. При этом простой ключ можно рассматривать как некоторое число.

Хэш-функция производит пересчет ключа в адрес записи на файле. Эта операция осуществляется СУБД всякий раз при поиске новой записи по ключу.

[NN5] Лекция 6

Информационное обеспечение САПР (продолжение)

Реляционный подход

Реляционные модели данных в последнее время получили широкое распространение вследствие простой формы представления данных, а также благодаря развитому теоретическому аппарату, позволяющему описывать различные преобразования реляционных данных. Основу реляционной модели данных составляет понятие отношения, представляющего собой подмножество декартова произведения доменов. Домен - это некоторое множество элементов, например множество целых чисел или множество допустимых значений, которые может принимать объект по некоторому свойству.

Декартовым произведением доменов D1, D2,..,Dk

D1*D2*....*Dk,

где

..........................................

называется множество всех кортежей длины k, т.е. состоящих из k элементов - по одному из каждого домена

 

Таким образом, декартово произведение

 

Пример (рис. 6.1).

Если D₁={A, 2}, D₂={B, C} D₃={4, 5, D}, то k=3 и соответственно декартово произведение D= D₁ * D₂ *D₃ ={(A,B,4),(A,B,5),(A,B,D),

(A,C,4),(A,C,5),(A,C,D),

(2,B,4),(2,B,5),(2,B,D),

(2,C,4),(2,C,5),(2,C,D)}.

Отношением R на множествах D1,D2,...,Dk называется подмножество декартова произведения D1*D2*....*Dk, то есть R, определенное на множествах D1*D2*....*Dk есть некоторое множество кортежей:

Атрибутом А называется некоторе подмножество домена D. Например, для домена D3 атрибутом может быть A3=(4,5).

Для рассмотренного примера отношения имеют следующий вид

 

.

В ряде случаев отношения удобно представлять в виде таблицы, где каждая строка соответствует кортежу, а столбец атрибуту, например,

 

R1

A	B
A	C

 

 

R2

C

 

 

R3

	C	D
A	B
A	B
	B	D

 

 

Реляционное исчисление

Реляционное исчисление базируется на теоретических основах исчисления предикатов. Предикат P(x1,x2,...,xn) это функция, принимающая значения «Истина» или «ложь», от аргументов, определенных в конкретных областях D1,D2,...,Dn. При построении высказываний используются

логические связки, например

конъюнкция, дизъюнкция, отрицание,

 

термы сравнения с операциями

и др., а также кванторы существования и общности .

Рассмотрим пример применения кванторов. Высказывание - означает-что среди элементов множества X найдется, по крайней мере, один, при котором оказывается истинным неравенство, заключенное в скобках. Высказывание означает, что для всех элементов множества X некоторая функция f(x) больше заданного a.

В реляционном исчислении принято связывать отношением R(A1,...,An) некоторый предикат P(x1,...,xn), аргументы, которых имеют одинаковые области определения, таким образом, что если P(a1,a2,...,an)=1, то кортеж <a1,a2,...,an> принадлежит отношению , для i=1,n, в противном случае кортеж не входит в состав указанного отношения. Отсюда следует, что посредством задания некоторого предиката может быть задано и соответствующее ему отношение.

Из сказанного видно, что реляционное исчисление позволяет описать самые разнообразные виды искомых отношений. Однако отсутствие процедурности существенно затрудняет реализацию языков, основанных на реляционном исчислении. Решении этой проблемы возможно при использовании методов реляционной алгебры.

 

D₁

A 2

 

D₂ D₂

 

B C B C

 

 

D₃ D₃ D₃ D₃ 5 D 4 5 D 4 5 D 4 5 D

 

 

A,B,4 A,C,4 2,B,4 2,C,4

A,B,5 A,C,5 2,B,5 2,C,5

A,B,D A,C,D 2,B,D 2,C,D

 

Рис.6.1.Графическая интерпретация получения декартова

произведения

[NN6] Лекция 7