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

Question

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

select 1,a,b, from T 

уже возникает целый ряд вопросов:

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

Я считаю, что даже язык PL/SQL Oracle не дает этого совершенно правильно. В то время как проекции invald в большинстве случаев обнаруживаются во время компиляции, это большое количество ошибок типа, которые отображаются только во время выполнения. Большинство других привязок к РСУБД (например, Java jdbc и perl DBI) используют 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 s, что мы могли бы определить бы:

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 s в одном 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 просто отлично, без каких-либо причудливых системных расширений.