Иерархические структуры данных и Doctrine / Хабр

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

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

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

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

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

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

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

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

CREATE TABLE ns_tree (
    `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    `name` VARCHAR(50) NOT NULL,
    `lft` BIGINT NOT NULL,
    `rgt` BIGINT NOT NULL,
    `level` BIGINT NOT NULL
) TYPE=InnoDB DEFAULT CHARSET=utf8;

CREATE INDEX nslrl_idx ON ns_tree (lft, rgt, level);

INSERT INTO ns_tree VALUES
    (1, 'FOOD', 1, 14, 0),
    (2, 'VEGETABLE', 2, 7, 1),
    (3, 'POTATO', 3, 4, 2),
    (4, 'TOMATO', 5, 6, 2),
    (5, 'FRUIT', 8, 13, 1),
    (6, 'APPLE', 9, 10, 2),
    (7, 'BANANA', 11, 12, 2);

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

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

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

SELECT node.id, node.name, node.level
FROM ns_tree AS node,
ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND parent.id = 1
ORDER BY node.lft;

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

 ---- ----------- ------- 
| id | name      | level |
 ---- ----------- ------- 
|  1 | FOOD      |     0 |
|  2 | VEGETABLE |     1 |
|  3 | POTATO    |     2 |
|  4 | TOMATO    |     2 |
|  5 | FRUIT     |     1 |
|  6 | APPLE     |     2 |
|  7 | BANANA    |     2 |
 ---- ----------- ------- 

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

SELECT node.id, node.name, (COUNT(parent.id) - 1) AS level
FROM ns_tree AS node,
ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

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

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

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

SELECT node.id, node.name, node.level
FROM ns_tree AS node, ns_tree AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt AND parent.id = 2
ORDER BY node.lft;

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

или другим способом — пусть это будет творческой задачей для читателя.

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

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

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

Смотрите сами.

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

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

BEGIN;

SELECT @treeRight := rgt FROM ns_tree
WHERE id = 2; /* справа от ветки VEGETABLES, у которой id = 2 */

UPDATE ns_tree SET rgt = rgt   2 WHERE rgt > @treeRight;
UPDATE ns_tree SET lft = lft   2 WHERE lft > @treeRight;

INSERT INTO ns_tree VALUES(0, 'SEA FOOD', @treeRight   1, @treeRight   2, 1);

COMMIT;

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

LOCK TABLE ns_tree WRITE;
...
UNLOCK TABLES;

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

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

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

BEGIN;

SELECT @treeLeft := lft, @treeRight := rgt, @treeWidth := rgt - lft   1
FROM ns_tree
WHERE id = 8; /* здесь идентификатор новой записи с именем 'SEA FOOD' */

DELETE FROM ns_tree WHERE lft BETWEEN @treeLeft AND @treeRight;
/*
  ВНИМАНИЕ!
  Обратите внимание - мы не удаляем по id,
  Хотя в данном случае это бы нас устроило.
  Но в общем случае нам необходимо удалить всю ветку с ее содержимым!
*/

UPDATE ns_tree SET rgt = rgt - @treeWidth WHERE rgt > @treeRight;
UPDATE ns_tree SET lft = lft - @treeWidth WHERE lft > @treeRight;

COMMIT;

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

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

Amazon: simpledb

— это атрибутно-ориентированное хранилище типа ключ-значение, входящее в состав Amazon WebServices. SimpleDB находится в стадии бета-версии; пользователи могут пользовать ей бесплатно — до тех пор пока их потребности не превысят определенный предел.

image

У SimpleDB есть несколько ограничений. Первое — время выполнения запроса ограничено 5-ю секундами. Второе — нет никаких типов данных, кроме строк. Все хранится, извлекается и сравнивается как строка, поэтому для того, чтобы сравнить даты, вам нужно будет преобразовать их в формат ISO8601.

Третье — максимальные размер любой строки составляет 1024 байта, что ограничивает размер текста (например, описание товара), который вы можете хранить в качестве атрибута. Однако поскольку структура данных гибкая, вы можете обойти это ограничения, добавляя атрибуты «ОписаниеТовара1», «Описание товара2» и т.д.

Одной из ключевых особенностей SimpleDB является использование модели конечной констистенции (eventual consistency model). Эта модель подходит для многопоточной работы, однако следует иметь в виду, что после того, как вы изменили значение атрибута в какой-то записи, при последующих операциях чтения эти изменения могут быть не видны.

Использование nested set в doctrine

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

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

YAML:

NsTree:
  tableName: ns_tree
  actAs: [NestedSet]
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    name:
      type: string(50)
      notnull: true
    lft:
      type: integer(8)
      notnull: true
    rgt:
      type: integer(8)
      notnull: true
    level:
      type: integer(8)
      notnull: true

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

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

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

NsTree:
  tableName: ns_tree
  actAs: 
    NestedSet:
      hasManyRoots: true
      rootColumnName: root_id
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    root_id:
      type: integer(8)
      notnull: true
    name:
      type: string(50)
      notnull: true
    lft:
      type: integer(8)
      notnull: true
    rgt:
      type: integer(8)
      notnull: true
    level:
      type: integer(8)
      notnull: true

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

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

или:

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

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

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

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

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

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

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

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

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

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

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

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

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

AlTree:
  tableName: al_tree
  columns:
    id:
      type: integer(8)
      primary: true
      autoincrement: true
    name:
      type: string(50)
      notnull: true
    parent_id: integer(8)

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

  relations:
    Parent:
      class: AlTree
      local: parent_id
      foreign: id
      type: one
    Children:
      class: AlTree
      local: id
      foreign: parent_id
      type: many

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

./doctrine generate-models-yaml

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

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

Никаких join’ов

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

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

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

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

Доступ к данным

Реляционная БДХранилище типа ключ-значение
Данные создаются, обновляются, удаляются и запрашиваются с использованием языка структурированных запросов (SQL).Данные создаются, обновляются, удаляются и запрашиваются с использованием вызова API методов.
SQL-запросы могут извлекать данные как из одиночной таблица, так и из нескольких таблиц, используя при этом соединения (join’ы).Некоторые реализации предоставляют SQL-подобный синтаксис для задания условий фильтрации.
SQL-запросы могут включать агрегации и сложные фильтры.Зачастую можно использовать только базовые операторы сравнений (=, !=, <, >, <= и =>).
Реляционная БД обычно содержит встроенную логику, такую как триггеры, хранимые процедуры и функции.Вся бизнес-логика и логика для поддержки целостности данных содержится в коде приложений.

Взаимодействие с приложениями

Новая волна


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

(хотя они также могут быть реляционными), шардированных упорядоченных массивов (sharded sorted arrays),

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

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

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

Характеристики хранилищ

Реляционная БДХранилище типа ключ-значение
База данных состоит из таблиц, таблицы содержат колонки и строки, а строки состоят из значений колонок. Все строки одной таблицы имеют единую структуру.Для доменов можно провести аналогию с таблицами, однако в отличие от таблиц для доменов не определяется структура данных. Домен – это такая коробка, в которую вы можете складывать все что угодно. Записи внутри одного домена могут иметь разную структуру.
Модель данных1 определена заранее. Является строго типизированной, содержит ограничения и отношения для обеспечения целостности данных.Записи идентифицируются по ключу, при этом каждая запись имеет динамический набор атрибутов, связанных с ней.
Модель данных основана на естественном представлении содержащихся данных, а не на функциональности приложения.В некоторых реализация атрибуты могут быть только строковыми. В других реализациях атрибуты имеют простые типы данных, которые отражают типы, использующиеся в программировании: целые числа, массива строк и списки.
Модель данных подвергается нормализации, чтобы избежать дублирования данных. Нормализация порождает отношения между таблицами. Отношения связывают данные разных таблиц.Между доменами, также как и внутри одного домена, отношения явно не определены.

Проблемы реляционных бд

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

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

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

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

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

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

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

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

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

Для начала, определим, что важно для сотрудников из компании, которые ищут кандидатов:

  1. для HR:

    1.1) компании, где работал соискатель
    1.2) позиции, которые ранее занимал соискатель в данных компаниях
    1.3) навыки и умения, которыми соискатель пользовался в работе;
    а также продолжительность работы соискателя в каждой компании на каждой позиции и длительность использования каждого навыка и умения

  2. для технического специалиста:

    2.1) позиции, которые занимал соискатель в данных компаниях
    2.2) навыки и умения, которыми соискатель пользовался в работе
    2.3) проекты, в которых участвовал соискатель;
    а также продолжительность работы соискателя на каждой позиции и в каждом проекте, длительность использования каждого навыка и умения

Для начала выявим нужные сущности:

  1. Сотрудник (Employee)
  2. Компания (Company)
  3. Позиция (должность) (Position)
  4. Проект (Project)
  5. Навык (Skill)


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

Иерархические структуры данных и Doctrine / Хабр
Рис.11. Схема базы данных для поиска соискателей на работу

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

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

Когда вы понимаете отношения между субъектами и между субъектами и объектами — уже упомянутые семь формальных правил — эту или схожую схему можно реализовать «на коленке»: на листке бумаги, мене чем за час. И это еще с учетом усталости после плодотворного рабочего дня.

Здесь можно было упростить схему добавления данных, если «навыки» вложить в сущность «проекты» через неполно структурированные данные (NoSQL) в виде XML, JSON или просто перечислять названия навыков через точку с запятой. Но это бы усложнило выборку с группировкой по навыкам и фильтрацию по отдельным навыкам.

Подобная модель лежит в основе базы данных проекта Geecko.

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

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

Руководство по разработке структуры и проектированию базы данных

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

Надлежащим образом структурированная база данных:

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

Основные этапы разработки базы данных:

  1. Анализ требований или определение цели базы данных;
  2. Организация данных в таблицах;
  3. Указание первичных ключей и анализ связей;
  4. Нормализация таблиц.

Рассмотрим каждый этап проектирования баз данных подробнее. Обратите внимание, что в этом руководстве рассматривается реляционная модель базы данных Эдгара Кодда, написанная на языке SQL (а не иерархическая, сетевая или объектная модели).

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

Вот несколько способов сбора информации перед созданием базы данных:

Начните со сбора существующих данных, которые будут включены в базу. Затем определите типы данных, которые нужно сохранить. А также объекты, которые описывают эти данные. Например:

Клиенты

  • Имя;
  • Адрес;
  • Город, штат, почтовый индекс;
  • Адрес электронной почты.

Товары

  • Название;
  • Цена;
  • Количество в наличии;
  • Количество под заказ.

Заказы

  • Номер заказа;
  • Торговый представитель;
  • Дата;
  • Товар;
  • Количество;
  • Цена;
  • Стоимость.

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

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

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

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

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

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

Некоторые СУБД также предлагают тип данных Autonumber, который автоматически генерирует уникальный номер в каждой строке.

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

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

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

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

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

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

Каждый объект может быть взаимосвязан с другим с помощью одного из трех типов связи:

Когда существует только один экземпляр объекта A для каждого экземпляра объекта B, говорят, что между ними существует связь “один-к одному” (часто обозначается 1:1). Можно указать этот тип связи в ER-диаграмме линией с тире на каждом конце:

Если при проектировании и разработке баз данных у вас нет оснований разделять эти данные, связь 1:1 обычно указывает на то, что в лучше объединить эти таблицы в одну.

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

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

Эта связи возникают, когда запись в одной таблице связана с несколькими записями в другой. Например, один клиент мог разместить много заказов, или у читателя может быть сразу несколько книг, взятых в библиотеке. Связи «один- ко-многим» (1:M) обозначаются так называемой «меткой ноги вороны», как в этом примере:

Чтобы реализовать связь 1:M, добавьте первичный ключ из «одной» таблицы в качестве атрибута в другую таблицу. Если первичный ключ таким образом указан в другой таблице, он называется внешним ключом. Таблица со стороны связи «1» представляет собой родительскую таблицу для дочерней таблицы на другой стороне.

Когда несколько объектов таблицы могут быть связаны с несколькими объектами другой. Говорят, что они имеют связь «многие-ко-многим» (M:N). Например, в случае студентов и курсов, поскольку студент может посещать много курсов, и каждый курс могут посещать много студентов.

На ER-диаграмме эти связи отображаются с помощью следующих строк:

При проектировании структуры базы данных реализовать такого рода связи невозможно. Вместо этого нужно разбить их на две связи «один-ко-многим».

Для этого нужно создать между этими двумя таблицами новую сущность. Если между продажами и продуктами существует связь M:N, можно назвать этот новый объект «sold_products», так как он будет содержать данные для каждой продажи. И таблица продаж, и таблица товаров будут иметь связь 1:M с sold_products. Этот вид промежуточного объекта в различных моделях называется таблицей ссылок, ассоциативным объектом или таблицей связей.

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

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

Два объекта могут быть взаимозависимыми (один не может существовать без другого).

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

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

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

В то же время не все базы данных необходимо нормализовать. В целом, базы с обработкой транзакций в реальном времени (OLTP), должны быть нормализованы.

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

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

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

Вместо этого во время физического проектирования базы данных разделите данные на несколько таблиц или записей, пока каждая ячейка не будет содержать только одно значение, и дополнительных столбцов не будет. Такие данные считаются разбитыми до наименьшего полезного размера. В приведенной выше таблице можно создать дополнительную таблицу «Реквизиты продаж», которая будет соответствовать конкретным продуктам с продажами. «Продажи» будут иметь связь 1:M с «Реквизитами продаж».

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

Например, атрибут «возраст» зависит от «дня рождения», который, в свою очередь, зависит от «ID студента», имеет частичную функциональную зависимость. Таблица, содержащая эти атрибуты, не будет соответствовать второй форме нормализации.

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

Таким образом, таблица с этими полями не будет соответствовать второй форме нормализации, поскольку атрибут «название товара» зависит от идентификатора продукта, но не от номера заказа:

Третья форма нормализации (3NF): каждый не ключевой столбец должен быть независим от любого другого столбца. Если при проектировании реляционной базы данных изменение значения в одном не ключевом столбце вызывает изменение другого значения, эта таблица не соответствует третьей форме нормализации.

В соответствии с 3NF, нельзя хранить в таблице любые производные данные, такие как столбец «Налог», который в приведенном ниже примере, напрямую зависит от общей стоимости заказа:

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

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

Также с помощью средств проектирования баз данных необходимо настроить БД с учетом возможности проверки данных на соответствие определенным правилам. Многие СУБД, такие как Microsoft Access, автоматически применяют некоторые из этих правил.

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

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

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

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

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

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

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

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

Сейчас UML используется не так часто. В наши дни он применяется академически и в общении между разработчиками программного обеспечения и их клиентами.

Проектируемая структура базы данных зависит от того, какую СУБД вы используете. Некоторые из наиболее распространенных:

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

Пожалуйста, опубликуйте ваши мнения по текущей теме материала. За комментарии, отклики, лайки, подписки, дизлайки низкий вам поклон!

Гибкие материалы:  Мягкие окна в Москве и Московской области | гибкие шторы из ПВХ

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *