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

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

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

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

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

2)Основные возможности языка SQL. Предложения SQL.

SQL – ИСТОРИЯ (Эдгар Френк Кодд) создал и описал концепцию реляционных баз данных и реляционную алгебру [1969-1970]; для проектирования БД предложил аппарат нормализации отношений Группа под руководством М. Сенко разрабатывала подход к построению баз данных на основе бинарных отношений.Бинарное отношение покрывает все, но имеет недостатки – избыточность хранения, сложность управления. Важное свойство бинарных отношений – СУБД находится сразу во всех нормальных формах.Работы по созданию языка запросов к СУБД проводились в 1975-1979 гг. в исследовательском центре IBM. Результатом этой работы стало создание экспериментальной реляционной СУБД SYSTEM R. Одним из важнейших элементов SYSTEM R стал язык SEQUEL (Structered English Query Language) явившийся прототипом для SQL. Основными авторами языка являются Д. Чемберлен и Р. Бойс.На ряду с работами Чемберлена и Бойса в IBM развивалось другое направление в области реляционных языков, которым руководил М. Злуф. В отличае от SEQUEL это был графически-ориентированный язык для интерактивной работы. Он получил название QBE (Query-By-Example) – запросы на примерах. SQL нельзя в полной мере отнести к традиционным языкам программирования, он не содержит традиционные операторы, управляющие ходом выполнения программы, операторы описания типов и многое другое, он содержит только набор стандартных операторов доступа к данным, хранящимся в базе данных. Операторы SQL встраиваются в базовый язык программирования, которым может быть любой стандартный язык типа C++, PL, COBOL и т. д. Кроме того, операторы SQL могут выполняться непосредственно в интерактивном режиме.

Структура SQL В отличие от реляционной алгебры, где были представлены только операции запросов к БД, SQL является полным языком, в нем присутствуют не только операции запросов, но и операторы, соответствующие DDL — Data Definition Language — языку описания данных. Кроме того, язык содержит операторы, предназначенные для управления (администрирования ) БД.

Предложения Sql Определение Данных Создать: CREATE TABLE – создать таблицу CREATE INDEX – создать индекс CREATE VIEW – создать представление Удалить: DROP TABLE – удалить таблицу DROP INDEX – удалить индекс DROP VIEW – удалить представление Очистить таблицу:TRUNCATE TABLE МАНИПУЛИРОВАНИЕ ДАННЫМИ INSERT – добавить записи DELETE – удалить записи UPDATE – обновить (изменить значение) записи SELECT – выбрать

СОЗДАТЬ ТАБЛИЦУ  CREATE TABLE name (column1_name column1_type,  column2_name column2_type,...);

ЯЗЫК СТРУКТУРИРОВАННЫХ ЗАПРОСОВ (SQL - Structured Query Language). Общее подмножество основных операторов языка – создание удаление таблиц; создание, изменение, удаление записей. Другие СУБД могут иметь свой синтаксис, свои операторы.

3)Тупики. Способы разрешения.

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

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

Условия возникновения тупиков В 1971 г. Коффман, Элфик и Шошани сформулировали следующие четыре условия для возникновения тупиков. 1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются. 2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами). 3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.  4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи. Для тупика необходимо выполнение всех четырех условий.

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

Алгоритм страуса Простейший подход – игнорировать проблему тупиков, т.е. пожертвовать производительностью или удобством, чтобы ликвидировать тупик. Например, ОС Unix, имеющая в ядре ряд массивов фиксированной размерности, потенциально страдает от тупиков, даже если они не обнаружены. Например, суммарное число процессов в системе определяется размерностью таблицы процессов. Если таблица заполнена, вероятность этого ничтожна, но такое может произойти, то для программы, которая делает вызов fork, резонно подождать некоторое время и попытаться осуществить этот вызов вновь. Обнаружение тупиков Обнаружение тупика это установление факта, что возникла тупиковая ситуация и определение процессов и ресурсов, вовлеченных в эту ситуацию. Как правило, алгоритмы обнаружения применяются, когда выполнены первые три необходимых условия возникновения тупиковой ситуации. Затем проверяется наличие режима кругового ожидания. При этом активно используются уже упоминавшиеся графы распределения ресурсов.

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

Предотвращение тупиков за счет нарушения условий возникновения тупиков.

Если мы сможем организовать работу системы так, что, по крайней мере, одно из этих условий не удовлетворено, тупик не возможен.

 

Серия сообщений "Базы данных":
Часть 1 - Файловые системы. Назначение файловых систем.
Часть 2 - Особенности орган хранения данных
...
Часть 24 - Жизненный цикл базы данных. Информационные хранилища – OLAP-технология.
Часть 25 - Хранимые процедуры. Языки для написания хранимых процедур.
Часть 26 - Моделирование сетевых структур с использованием вспомогательной таблицы.
Часть 27 - Основные функции СУБД. Типовая организация СУБД. Жизненный цикл базы данных.
Часть 28 - Кластерные и распределенные СУБД. Пример: IBM DB2 Parallel Edition, MS SQL Server и Oracle. Применение триггеров
...
Часть 43 - Метод вспомогательной таблицы для случая произвольного графа. Отличия от случая моделирования иерархий
Часть 44 - Объектно-ориентированная модель и реляционная модель. Сходство и отличия.
Часть 45 - Использование «координатного» метода для моделирования иерархий и произвольных графов. Его достоинства и