Статьи

Математика и SQL: Часть 4. Основные типы данных — наборы, кортежи и пакеты


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

Я отношения и установить

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

Набор — это неупорядоченный список уникальных предметов.  Таким образом, {a, b} является множеством, а {a, b, b} — нет (однако это множественный набор или сумка, см. Ниже). Кроме того, поскольку он неупорядочен, {a, b} = {b, a}. Мы можем спроектировать порядок в списке для нашего удобства, но это не влияет на основную математику. Наборы могут быть конечными или бесконечными. В базах данных мы фокусируемся на конечных наборах (бесконечные наборы могут быть вычислены, но не могут быть сохранены в виде набора в конечной файловой системе). Бесконечные множества предназначены для математических библиотек и здесь нас не особо волнуют.

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

Рассмотрим точку в формате (x, y). Для любой данной точки x и y являются ее тривиальными функциями. Для (2, 2) x = 2 тривиально верно, как и y = 2. Это кажется тавтологическим (и на одном уровне это так), но это также важно, потому что оно касается основной операции реляционной базы данных. Подробнее об этом смотрите в части 2 этой серии .

II ряд и кортеж

Кортеж — это упорядоченный набор предметов. В отличие от набора порядок важен, и повторение разрешено. (1, 2, 3), (1, 3, 3) и (1, 1, 1) являются допустимыми кортежами. В кортежах порядок приписывает значение значению. Например, если предыдущие кортежи ссылались на точки в трехмерном евклидовом пространстве, первый соответствовал бы оси x, второй — расстоянию вдоль оси y, а последний — расстоянию вдоль оси z. Это означает, что точки (1, 2, 3) и (2, 1, 3) различны и не равны (если бы они были множествами с одинаковыми членами, они были бы равны).

В то время как отношения являются открытыми множествами (которые, по-видимому, могут быть добавлены до бесконечности), кортежи являются закрытыми. Хотя можно добавить больше членов, это включает в себя семантический сдвиг в данных. Например, точки (1, 2) и (1, 2, 3) имеют одинаковую ось x и y, но двумерное пространство семантически отличается от трехмерного пространства.

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

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

III Кортежи, множества и отношения в Perl

Кортежи и наборы, конечно, обычно полезны в программировании. Понимание этого часто является ключом к повышению производительности, а в Perl это несколько нелогично.

Наивным взглядом на просмотр базы данных было бы видеть кортеж как% хеш, а набор как @array. На самом деле все наоборот. Понимание этого полезно, потому что, если вы действительно хотите набор, хеш часто является лучшим инструментом, чем массив в Perl.

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

Предположим, мы хотим определить, какие члены одной последовательности не найдены в определенном наборе (в настоящее время представлен в массиве). Мы могли бы сделать что-то вроде:

my %sethash;
$sethash{$_} = 1 for @setarray;
my @excluded = grep {not exists $sethash{$_}} @sequencearray;

Это будет работать намного лучше, чем:

my @excluded;
for my $element (@sequencearray){
    push @excluded, $element unless grep {$_ eq $element} @sequencearray;
}

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

IV набор и сумка

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

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

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

VA Примечание о заказе

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

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

SELECT f.foo, b.bar
  FROM (select foo, id from foobar order by transdate desc limit 20) f
  JOIN barbaz b ON f.id = b.foo_id;

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