Почему безопасные по типу реляционные операции так сложны?

Question

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

select 1,a,b, from T

Уже возникает ряд вопросов:

• какой тип этой функции?
• какой тип проекции 1,a,b? Какой тип проекции в целом?
• Что такое тип результата и как мне выразить связь между типом результата и проекцией?
• какой тип такой функции, которая принимает любую действительную проекцию?
• Как я могу обнаружить неверные прогнозы во время компиляции?
• Как добавить столбец в таблицу или в проекцию?

Я считаю, что даже язык Oracle PL/SQL не совсем правильно понимает это. В то время как неверные проекции в основном обнаруживаются во время компиляции, существует большое количество ошибок типов, которые отображаются только во время выполнения. Большинство других привязок к СУБД (например, jdbc Java и DBI perl) используют SQL, содержащийся в Strings, и, таким образом, полностью отказываются от безопасности типов.

Дальнейшие исследования показали, что есть несколько библиотек на Haskell ( HList, vinyl и TRex), которые предоставляют расширяемые записи с сохранением типов и некоторые другие. Но для всех этих библиотек требуются расширения Haskell, такие как DataKinds, FlexibleContexts и многие другие. Кроме того, эти библиотеки не просты в использовании и пахнут обманом, по крайней мере для таких неинициализированных наблюдателей, как я.

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

Мои вопросы следующие:

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

Answer 1

Давайте определим таблицу, индексированную по некоторым столбцам, как тип с двумя параметрами типа:

data IndexedTable k v = ???

groupBy :: (v -> k) -> IndexedTable k v

-- A table without an index just has an empty key
type Table = IndexedTable ()

k будет (возможно, вложенным) кортежем всех столбцов, по которым таблица проиндексирована. v будет (возможно, вложенным) кортежем всех столбцов, по которым таблица не проиндексирована.

Так, например, если бы у нас была следующая таблица

| Id | First Name | Last Name |
|----|------------|-----------|
|  0 | Gabriel    | Gonzalez  |
|  1 | Oscar      | Boykin    |
|  2 | Edgar      | Codd      |

... и он был проиндексирован в первом столбце, тогда тип будет:

type Id = Int
type FirstName = String
type LastName = String

IndexedTable Int (FirstName, LastName)

Однако, если он был проиндексирован в первом и втором столбце, тип будет следующим:

IndexedTable (Int, Firstname) LastName

Table будет реализовывать Functor, Applicative, а также Alternative Типы классов. Другими словами:

instance Functor (IndexedTable k)

instance Applicative (IndexedTable k)

instance Alternative (IndexedTable k)

Таким образом, соединения будут реализованы как:

join :: IndexedTable k v1 -> IndexedTable k v2 -> IndexedTable k (v1, v2)
join t1 t2 = liftA2 (,) t1 t2

leftJoin :: IndexedTable k v1 -> IndexedTable k v2 -> IndexedTable k (v1, Maybe v2)
leftJoin t1 t2 = liftA2 (,) t1 (optional t2)

rightJoin :: IndexedTable k v1 -> IndexedTable k v2 -> IndexedTable k (Maybe v1, v2)
rightJoin t1 t2 = liftA2 (,) (optional t1) t2

Тогда у вас будет отдельный тип, который мы будем называть Select, Этот тип также будет иметь два параметра типа:

data Select v r = ???

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

selectIndexed :: Indexed k v -> Select v r -> r

Пример SelectТо, что мы могли бы определить, будет:

count   :: Select v Integer
sum     :: Num a => Select a a
product :: Num a => Select a a
max     :: Ord a => Select a a

это Select Тип будет реализовывать Applicative интерфейс, чтобы мы могли объединить несколько Selectв один Select, Например:

liftA2 (,) count sum :: Select Integer (Integer, Integer)

Это было бы аналогично этому SQL:

SELECT COUNT(*), SUM(*)

Однако часто в нашей таблице будет несколько столбцов, поэтому нам нужен способ Select на один столбец. Давайте назовем эту функцию Focus:

focus :: Lens' a b -> Select b r -> Select a r

Так что мы можем написать такие вещи, как:

liftA3 (,,) (focus _1 sum) (focus _2 product) (focus _3 max)
  :: (Num a, Num b, Ord c)
  => Select (a, b, c) (a, b, c)

Так что, если мы хотим написать что-то вроде:

SELECT COUNT(*), MAX(firstName) FROM t

Это было бы эквивалентно следующему коду на Haskell:

firstName :: Lens' Row String

table :: Table Row

select table (liftA2 (,) count (focus firstName max)) :: (Integer, String)

Так что вы можете задаться вопросом, как можно реализовать Select а также Table,

Я опишу как реализовать Table в этом посте:

http://www.haskellforall.com/2014/12/a-very-general-api-for-relational-joins.html

... и вы можете реализовать Select как раз:

type Select = Control.Foldl.Fold

type focus = Control.Foldl.pretraverse

-- Assuming you define a `Foldable` instance for `IndexedTable`
select t s = Control.Foldl.fold s t

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

Как насчет выбора столбцов из таблицы? Ну, вы можете определить:

column :: Select a (Table a)
column = Control.Foldl.list

Итак, если вы хотите сделать:

SELECT col FROM t

... вы бы написали:

field :: Lens' Row Field

table :: Table Row

select (focus field column) table :: [Field]

Важным выводом является то, что вы можете реализовать реляционный API в Haskell просто отлично, без каких-либо необычных системных расширений.