30378

Информационное обеспечение САПР. Реляционная модель баз данных

Лекция

Информатика, кибернетика и программирование

Лекция: Информационное обеспечение САПР окончание Рассматриваются реляционная сетевая и иерархическая модели баз данных о которых в общем излагалось в предыдущей лекции. Реляционная модель баз данных Реляционная база данных разработанная Э. Тем самым теория реляционных баз данных становится областью приложения математической логики и современной алгебры и опирается на точный математический формализм. В реляционных базах данных основные операции – включение удаление модификация и запрос данных – применяются к кортежам и доменам.

Русский

2013-08-24

320 KB

9 чел.

11. Лекция: Информационное обеспечение САПР (окончание)

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

11.1. Реляционная модель баз данных

Реляционная база данных, разработанная Э.Ф. Коддом (Е. F. Codd) в 1970 г., – это конечный набор конечных отношений (таблиц) вида рис. 10.3,б. Над отношениями можно осуществлять различные алгебраические операции. Тем самым теория реляционных баз данных становится областью приложения математической логики и современной алгебры и опирается на точный математический формализм.

Каждое отношение имеет свое имя; столбцы отношения соответствуют тому или иному атрибуту, имеющему имя и значения. Элементы отношения, соответствующие одной строке, составляют кортеж отношения (рис. 10.3, б). Арность кортежа – число значений атрибутов в кортеже, т.е. число атрибутов в отношении [7,13, 31].

Схема отношения – список имен атрибутов вместе с именем отношения; так, для рис. 10.3,а схема отношения – ТРАНЗИСТОРЫ (p, Iк max, Pк, Cк), для рис. 10.3, б – ИМЯ ОТНОШЕНИЯ (A, B, С, D).

Домен – множество значений атрибутов (в том числе и только одного атрибута – один столбец). Вообще столбцы не обязательно являются поименованными, а порядок следования элементов в картежах также несущественен.

Существует три подхода к анализу реляционных БД и формированию запросов в них: реляционная алгебра, реляционное исчисление на переменных-кортежах и реляционное исчисление на переменных-доменах.

В реляционных базах данных основные операции – включение, удаление, модификация и запрос данных – применяются к кортежам и доменам.

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

При удалении данных должны быть заданы отношение и значения атрибутов, образующих ключ удаляемых кортежей.

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

Запрос в реляционных базах данных может быть сформулирован к одному или нескольким отношениям (таблицам). Например имеется запрос: указать типы всех транзисторов и их Pк, для которых Ск > 15 пФ. Тогда значение атрибута Ск = 15 пФ. Затем на печать выдается новый файл-отношение "Тип транзистора, Рк, β". Могут быть более сложные запросы: например, определить мощности рассеивания транзисторов, для которых β 40, Iк max > 2а, Ск < 150 пФ и т. д. Тогда эти значения составляют ключ, и по ним составляется новое отношение Рк.

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

Основные операции реляционной алгебры приведены в табл. 11.1. В ней даны исходные отношения, результаты операций, а также в ряде случаев теоретико-множественное представление операций. Первые пять операций являются основными, остальные – дополнительные, которые могут быть выражены через пять основных.

Объединение отношений R S – это множество кортежей (отношений), принадлежащих отношениям R, S или им обоим; отношения R и S должны иметь одинаковую арность.

Разность отношений R – S – множество кортежей, принадлежащих R, но не принадлежащих S. Отношения R и S также должны иметь одинаковую арность.

Декартово произведение отношений R x S – одна из основных операций по затратам машинного времени при формировании запросов к реляционной БД. При умножении отношений к каждому кортежу первого отношения (R) присоединяется каждый кортеж второго отношения (S) – конкатенация кортежей; при этом отношения R и S могут иметь одинаковую или различную арность. При декартовом умножении арности исходных отношений складываются, а количества кортежей – перемножаются.

Проекция отношения R[X,Y (R)] – операции выборки по столбцам (атрибутам), приведенным в обозначении проекции.

Например, C,A (R) — отношение, составленное из атрибутов С и А отношения R; 2,3 (R) — отношение, составленное из 2-го и 3-го атрибутов отношения R, при этом арность проекции равна числу имен в ее обозначении.

Селекция отношения R [σF (R)] — операция выборки по строкам (кортежам), удовлетворяющим формуле F. В формулу входят операнды, являющиеся константами или номерами (именами) атрибутов, арифметические операторы сравнения: <, =, >, , , и логические операторы (И), (ИЛИ), (НЕ).

Например, σB="f"(R) обозначает множество кортежей, в которых компоненты атрибута В равны f, или σ2>3D=A(R) обозначает множество кортежей, в которых компоненты 2-го атрибута больше компонентов 3-го атрибута и одновременно равны компоненты атрибутов А и D).

Пересечение отношений RS есть краткая запись для отношения R – (R – S) и обозначает множество кортежей, принадлежащих одновременно R и S.

Частное отношений — множество кортежей, содержащих r – s первых компонентов кортежей отношения R, в которых остальные (s) компонентов принадлежат отношению S.

Соединение (θ-соединение) отношений — это селекция (с формулой θ) декартова произведения отношений R и S:

В частности, означает, что сначала надо выполнить декартово произведение отношений R и S, а затем в новом отношении выполнить селекцию по формуле А < D.

Эквисоединение отношений — это θ-соединение, если в формуле θ используются только равенства (см. таблицу 11.1, строку 9).

Естественное соединение — это эквисоединение, которое выполняется для атрибутов отношений R и S с одинаковыми именами (см таблицу 11.1, строку 10). Так как для указанных атрибутов имена и значения полностью совпадают, то один из них в каждой паре в результирующем отношении устраняют. Естественное соединение — одна из основных операций при формировании запросов к реляционной БД.

Композиция отношений — это проекция θ-соединения или проекции селекции декартова произведения. По сути, естественное соединение — тоже частный случай композиции. Декомпозиция отношений — это операция, обратная композиции, т. е. восстановление двух отношений из одного, естественное соединение которых образует исходное отношение.

Таблица 11.1. Операции реляционной алгебры

Операции

Исходные отношения

Результат операции

1

Объединение

2

Разность

См. п. 1

3

Декартово произведение

4

Проекция

5

Селекция

6

Пересечение

7

Частное

8

Соединение (θ-соединение)

9

Эквисоединение

См п. 8

10

Естественное соединение

11

Композиция

См п. 8

12

Декомпозиция

Операция, обратная композиции

В терминах реляционной алгебры легко записываются запросы к реляционной базе данных. Если задано несколько отношений, то запрос выражается в виде операции композиции к этим отношениям. Однако формальное применение композиции — последовательное применение декартова произведения всех отношений, селекции и проекции — приводит к неоправданным затратам машинного времени. Поскольку арность и число кортежей в исходных отношениях могут быть велики (десятки, сотни), нецелесообразно формировать сначала все декартово произведение, а только затем применять селекцию и проекцию. Так, если два отношения имеют по n кортежей и время доступа к каждой записиt0, то общее время доступа к памяти для формирования полного декартова произведения Tдоступа = n2t0. Если n = 104, t0 = 10 мс, то Tдоступа = 106 11,5 сут. Поэтому с

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

  •  выполнять селекции и проекции как можно раньше до декартова умножения (с целью сокращения арности и количества кортежей);
  •  собирать в каскады селекции и проекции, чтобы выполнять их за один просмотр файла;
  •  обрабатывать (сортировать, индексировать) файлы перед выполнением соединения;
  •  комбинировать проекции с предшествующими или последующими двуместными операциями.

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

Таблица 11.2. Эквивалентные выражения реляционной алгебры

Название

Результат операции

1

Закон коммутативности для соединений и декартовых произведений

2

Закон ассоциативности для соединений и произведений

3

Каскад проекций

4

Каскад селекций

5

Перестановка селекции и проекции

6

Перестановка селекции с произведением

7

Перестановка проекции с произведением

11.2. Сетевые модели баз данных

Как было сказано выше, сетевая модель данных реализует связи типа "многие ко многим". Сетевые базы данных разрабатывались Ассоциацией по языкам систем обработки данных КОДАСИЛ1) и ее рабочей группой DBTG. Первые исследования этой группы были направлены на создание языков программирования задач обработки данных, в частности, языка КОБОЛ. В дальнейшем были разработаны специальные предложения DBTG для систем управления сетевыми базами данных.

Наибольшее развитие получили две группы языков: языки описания данных (ЯОД КОДАСИЛ) и языки манипулирования данными (ЯМД КОДАСИЛ). Первые служат для описания сетевой базы данных, предназначенной для коллективного использования программами, написанными на различных языках. Вторые — для включения, удаления и модификации данных в сетевой БД.

Сформулируем основные определения ЯОД КОДАСИЛ и укажем на соответствие определений в сетевых и реляционных БД. Пример структуры сетевой базы данных приведен на рис. 11.1. Там же условно показаны основные термины сетевой БД.

Элемент данных — наименьшая единица поименованных данных, представляемых в БД значением, — соответствует значению атрибута в реляционной БД (РБД).

Агрегат данных — совокупность элементов данных внутри одной записи — соответствует домену в РБД.


Рис. 11.1.  Структура сетевой базы данных

Запись — совокупность элементов данных, состоящая из элементов или агрегатов данных — соответствует кортежу в РБД. Она характеризуется типом записи, которому соответствует произвольное число ее экземпляров.

Набор — совокупность записей — соответствует отношению в РБД; характеризуется типом набора (имя отношения в РБД). Каждый экземпляр набора должен содержать один экземпляр объявленного для него типа записи — владельца — и один или несколько типов записей — членов набора. Например, если тип набора ТРАНЗИСТОРЫ СВЧ, то тип записи для владельца набора — ТРАНЗИСТОРЫ; тип записей членов набора — марки транзисторов СВЧ (рис. 11.1).

Область — совокупность записей, не сохраняющая соответствия "владелец — член набора". Область может содержать экземпляры одного (или более) типа записей, а экземпляры одного типа записи могут находиться в нескольких областях (рис. 11.1); конкретный же экземпляр записи может приписываться только одной области.

Схема БД — глобальное описание сетевой БД в приведенных терминах с точки зрения администратора базы данных.

Подсхема БД — часть схемы БД с точки зрения прикладного программиста, ограничивающая сферу действия последнего. Это предохраняет от случайных изменений в тех частях БД, к которым он не должен обращаться.

База данных представляет собой совокупность всех записей, наборов и областей, управляемых некоторой схемой.

Возможны различные частные структуры сетевых баз данных, соответствующих различным схемам. Это последовательные структуры, деревья, циклы и сети.

Последовательные структуры данных являются простейшими из них и представлены в БД одним набором, члены которого упорядочены определенным образом. В древовидных структурах — иерархических — каждая запись (кроме одной, называемой корневой) связана с нулем или несколькими различными записями, расположенными ниже ее по иерархии, и с одной записью, расположенной выше. Корнем дерева служит запись наивысшего уровня, например, ТРАНЗИСТОРЫ на рис. 11.1. Так как каждый набор может иметь произвольное число записей (членов этого набора) и допускается произвольное число типов наборов, дерево может быть любой ширины и глубины.

Циклы — замкнутые структуры в БД. Различают однотипные и многотипные циклы. В однотипных циклах один и тот же тип записи объявляется и владельцем, и членом одного и того же типа набора. Например, тип набора СОСТОИТ ИЗ (рис. 11.1), означает, что каждый прибор может, в свою очередь, состоять из других приборов. В многотипных циклах владелец одного типа набора является членом предыдущего.

Сети — наиболее общая структура данных по сравнению с деревьями и циклами, в которой каждый тип записи может быть членом более чем одного типа набора (рис. 11.1).

Разработан синтаксис ЯОД КОДАСИЛ, включающий в себя различные типы сетей описания данных, схемы, области, записи и набора.

11.3. Иерархическая модель базы данных

Иерархические модели баз данных исторически возникли одними из первых. В качестве примера рассмотрим иерархическую БД — Information Management Systems (IMS), разработанную в 1967 году. Существуют соответствия терминов, описывающих сетевые модели БД КОДАСИЛ и иерархическую IMS, в частности: тип набора — связь; тип записи — тип сегмента; запись — владелец набора — исходный сегмент; запись — член набора — порожденный сегмент и т. д. (рис. 11.2).

На вершине иерархической структуры только один тип сегмента — тип корневого сегмента. Связь между типами сегментов указывают стрелкой. Запись IMS (или запись иерархической базы данных) означает, что экземпляр корневого сегмента связан со всеми экземплярами записей нижнего уровня.

В иерархической структуре любой тип записи не может иметь более одного владельца (порожденный сегмент). Поэтому и не нужно вводить понятие "тип набора".


Рис. 11.2.  Структура иерархической модели баз данных

Была рассмотрена физическая база данных. Однако существуют еще и логические отношения, связывающие две (или более) физические БД дерева (рис. 11.2). С введением этого понятия могут быть связаны два исходных сегмента: один из них, находящийся в той же базе данных, что и рассматриваемый сегмент, называют физически исходным сегментом, другой — логически исходным сегментом. Логические связи на рис. 11.2 показаны пунктирными линиями. С помощью иерархических структур и логических отношений можно представить и некоторые сетевые структуры. Существуют некоторые ограничения на взаимное расположение физически и логически исходных и порожденных сегментов.

В памяти ЭВМ файлы иерархической базы данных IMS могут быть представлены четырьмя способами: HSAM — последовательный метод доступа, HISAM — индексно-последовательный, HDAM — прямой, HI DAM — индексно-прямой2).

При последовательном методе доступа дерево БД просматривается сверху вниз и слева направо. Для поиска нужной записи необходимо просматривать все дерево. Команды включения, удаления и замены сегментов (записей) не допускаются.

При индексно-последовательном способе записи БД хранятся в цепочке блоков памяти, в качестве ключей используются элементы корневого сегмента. Каждая запись расположена в одном блоке первичной области и при необходимости переходит в специальную область переполнения.

В случае прямого метода доступа загрузка сегментов в базу данных осуществляется в произвольном порядке и обращение к ним не последовательное, как в предыдущем способе, а прямое — по значению ключа. При удалении некоторых сегментов пространство памяти может быть использовано повторно.

В индексно-прямом методе доступа используются корневые сегменты, расположенные по возрастанию ключа в так называемой начальной базе данных и указывающие на те или иные рабочие сегменты базы данных.

Контрольные вопросы и упражнения

  1.  Каково назначение и состав ИО САПР?
  2.  Что входит в банк данных?
  3.  Для чего предназначены СУБД?
  4.  Перечислите требования, предъявляемые к базе данных.
  5.  Приведите примеры информационного согласования программ при построении баз данных.
  6.  Какие базы данных называют сетевыми?
  7.  Какие базы данных называют реляционными?
  8.  Приведите основные операции реляционной алгебры.
  9.  Перечислите основные понятия для различных уровней представления данных.
  10.  Укажите основные особенности и характеристики трех моделей представления данных.
  11.  Докажите необходимость оптимизации запросов к базам данных.
  12.  Приведите основные характеристики и параметры сетевых СУБД.
  13.  Приведите основные характеристики и параметры иерархических СУБД.
  14.  Что составляет кортеж отношения?
  15.  Что означает "арность кортежа"?
  16.  Что называют доменом?


 

А также другие работы, которые могут Вас заинтересовать

27559. Юридические факты 30.5 KB
  Юридические факты – конкретные жизненные обстоятельства события действия вызывающие в соответствии с нормами права наступление определенных правовых последствий – возникновение изменение или прекращение правовых отношений. Юридические факты имеют ряд признаков: по своему содержанию это реальные жизненные обстоятельства явления; данные жизненные обстоятельства предусмотрены нормами права; они вызывают наступление определенных юридических последствий; юридический факт несет в себе информацию о состоянии общественных отношений; ...
27560. Позитивный и ретроспективный аспект юридической ответственности 27.5 KB
  Юридическая ответственность – возникшее в результате лично совершенного правонарушения и предусмотренное юридической нормой политикоправовое состояние когда компетентный орган должностное лицо или гражданин на основе закона или в специальной форме требует от правонарушителя отчет в совершенном деянии возлагает на него определенную меру лишений а правонарушитель претерпевает неблагоприятные последствия нарушения юридической нормы. 1 Положительная позитивная ответственность – одна из характеристик правомерного поведения. Все несут...
27561. Политика и право: назначение и соотношение 28 KB
  В этой связи теория государства и права носит политический характер. Право воздействует на политику по нескольким направлениям: 1 посредством публичной власти закрепляются политический строй общества механизм функционирования политической системы политические свободы граждан 2 в результате воздействия права на политику все виды политической деятельности осуществляются как права субъектов а не как проявление их силы авторитета иных качеств 3 право придает легитимность политическим решениям и органам государственной власти 4 право...
27562. Субъекты права в России. Правосубъектность 29 KB
  Субъекты правоотношений – это участники правовых отношений имеющие субъективные права и юридические обязанности. Традиционно все многочисленные субъекты права подразделяются в юридической литературе на два вида: индивиды физические лица и организации юридические лица. Виды коллективных субъектов права: 1.
27563. Сущность права. Классовое и общечеловеческое в праве 28 KB
  Сущность права – это главная внутренняя относительно устойчивая качественная основа права которая отражает его истинную природу и назначение в обществе Основные подходы к пониманию сущности права: 1 сущность права – это возведенная в закон воля той социальной группы которая обладает реальной государственной властью марксистколенинская теория. 2 сущность права – это социальная свобода соединенная с социальной ответственностью. 3 сущность права – это реальное общественное отношение которое складывается в социальнонеоднородном обществе.
27564. Теория государства и права в системе юриспруденции. Место в системе других социальных наук 30 KB
  В свою очередь юридические науки можно условно поделить на четыре основные группы: – общая теория государства и права; – историкоправовые науки; – отраслевые науки; – прикладные науки криминалистика судебная медицина психиатрия. Особенность теории государства и права как науки состоит в том что она является: – гуманитарной наукой предметом изучения которой составляют общественные явления – право и государство. Этой особенностью она отличается от других наук – естественных и технических; – политикоюридической наукой изучающей такие...
27565. Теория и практика формирования правового государства в России 29.5 KB
  Теория правового государства насчитывает многовековую историю. Многие мыслители начиная с античной древности и вплоть до наших дней занимаются проблемой создания рационального государства которое отвечало бы представлениям людей о свободе и справедливости законности и демократии. В числе ученых философов и правоведов принимавших участие в выработке и обосновании теории правового государства необходимо упомянуть Аристотеля Платона Полибия Ш.
27566. Типология государств (Кельзена, Еллинека) 27.5 KB
  Типология государств Кельзена Еллинека. Типология государства – традиционно рассматривают как теория учение о типах государств когдалибо существовавших в истории человеческого общества или существующих в настоящее время. Типология государства – это процесс систематизации государств с учетом их сущностных свойств для повышения эффективности в теоретической и практической деятельности по изучению государства и правоприменения. Под типом государства понимаются взятые в единстве общие черты различных государств система их важнейших...
27567. Типология государства: формационный подход 31 KB
  Типология государства: формационный подход. Типология государства – традиционно рассматривают как теория учение о типах государств когдалибо существовавших в истории человеческого общества или существующих в настоящее время. Типология государства – это процесс систематизации государств с учетом их сущностных свойств для повышения эффективности в теоретической и практической деятельности по изучению государства и правоприменения. Тип государства и права ставится в зависимость от типа общественноэкономической формации.