Реализация реляционной алгебры

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

Данный пост является Literate Haskell файлом и может быть вставлен в редактор. При написании поста использовался компилятор Glasgow Haskell Compiler версии 7.8 и на более ранних версиях код не будет работать, во всяком случае без изменений.

Для начала загрузим немножно расширений:

И используемых модулей.

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

Для дальнейшей работы нам потребуется два типа, тут можно обойтись и одним, но так проще. Для начала, введем тип данных, обозначающий, что поле “вида” а, имеет тип b.

Здесь важно, что :-> является оберткой типа или типом данных, а не синонимом типа, поскольку это позволяет сохранять информацию о “теге” a.

Пример:

*Main> V 5 :: "String" :-> Int
V 5
*Main> :t it
it :: "String" :-> Int

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

Так же введем тип, отвечающий предыдущему на уровне типов

Данное действие совершенно не обязательно, но так удобнее работать.

Теперь все готово для ввода кортежей,

Так мы построили кортеж в виде связного списка, каждый из узлов которого параметризован типом \(b \rightarrow a\), обозначающим, что имени b соответсвует значение типа a. Для такой записи доступ к значению, к сожалению, будет линейным от размера записи, но это когда-нибудь можно будет исправить.

Добавим полезный инстанс:

Пример использования:

 *Main> let t = (HCons "q" (HCons 5 HNil) :: HRec ["Name" :-> String, "Age" :-> Int])
 *Main> t
 HCons (Name :--> "q") (HCons (Age :--> 5) (HNil))
 *Main> :t t
 t :: HRec '["Name" :--> String, "Age" :--> Int]

Для того, чтобы кортежи могли находиться во множествах, введем Eq и Ord инстансы:

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

Тут вполне можно использовать и синоним типа, но это будет хуже, т.к. newtype является ещё и прокси и может служить для передачи информации о типе. Если кто хочет, то может самостоятельно проверить использование синонима типа в данном контексте.

Начнем с простых операций над множествами:

Объедиение, Пересечение, Вычитание

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

Переименование

Переименованием называется унарная операция \(\rho_{a / b}(R)\) результатом которой является множество равное \(R\), за исключением того, что все аттрибуты a в кортежах переименованы в b.

Рассмотрим сначала переименование на типах, т.е. если у нас есть список на уровне типов [s -> a] :: [*] и список переименований [s -> g] :: [*] и если \(s_n = g_n\), то тогда мы переименовываем \(s_n -> a \rightarrow g_n -> a\). Это можно сделать рекурсивно, для каждого из элементов списка \(G\) мы проходим по всем элементам списка a, переименовывая если имена совпадают.

Примеры использования:

 *Main> :kind! Rename ["Foo" :--> Int,"Bar" :--> ()] ["Foo" :--> "Bar", "Bar" :--> "Foo"]
 Rename ["Foo" :--> Int,"Bar" :--> ()] ["Foo" :--> "Bar", "Bar" :--> "Foo"] :: [*]
 = '["Bar" :--> Int, "Foo" :--> ()]

Так же мы можем использовать это при определении записей:

*Main> show (HCons 5 (HCons () HNil) :: HRec (Rename ["Foo" :--> Int,"Bar" :--> ()] ["Foo" :--> "Bar", "Bar" :--> "Foo"]))
"HCons (Bar :--> 5) (HCons (Foo :--> ()) (HNil))"

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

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

Пример:

*Main> rrename t (Proxy :: Proxy '["Foo" :-> "Zoo"])
HCons (Zoo :--> 5) (HCons (Bar :--> ()) (HNil))

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

 *Main> rrename'' t (Proxy :: Proxy '["Foo" :--> "Zoo"])
 HCons (Zoo :-> 5) (HCons (Bar :-> ()) (HNil))

Задание. Проверим, что будет если мы попробуем переименовать несуществующее поле:

 *Main> :kind! Rename ["Foo" :-> Int,"Bar" :-> ()] ["Foo" :--> "E", "Zoo" :--> "Foo"]
 Rename ["Foo" :-> Int,"Bar" :-> ()] ["Foo" :--> "E", "Zoo" :--> "Foo"] :: [*]
 = '["E" :-> Int, "Bar" :-> ()]

Как изменить код таким образом, чтобы такое переименование было запрещено (не выводилось)?

Собственно, теперь можно представить саму реализацию метода:

Проекция

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

Как обычно, начнем с функции, работающей на уровне типов:

Пример:

 *Main> :kind! Project' ["Foo" :-> Int,"Bar" :-> ()] '["Foo"]
 Project' ["Foo" :-> Int,"Bar" :-> ()] '["Foo"] :: [*]
 = '["Foo" :-> Int]

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

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

При помощи вспомогательного класса можно построить саму проекцию.

Пример:

  *Main> rproject t (Proxy :: Proxy '["Bar"])
  HCons (Bar :-> ()) (HNil)

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

Выборка

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

Для этого введем класс предикатов по кортежу:

И предикатов по конкретному типу:

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

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

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

Произведение

Произведением множеств \(R_1=\{a_1,\ldots,a_n\}\) и \(R_2=\{b_1,\ldots,b_n\}\) называется множество \(R_3=\{a_1,\ldots,a_n,b_1,\ldots,b_n\}\) с прямым перебором всех элементов.

Как обычно, сначала пишем функцию работающую на уровне типов:

И затем конструируем классы типов для объединения:

Деление

И напоследок деление, строящееся аналогичным образом:

Заключение

Зачем все это может быть нужно? В данном случае – просто так, для отработки работы с типами и гетерогенными записями. Части похожих задач могут возникать в произвольных местах, в проектах, и хорошо бы иметь представление о работе с ними.

Если код выше можно как-то обобщить или упростить или обсудить какой-то из вопросов отдельно, то буду рад комментариям.