Иерархическая система ос windows информационная модель в виде дерева

Обновлено: 07.07.2024

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

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

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

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

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

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

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

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

Затем иерархическая СУБД проверит содержимое этого элемента и его связи, если связей опять будет несколько, то она отправится опять-таки в крайний левый дочерний элемент, чтобы проверить его содержимое, проверив его содержимое она увидит, что у этого узла нет дочерних элементов и вернется в родительский узел этого узла, чтобы проверить, есть ли у него еще дочерние элементы. И так постепенно, узел за узлом, спуская и поднимаясь по иерархии узлов СУБД переберет все узлы и выдаст нам все записи, в которых есть слово «сотрудник». Ну, думаю, что с иерархической моделью данных мы более-менее разобрались (если не разобрались, то пишите в комментарии), можно приступить к рассмотрению структуры иерархической базы данных.

Структура иерархической базы данных

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

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

Экземпляр сегмента образуется из конкретных значений полей данных. Тип сегмента – это именованная совокупность всех типов полей данных, входящих в данный сегмент. Если ориентироваться по рисунку выше, то тип сегмента – это родительский элемент и все его дочерние элементы. Как я уже говорил: иерархическая модель данных базируется на теории графов, но если структура сетевой БД описывается ориентированным графом (графом со стрелочками), то структура иерархической базы данных описывается неориентированным графом. Характерной особенностью структуры иерархической модели данных является то, что у любого потомка или дочернего элемента может быть только один предок или родительский элемент.

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

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

Преобразование концептуальной модели в иерархическую модель данных

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

Как вы помните: дуги, соединяющие узлы между собой, – это связи. Связи бывают один к одному и один ко многим. Преобразование связей один ко многим происходит автоматически в том случае, если потомок иерархического дерева имеет только одного предка. Происходит это следующим образом: Каждый объект с его атрибутами, участвующий в такой связи, становится логическим сегментом. Между двумя логическими сегментами устанавливается связь типа «один ко многим». Сегмент со стороны «много» становится потомком, а сегмент со стороны «один» становится предком. Согласитесь, что преобразование в иерархическую модель данных похоже на преобразование в сетевую модель.

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

Управление иерархическими данными

У иерархической модели данных существует два средства управления данными: языковые средства описания данных (ЯОД) и языковые средства манипулирования данными (ЯМД). Физическая структура иерархической базы данных описывает: логическую структуру иерархической модели данных и саму структуру хранения базы данных.

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

иерархически последовательный;
иерархически индексно-последовательный;
иерархически прямой;
иерархически индексно-прямой;
индексный.

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

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

найти указанное дерево БД;
перейти от одного дерева к другому;
найти экземпляр сегмента, удовлетворяющий условию поиска;
перейти от одного сегмента к другому внутри дерева;
перейти от одного сегмента к другому в порядке обхода иерархии.

Примеры типичных операторов поиска данных с возможностью модификации:

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

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

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

В первую очередь, это связано с тем, что реляционные базы не приспособлены к хранению иерархических структур (как, например, XML-файлы), структура реляционных таблиц представляет из себя простые списки. Иерархические же данные имеют связь «родитель-наследники», которая не реализована в реляционной структуре.

Тем не менее, задача «хранить деревья в базе данных» рано или поздно возникает перед любым разработчиком.

Ниже мы подробно рассмотрим, какие существуют подходы в организации хранения деревьев в реляционных БД, а также рассмотрим инструментарий, который нам предоставляет ORM Doctrine для работы с такими структурами.

Список смежных вершин (Adjacency List)

Описание структуры

Как правило, такая структура данных предполагает хранение информации о смежных вершинах нашего дерева. Давайте рассмотрим простейший граф с темя вершинами (1,2,3):

Рис. 1. Граф с тремя вершинами

Как видим каждый элемент данного графа хранит информацию о связи с другими элементами, т.е.:

Фактически, для построения дерева такой граф избыточен, т.к. для привычной ветвистой структуры нам нужно хранить только связь «родитель-наследник», т.е.:

Тогда мы получим дерево с одним корневым элементом (1) и двумя ветками (2,3):

Рис. 2. Граф дерева

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

Итак, чтобы хранить в базе данных иерархическую структуру методом списка смежных вершин (Adjacency List), нам необходимо хранить информацию о связях «наследник-родитель» в таблицах с данными. Давайте рассмотрим реальный пример дерева:

Рис. 3. Древовидная структура методом смежных вершин

На рисунке квадратами обозначены узлы деревьев. У каждого узла есть имя (верхний прямоугольник внутри квадрата), идентификатор (левый нижний квадрат) и ссылка на идентификатор родителя (правый нижний квадрат). Как видно из Рис. 3, каждый наследник в такой структуре ссылается на своего предка. В терминах БД мы можем это отобразить следующим образом в виде таблицы:

Рис. 4. Таблица данных дерева, построенная методом списка смежных вершин

Или же в виде SQL:

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

Проблемы с чтением из БД менее заметны, если вычитывать все дерево целиком. Это достаточно простой запрос:

Однако в дальнейшем такая выборка подразумевает достаточно емкую программную пост-обработку данных. Сначала нужно рекурсивно перестроить данные с учетом связей «предок-наследник» и лишь потом их можно будет использовать для вывода куда-либо.

Другой вариант чтения дерева целиком:

Результат в данном случае будет такой:

Хотя данные в таком виде уже более приспособлены сразу для вывода, но, как видите, главный недостаток такого подхода — необходимо достоверно знать количество уровней вложенности в вашей иерархии, кроме того, чем больше иерархия, тем больше JOIN'ов — тем ниже производительность.

Тем не менее, данный способ обладает и существенными достоинствами — в дерево легко вносить изменения, менять местами и удалять узлы.

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

С другой стороны, этот алгоритм также довольно уверенно себя чувствует и с большими деревьями, если считывать их порциями вида «знаю родителя — прочитать всех наследников». Хороший пример такого случая — динамически подгружаемые деревья. В этом случае алгоритм практически оптимизирован для такого поведения.

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

Использование списка смежных вершин в Doctrine

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

Итак, сущности, которыми мы оперируем в ORM Doctrine — это активные записи (Active Record). Т.е. объекты, которые совмещают в себе бизнес-логику и сами умеют взаимодействовать с базой данных. Но разработчики Doctrine предусмотрели расширение функциональности объектов записей не только наследованием, но и применением к этим объектам «шаблонов поведения». Это реализуется пакетом Doctrine/Template.

Т.о., если возникает необходимость воспитать активную запись до какого-либо поведения (например, Versionable — проводит аудит всех изменений, I18N — многоязычная или NestedSet — древовидная вида «вложенное множество»), то это можно сделать как раз с помощью данных шаблонов поведения.

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

Когда придет время, мы покажем на примерах, как это сделать.

Пока, к сожалению, или к счастью, но в виде шаблона к таблицам метод списка смежных вершин в Doctrine не реализован. При желании вы можете написать реализацию сами и даже предложить ее разработчикам Doctrine, — это уже на ваше усмотрение.

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

Для этого следует сконфигурировать нашу модель должным образом. Используя YAML опишем структуру нашей таблицы:

А вот теперь самое важное — правильно описать связи в таблице. Там же со следующей строчки напишем:

Теперь соберем нашу модель, запустив команду:

Все. Модель готова. Фактически тоже самое можно было сделать в уже готовом базовом классе BaseAlTree:

Теперь пришло время насладиться результатами нашей работы. Напишем несложный код, отображающий дерево, построенное с отступами на обычной HTML-странице, используя рекурсию.

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

Но в тоже время, реализовать динамически подгружаемое дерево таким способом — одно удовольствие!

Вложенное множество (Nested Set)

Описание структуры

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

При построении дерева на основе вложенных множеств, мы воспользуемся принципом обхода этого дерева слева-направо, как показано стрелками на Рис. 5. Для этого определим для каждого узла дерева целочисленные ключи слева (lft) и справа (rgt) (нижние квадратики внутри узла). И раздадим им во время обхода целочисленные инкрементные значения. Посмотрите что получилось.

Рис. 5. Вложенное множество (Nested Set).

Корневой элемент получил ключи 1 и 14, которые включают в себя диапазон чисел всех остальных ключей. Ветка VEGETABLE получила ключи 2 и 7, которые, в свою очередь, включают весь диапазон чисел ключей всех ее наследников и т.д. Вот они — вложенные множества. Все просто, не так ли?

Давайте воссоздадим такую же структуру в контексте таблицы БД.

Рис. 6. Таблица иерархических данных на основе метода вложенных множеств

Или же в виде SQL:

Как видите, мы ввели дополнительно еще одно поле в таблицу — level. В нем будет храниться информация об уровне вложенности каждой ветки дерева. В принципе, это делать вовсе не обязательно — уровень вложенности может быть достаточно просто вычислен, но так как данный алгоритм оптимизирован как раз для чтения, то почему бы не выиграть в производительности за счет кеширования информации об уровне? Риторический вопрос…

Чтение дерева из БД

Читаем все дерево:

Результат будет таким:

Теоретически, тот же результат мы бы могли получить, вычисляя уровень вложенности на лету:

Попробуйте сравнить результат самостоятельно — он будет идентичен первому. Только сам запрос в данном случае более ресурсоемкий. А так как Nested Set — это оптимальный алгоритм чтения, то небольшая оптимизация в виде кеширования уровня вложенности рядом с остальными данными не такая уж и плохая стратегия.

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

Например, если мы хотим извлечь все овощи (VEGETABLE) из нашего примера, это сделать достаточно просто:

Да, быстрое и гибкое чтение, включая агрегацию с внешними связанными данными — конек данного алгоритма.

Тем не менее, не бывает худа без добра, и в данном случае, значительные трудности начинаются когда нам необходимо внести изменения в Nested Set дерево или удалить какую-либо из его ветвей.

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

Добавление новой ветки

Предположим, что мы хотим добавить новую ветку с именем SEA FOOD в наше дерево на одном уровне с VEGETABLES и FRUIT.

Если вы используете в MySQL таблицы MYISAM, или версию, которая не поддерживает транзакции, вы можете вместо BEGIN и COMMIT использовать блокировки на запись:

Как видите, задача на добавление новой ветки достаточно затратная и нетривиальная. Тем не менее, решаемая.

Удаление ветки

Давайте теперь попробуем удалить вновь созданную ветку:

Вывод — Nested Set действительно хорош, когда нам необходимо считывать структуру деревьев из БД. При этом он одинаково хорош для деревьев любого объема.

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

Использование Nested Set в Doctrine

А вот этот метод имеет отражение в Doctrine в виде реализации шаблона поведения, который мы можем привязать к нашей модели.

Сделать это довольно просто, методом конфигурации модели через YAML-конфиг или прамо в коде базового класса.

Как видите, достаточно просто указать actAs: [NestedSet] в описании класса.

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

В этом случае конфигурацию следовало бы записать так:

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

Для первого случая:

Для второго случая (несколько деревьев):

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

Примеры работы с деревьями Nested Set в Doctrine

Извлекаем и печатаем все дерево на экран:

Посмотрите как это просто!

За дополнительными примерами и информацией вы можете обратиться к официальной документации Doctrine, разделы 8.2.4 и 8.2.5

Материализованный путь (Materialized Path)

Описание структуры

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

Рис. 7. Древовидная структура, организованная по принципу «материализованый путь»

Принцип формирования таких путей достаточно прост. Глубина пути — это уровень дерева. Внутри ветки нумерация — инкрементная. Другими словами, VEGETABLE — первый ребенок FOOD, FRUIT — второй ребенок и т.д.

Проще будет взглянуть на это в виде таблицы:

Возможно, так даже более наглядно.

В базе данных все это находит следующее отражение.

Рис. 8. структура таблицы иерархических данных, организованных по принципу «материализованный путь»

В чем же преимущество такого подхода?

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

Поиск пути к узлу:

Вычисление уровня вложенности.

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

Выбор ветки:

Обратите внимание, в данном примере мы воспользовались нашей самописной функцией и это было достаточно удобно.

Поиск родителя:

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

Насколько известно автору, алгоритм довольно уверенно себя чувствует на достаточно больших объемах данных.

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

А вот удаление, добавление в конец или изменение узла — это операции довольно простые, и, как правило, не вызывают сложностей в данной модели.

Как видно из примеров, данный алгоритм также можно несколько оптимизировать на чтение, путем введения ещё одного поля level, как это было сделано для списков смежных вершин (Nested Set). Однако это несколько усложнит операции добавления, изменения и удаления узлов дерева, т.к. уровни придется пересчитывать для всего или части дерева при каждом изменении. В конечном счете, именно разработчику решать, в какую сторону следует делать перекос производительности.

Использование в Doctrine

К сожалению, на данный момент, этот метод хранения деревьев пока не нашел своей реализации в ORM Doctrine (текущая версия на момент написания материала — 1.0.4, 1.1.0 — в альфа версии также реализации не имеет).

Тем не менее есть все предпосылки полагать, что его реализация появится в будущем, т.к. исходные коды библиотеки содержат в пакете Doctrine/Tree абстракный пустой класс с именем MaterializedPath.

Автор будет следить за событиями и обновит эту статью, как только реализация найдет свое отражение, так что можете сюда вернуться позже.

Комбинированный подход

Списки смежности + материализованный путь (Adjacency List + Materialized Path)
Списки смежности + вложенные множества (Adjacency List + Nested Set)

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

Рис. 9. Таблицы моделей иерархических структур данных AL+MP и AL+NS

Последствия такого подхода очевидны.

AL+MP

Улучшаются операции выборки ветвей и поддеревьев целиком
Ухудшаются операции переноса ветвей

Улучшаются операции выборки родителей заданного узла
Улучшаются операции выборки наследников заданного узла

AL+NS

Для связки AL+NS взаимовыгодность не столь очевидна. В первую очередь это объясняется тем, что недостатки от проблем изменения узлов дерева в модели NS напрочь убивают в этой сфере все достоинства AL. Это значит, что такую связку следует рассматривать лишь как качественное улучшение поиска родителей и наследников заданного узла в алгоритме NS, а также как повышение надежности самого алгоритма (ключи можно всегда перестроить в случае порчи — информацию о связях хранит AL). Утверждение о повышении надежности справедливо и для предыдущей комбинации методов. Но ведь и это качественное улучшение, хотя и не такое очевидное, не так ли?

Заключение

В данной статье мы рассмотрели несколько основных методов хранения иерархических данных в реляционных БД и очертили все их достоинства и недостатки. Также мы показали на практике, какие из них доступны для использования в реализации ORM Doctrine, и как их использовать.

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

Учитель информатики Кузнецова Л. Л. МОУ СОШ №10

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

Рассмотрим процесс построения информационной модели, которая позволяет классифицировать современные компьютеры. Класс Компьютеры можно разделить на три подкласса: Суперкомпьютер, Серверы Персональные компьютеры.

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

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

Для описания исторического процесса смены поколений семьи используются динамические информационные модели в форме генеалогического дерева. В качестве примера можно рассмотреть фрагмент (X - XI века) генеалогического дерева династии Рюриковичей.

ТСО: компьютер, мультимедийный проектор.

Ход урока

I. Организационный момент.

Что нас окружает? Множество объектов.
Какие системы объектов целесообразно и возможно представить с помощью табличных моделей?
Что отражают информационные модели?

III. Объяснение нового материала.

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

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

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

Однако некоторые группы объектов имеют одинаковые общие свойства, которые отличают их от объектов других групп.

Группа объектов, обладающих одинаковыми общими свойствами, называется классом объектов. Внутри класса объектов могут быть выделены подклассы, объекты которых обладают некоторыми особенными свойствами, в свою очередь подклассы могут делиться на ещё более мелкие группы и так далее. (Приложение, слайд 3.) Класс Четырёхугольники можно разделить на два подкласса: Параллелограммы и Трапеции. Подкласс Параллелограммы делится, свою очередь, на Прямоугольники и Ромбы, а в Прямоугольниках выделяются ещё Квадраты. Подкласс Трапеции делится на Равнобедренные и Прямоугольные.

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

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

В иерархической структуре элементы распределяются по уровням, от первого (верхнего) уровня до нижнего (последнего) уровня. Рассмотрим на примере объекта “Часы”, в качестве основания классификации возьмём способы функционирования.

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

Рассмотрим процесс построения статической иерархической информационной модели, которая позволяет классифицировать современные компьютеры. (Приложение, слайд 7.)

Класс компьютеры можно разделить на три подкласса: Суперкомпьютеры, Серверы, Персональные компьютеры. Подкласс Персональные компьютеры делится, в свою очередь, на Настольные, Портативные и Карманные.

Удобным способом наглядного представления структуры информационных моделей является граф. (Приложение, слайд 8.)

В случае представления информации о составе и структуре системы в виде графа компоненты системы изображаются вершинами, а связи между ними – линиями (дугами или рёбрами). Графы используются во многих областях практической научной деятельности людей. Следующий пример относится к органической химии. Известно, что свойства химических веществ, называемых углеводородами, зависят не только от того, из какого количества атомов углерода и водорода состоит молекула, но и от способа их соединения, т.е. от структуры молекулы. Возьмём молекулу углеводорода , состоящую из пяти атомов углерода и двенадцати атомов водорода. В зависимости от способа соединения мы получим пентан (Приложение, слайд 9,) или, при другом способе соединения атомов, можно получить 2,2 деметилпропан (Приложение, слайд 10). Принятый в химии способ отображения структуры молекулы фактически является графом.

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

Когда важно знание группы крови?

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

Какую группу крови можно перелить человеку, имеющему III, II, I группы крови?

Что сейчас вы держите в руках?

Правильно, шариковую ручку.

Из чего она состоит?

Её устройство тоже можно представить в виде графа. Школьники изображают устройство шариковой ручки в виде графа, используя средства Microsoft Word, панель рисование.

Полученный граф напоминает ветвящийся куст, который “растёт сверху вниз”. Граф, отражающий состав шариковой ручки, является деревом. Корень этого дерева – вершина “Шариковая ручка”.

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

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

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

Назовите предков Ярослава?

IV. Самостоятельная работа.

Отобразите в виде графа структуру объектов: велосипед, ботинок.

Читайте также: