Статьи

Математика и SQL, часть 1: Введение — отношения и функции

Июнь 3, 2018

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

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

I: SQL как реляционная математическая реализация

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

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

Примеры кода, объясняющие способы выполнения различных операций, будут предоставлены в Perl. Обратите внимание, что это в основном довольно наивные версии. Если бы кто-то действительно создавал СУБД в Perl, код, вероятно, был бы совсем другим.

II: Реляционная математика, отношения и функции

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

отношение — это набор взаимосвязанных фактов .

Например, давайте рассмотрим два отношения: одно показывает квадратные корни, а другое — квадраты:

  • Для квадратных корней:
    • 1: 1
    • 1: -1
    • 4: 2
    • 4: -2
    • 9: 3
    • 9: -3
  • Для квадратов
    • -3: 9
    • -2: 4
    • -1: 1
    • 0: 0
    • 1: 1
    • 2: 4
    • 3: 9

Оба эти отношения. Они предоставляют список фактов, которые коррелируют. Корень квадратный из 1 — 1. Другой квадратный корень — -1. -1 в квадрате равно 1, и так далее.

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

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

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

Ниже приведены математические функции:
  1. f (x) = x + 1
  2. f (x) = 2 * x
  3. f (x) = x 2

Это функции, потому что
для любого данного x существует ровно один f (x).

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

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

Итак, давайте рассмотрим один пример того, как это работает в Perl. Мы будем использовать хеш-таблицу, которая в основном является хранилищем ключей / значений. Хеш-таблица — это неупорядоченное отношение в Perl, так что значение является функцией ключа. В этом примере мы отметим это, чтобы быть немного более прозрачным математически, хотя в производстве.
 package KeyValueStore;
my %store;
sub set {
    my ($key, $value) = @_;
    $store{$key} = $value;
}
sub remove {
    my $key = shift;
    delete $store{$key};
}
sub get {
    my $key = shift;
    $store{$key};
}
package main;
use KeyValueStore;
KeyValueStore::set('foo', 'bar');
KeyValueStore::set('1', '2');
print KeyValueStore::get('foo');
1;

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

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

41
Share: