объединение звёзд, полносвязная сеть, произвольный граф. Приведение сетевых структур к более простым. Семантические сети.

Сетевая модель организации данных является расширением иерархической модели. В иерархических структурах запись-потомок должна иметь только одного предка - в сетевой структуре данных потомок может иметь любое число предков. В сетевых моделях один и тот же тип записи может быть членом в нескольких групповых отношениях и одновременно быть владельцем в других. В иерархической модели база данных можеть иметь только древовидную структуру. Количество деревьев в БД определяется числом корневых записей. Каждая БД в системе реализует единую модель данных. В качестве основы этой модели принят сетевой принцип организации данных. БД состоит из множества элементарных записей, для их обозначения в предлагаемой модели используется термин "атом". Количество атомов в БД не ограничено, каждому атому в момент его создания выделяется идентификатор, уникальный в рамках этой БД, который является виртуальным адресом атома, остается неизменным в течение всего времени существования атома и используется для выполнения любых операций с атомом (для обращения к нему). Таким образом, в БД реализован механизм единой виртуальной адресации всех элементарных записей данных (атомов). Каждый атом содержит данные (тело атома), которые в общем случае рассматриваются как двоичные данные. Тело атома может иметь произвольный размер, в том числе нулевой (пустое тело). Каждый атом имеет множество ссылок на другие атомы в этой же БД, которые представляют собой виртуальные адреса других атомов. Атом может иметь произвольное количество ссылок на другие атомы, в том числе ни одной. С помощью ссылок реализуется механизм связывания данных. Ссылки являются однонаправленными, то есть: если атом А ссылается на атом Б, то обратное из этого не следует, но и не опровергается

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

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

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

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

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

Все другие варианты основаны на неполносвязных топологиях, когда для обмена данными между двумя компьютерами может потребоваться промежуточная передача данных через другие узлы сети. Ячеистая топология (mesh) получается из полносвязной путем удаления некоторых возможных связей. Топология Общая шина.

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

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

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

организовать сложную сеть с произвольным графом (компы раскиданы как попало и связаны чем придется :)) и различными весовыми коэффициентами ребер графа (т.е. с различной пропускной способностью между разными компами). Древовидные структуры данных более удобны для реализации в памяти ЭВМ, чем сетевые, и требуют менее сложного программного обеспечения. Поэтому в ряде случаев сетевые структуры заменяются совокупностью деревьев. При этом сложные сети вначале приводятся к простым, а затем простые сети заменяются деревьями. Сложные сети приводятся к простому виду путем введения избыточности. При этом все элементы сложной сети повторяются дважды. Зтем простые сети заменяются деревьями также путем введения избыточности. При этом ряд элементов сети также повторяется.

. Домен - это семантическое понятие. Домен можно рассматривать как подмножество значений некоторого типа данных имеющих определенный смысл. Домен характеризуется следующими свойствами: Каждый столбец имеет свой тип данных. внутри домена могут лежать поддомены. Домен имеет уникальное имя (в пределах базы данных). Домен определен на некотором простом типе данных или на другом домене. Домен может иметь некоторое логическое условие, позволяющее описать подмножество данных, допустимых для данного домена. Домен несет определенную смысловую нагрузку.Кортеж - это множество пар {имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута. "Значение" является допустимым значением домена данного атрибута Попросту говоря, кортеж - это набор именованных значений заданного типа. Кортеж – строки внутри таблицы.Имя кортежа – имя столбца, значение – внутри столбца.Отношение - это множество кортежей, соответствующих одной схеме отношения. На самом деле, понятие схемы отношения ближе всего к понятию структурного типа данных в языках программирования. Отношение - таблица: 1заголовок и шапка.

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

В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language). Язык SQL представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления, использующий синтаксис, близкий к фразам английского языка и расширенный дополнительными возможностями, отсутствующими в реляционной алгебре и реляционном исчислении. Язык доступа к данным называется реляционно полным, если он по выразительной силе не уступает реляционной алгебре т.е. любой оператор реляционной алгебры может быть выражен средствами этого языка. Каждая строка должна отличаться от любой другой и обладать уникальностью. Хотя бы в одном из столбцов находится нечто, что делает ее отличной от др.Целиком вся строка внутри таблицы повторяться не может. Набор столбцов, значения в которых уникальны – ключ. Ключ может быть для таблицы ни один. Минимальный набор столбцов обычно объявляют первичным ключом. Все остальные – возможные. Таблицы могут ссылаться на друг друга.Внешний ключ – те ключи, которые указывают на значения другой таблицы.

Отношения:

1. Один к одному

       2.Один ко многим

       3. Многие ко многим

Реляционная Модель – Терминология Сущность(объект реального мира, может описываться набором отношений) – отношение – таблица. Кортеж – запись – строка. Атрибут – поле – столбец, колонка.

3)Проблема «грязного чтения данных». Способы разрешения.

Рассмотрим следующий сценарий совместного выполнения транзакций 1 и 2. Транзакция 1 изменяет объект базы данных A. Параллельно с этим транзакция 2 читает объект A. Поскольку операция изменения еще не завершена, транзакция 2 видит несогласованные "грязные" данные (в частности, операция транзакции 1 может быть отвернута при проверке немедленно проверяемого ограничения целостности). Это тоже не соответствует требованию изолированности пользователей (каждый пользователь начинает свою транзакцию при согласованном состоянии базы данных и в праве ожидать видеть согласованные данные). Чтобы избежать ситуации чтения "грязных" данных, до завершения транзакции 1, изменившей объект A, никакая другая транзакция не должна читать объект A (минимальным требованием является блокировка чтения объекта A до завершения операции его изменения в транзакции 1).

Зависимость D1. Феномен «грязное чтение» Транзакция T1 считывает объект данных O прежде, чем T2 произведет операцию записи над ним, потом T2 делает следующее изменение объекта. Версия, считанная T1, может оказаться противоречивой (могут быть нарушены ограничения логической целостности данных), так как Т1 считала не окончательное значение O (значение фиксируется при выполнении операции commit. Феномен грязного чтения будет наблюдаться и при следующих последовательностях завершения транзакций ((T1, commit) или (T1, rollback))  и ((T2, commit) или (T2, rollback))в любом порядке. Таким образом, полное описание данного феномена будет включать все четыре варианта завершения транзакций T1 и T2.

Приведем пример возникновения такой зависимости транзакций — вновь с информацией о положении точки на плоскости. Пусть работают две транзакции, каждая их которых передвигает точку по кривой x+y = 120. Выполняются операции модификации координаты x и модификации координаты y; пусть каждая транзакция считывает значение точки и меняет значение так, чтобы y оказался меньше на 10, а x — больше на 10. Предположим, обе транзакции работают с точкой v = (10,110). Очевидно, что при выполнении в следующей последовательности операций будет возникать рассогласование данных:<10,110> (->) (T1,R(x,y)) <10,110> (->) (T1,W(y)) <10,90> (->) (T2,R(x,y)) <10,90> (->) <10,80> (->) (T2,W(x)) <20,80> (->) (T1,commit)(!!!)...

Произошло рассогласование данных: появилась точка (20,80), которая не удовлетворяет условию «x+y = 120». Транзакция T2 рассогласовала данные, и эти данные оказались зафиксированными транзакцией T2 (она «ничего не знает» о параллельно работающей с ней T1). Это означает, что любая другая транзакция может считать эти некорректные данные в момент времени (!!!); последствия рассогласования перестают быть контролируемыми.

 

Серия сообщений "Базы данных":
Часть 1 - Файловые системы. Назначение файловых систем.
Часть 2 - Особенности орган хранения данных
...
Часть 29 - Иерархическая СУБД IBM IMS и язык DL1. Особенности реализации для работы на кластере (Sysplex).
Часть 30 - Технология оперативной обработки транзакций – OLTP. Мониторы транзакций на примере IBM CICS и TPF
Часть 31 - Понятие сетевой организации данных. Структуры типа «звезда»,
Часть 32 - Основные реляционные СУБД: IBM DB2, ORACLE, MS SQL Server, Informix. Сравнение.
Часть 33 - Основные положения теории массового обслуживания (теория очередей).
...
Часть 43 - Метод вспомогательной таблицы для случая произвольного графа. Отличия от случая моделирования иерархий
Часть 44 - Объектно-ориентированная модель и реляционная модель. Сходство и отличия.
Часть 45 - Использование «координатного» метода для моделирования иерархий и произвольных графов. Его достоинства и