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

Ловушка соединений в теории баз данных

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

Содержание

• Фон работы модели Кодда
• Понимание ловушки соединений
• Пример Поставщик-Детали-Проекты
• Почему важны другие композиции
• Дополнительные примеры ловушки соединений
• Почему пути на основе указателей не работают в реляционных системах
• Как избежать ловушки соединений

Фон работы модели Кодда

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

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

Понимание ловушки соединений

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

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

Пример Поставщик-Детали-Проекты

Рассмотрим классический пример, который Кодд использовал для иллюстрации ловушки соединений:

Рассмотрим три отношения:

1. SUPPLIERS (S#, SNAME, STATUS, CITY) - ПОСТАВЩИКИ
2. PARTS (P#, PNAME, COLOR, WEIGHT, CITY) - ДЕТАЛИ
3. PROJECTS (J#, JNAME, CITY) - ПРОЕКТЫ

И две связи:

1. SUPPLIES (S#, P#, QTY) - какие поставщики поставляют какие детали
2. USES (P#, J#, QTY) - какие проекты используют какие детали

Естественная композиция, которую мы хотим получить: “Какие поставщики поставляют детали для каких проектов?”

В навигационной системе вы могли бы попробовать следовать этому пути:

• Начать с поставщика
• Найти все детали, которые он поставляет
• Для каждой детали найти все проекты, которые ее используют
• Собрать все уникальные проекты

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

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

Правильное реляционное решение было бы таким:

SELECT DISTINCT S.S#, J.J#
FROM SUPPLIERS S, SUPPLIES SP, PARTS P, USES U, PROJECTS J
WHERE S.S# = SP.S# 
  AND SP.P# = P.P# 
  AND P.P# = U.P# 
  AND U.J# = J.J#

Это правильно учитывает все связи без двойного подсчета или следования неправильным путям.

Почему важны другие композиции

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

1. Требования бизнес-логики: Разные бизнес-вопросы требуют разных композиций. Например:

   • “Какие поставщики поставляют детали, используемые в проектах в Лондоне?” (фильтр по городу)
   • “Какие поставщики поставляют более 50 единиц любой детали?” (количественное ограничение)
   • “Какие поставщики поставляют все детали, используемые конкретным проектом?” (универсальная квантификация)

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

   • “Какие поставщики поставляют детали, которые никогда не используются ни одним проектом?” (сиротские данные)
   • “Какие проекты используют детали, которые не предоставляет ни один поставщик?” (несогласованность данных)

3. Оптимизация производительности: Понимание разных композиций помогает в проектировании эффективных индексов и стратегий запросов.

4. Анализ нормализации: Разные композиции могут выявлять функциональные зависимости и помогать выявлять возможности нормализации.

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

Дополнительные примеры ловушки соединений

Вот другие примеры, где ловушка соединений вызывает проблемы:

Пример 1: Сотрудник-Отдел-Проекты

Рассмотрим:

• EMPLOYEES (EID, ENAME, SALARY) - СОТРУДНИКИ
• DEPARTMENTS (DID, DNAME, BUDGET) - ОТДЕЛЫ
• PROJECTS (PID, PNAME, START_DATE) - ПРОЕКТЫ
• WORKS_IN (EID, DID, ROLE) - РАБОТАЕТ_В
• ASSIGNED_TO (EID, PID, HOURS) - НАЗНАЧЕН_НА

Ловушка: Попытка найти “В каких отделах работают сотрудники, участвующие в каких проектах” путем:

• Взятия сотрудника
• Нахождения его отдела
• Нахождения всех проектов, в которых он назначен
• Затем утверждения, что эти отделы работают над этими проектами

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

Правильный подход:

SELECT DISTINCT D.DID, P.PID
FROM DEPARTMENTS D, EMPLOYEES E, WORKS_IN WI, PROJECTS P, ASSIGNED_TO A
WHERE D.DID = WI.DID 
  AND WI.EID = E.EID 
  AND E.EID = A.EID 
  AND A.PID = P.PID

Пример 2: Клиент-Товар-Магазин

Рассмотрим систему электронной коммерции с:

• CUSTOMERS (CID, CNAME, EMAIL) - КЛИЕНТЫ
• PRODUCTS (PID, PNAME, PRICE) - ТОВАРЫ
• STORES (SID, SNAME, LOCATION) - МАГАЗИНЫ
• PURCHASES (CID, PID, QUANTITY, DATE) - ПОКУПКИ
• INVENTORY (SID, PID, STOCK) - ЗАПАСЫ

Ловушка: Нахождение “Какие клиенты покупают товары, доступные в каких магазинах” путем следования:

• Клиент → Товары, которые он купил → Магазины, в которых есть эти товары

Проблема: Клиент мог купить товар, когда он был доступен в Магазине А, но теперь он доступен только в Магазине Б. Временной аспект создает неправильные ассоциации.

Правильный подход:

SELECT DISTINCT C.CID, S.SID
FROM CUSTOMERS C, PRODUCTS P, STORES S, PURCHASES PUR, INVENTORY INV
WHERE C.CID = PUR.CID 
  AND PUR.PID = P.PID 
  AND P.PID = INV.PID 
  AND INV.SID = S.SID

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

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

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

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

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

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

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

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

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

Как избежать ловушки соединений

Чтобы избежать ловушки соединений, проектировщикам баз данных следует:

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

2. Использовать правильные SQL-соединения: Понимать разницу между INNER JOIN, LEFT JOIN, RIGHT JOIN и FULL JOIN и выбирать подходящий для каждого запроса.

3. Использовать реляционную алгебру: Формулировать запросы в терминах выбора, проекции, соединения, объединения, разности и переименования операций.

4. Учитывать бизнес-логику: Всегда спрашивать “Какой бизнес-вопрос мы пытаемся ответить?”, а не “Как мне перейти от А к Б к В?”

5. Тестировать с граничными случаями: Рассматривать сценарии, такие как дублирующиеся пути, NULL-значения и множественные связи между одними и теми же сущностями.

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

Источники

1. Edgar F. Codd - Wikipedia
2. A relational model of data for large shared data banks | Communications of the ACM
3. Codd’s 12 Rules - Liam ERD
4. 50 Years of Codd’s Rules: Transforming Data Management and the Global Economy | Medium
5. Codd’s theorem - Wikipedia
6. The Relational Model, Part 1 - by Joe Reis

Заключение

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

1. Реляционная ≠ Навигационная: Реляционная модель использует операции над множествами, а не физическое следование указателям
2. Естественная композиция против следования по путям: Ответ на вопрос “Какие X связаны с какими Y?” не всегда находится путем следования по всем возможным путям
3. Важна семантика множеств: Устранение дубликатов и правильные условия соединения важны для правильных результатов
4. Сначала бизнес-логика: Всегда начинайте с бизнес-вопроса, затем определяйте соответствующие реляционные операции

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