Возможности языка для реализации реляционной алгебры

Я пытался закодировать реляционную алгебру в Scala (которая, насколько мне известно, имеет одну из самых продвинутых систем типов) и, похоже, просто не нашел способ добраться туда, куда я хочу.

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

Итак, какие языковые функции потребуются и какой язык имеет эти функции для реализации статически верифицируемой реляционной алгебры?

Некоторые из требований: Кортеж — это функция, отображающая имена из статически определенного набора допустимых имен для рассматриваемого кортежа в значения типа, указанного именем. Давайте назовем этот набор имен доменом.

Отношение — это множество кортежей с одним и тем же доменом, так что диапазон любого кортежа уникален в множестве.

Пока что модель можно легко смоделировать в Scala, просто

trait Tuple
trait Relation[T<Tuple] extends Set[T]

vals, vars и defs в Tuple — это набор типов имен, определенный выше. Но в Tuple не должно быть двух определений с одинаковым именем. Также vars и нечистые определения, вероятно, тоже должны быть ограничены.

Теперь о сложной части:

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

def join(r1:Relation[T1],r2:Relation[T2]):Relation[T1 with T2]

должен сделать трюк.

Проекция отношения — это отношение, в котором домен кортежей является подмножеством домена кортежей операндов.

def project[T2](r:Relation[T],?1):Relation[T2>:T]

Здесь я не уверен, что вообще возможно найти решение. Что вы думаете? Какие языковые функции необходимы для определения проекта?

Вышеизложенное подразумевает, что API должен быть пригодным для использования. Слои и слои шаблона не приемлемы.


scala orm dsl type-systems database-relations
person John Nilsson    schedule 04.10.2008    source источник

Ответы (5)


arrow_upward
6
arrow_downward

То, о чем вы просите, - это иметь возможность структурно определить тип как разность двух других типов (исходное отношение и определение проекции). Честно говоря, я не могу придумать ни одного языка, который позволил бы вам это сделать. Типы могут быть структурно кумулятивными (A with B), поскольку A with B является структурным подтипом как A, так и B. Однако, если подумать, операция типа A less B на самом деле будет супертипом операции A, а не подтипом. Вы запрашиваете произвольное, контравариантное отношение типизации для естественно ковариантных типов. Не было даже доказано, что такие вещи работают с номинальными экзистенциальными типами, не говоря уже о структурных типах точки объявления.

Я работал над такого рода моделированием раньше, и путь, который я выбрал, состоял в том, чтобы ограничить проекции одной из трех областей: P == T, P == {F} where F in T, P == {$_1} where $_1 anonymous. Во-первых, проекция эквивалентна типу ввода, что означает отсутствие операции (SELECT *). Второй говорит, что проекция — это одно поле, содержащееся в типе ввода. Третий — сложный. Это говорит о том, что вы разрешаете объявление некоторого анонимного типа $_1, который не имеет отношения static к типу ввода. Предположительно, он будет состоять из полей, делегирующих тип ввода, но мы не можем обеспечить это. Это примерно та стратегия, которую использует LINQ.

Извините, я не мог быть более полезным. Я бы хотел, чтобы можно было сделать то, о чем вы просите, это открыло бы много очень изящных возможностей.

person Daniel Spiewak    schedule 04.10.2008
comment
Я хотел бы, чтобы вы предоставили мне несколько ключей для расшифровки того, что вы написали во втором абзаце. - person John Nilsson; 05.10.2008

arrow_upward
2
arrow_downward

Учебник D настолько прост и тесно связан с теорией отношений, на который может быть.

person Andrew not the Saint    schedule 05.10.2008
comment
Tutorial D - мое вдохновение для этого. Но я надеялся не писать новый язык и просто встроить API в какой-нибудь язык GP. Скала в данном случае. - person John Nilsson; 05.10.2008
comment
Тем не менее, написание плагина-копилятора для Scala находится на моем радаре. Даже тогда я бы хотел, чтобы это было более общей функцией, чем просто компилятор Tutorial D. - person John Nilsson; 05.10.2008

arrow_upward
1
arrow_downward

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

person Yardena    schedule 23.10.2008

arrow_upward
1
arrow_downward

Возможно, вы найдете что-то полезное здесь: http://research.microsoft.com/en-us/um/people/simonpj/papers/list-comp/list-comp.pdf

он показывает, как добавить «группировать по» и «упорядочить по» в список включений.

person Community    schedule 18.08.2009

arrow_upward
0
arrow_downward

Я думаю, что остановился на использовании обычных средств для сбора карт для части проекта. Клиенту достаточно указать функцию [T<:Tuple](t:T) => P

С некоторыми трюками с Java, чтобы добраться до класса P, я должен иметь возможность использовать отражение для реализации логики запроса.

Для соединения я, вероятно, буду использовать DynamicProxy для реализации функции сопоставления.

В качестве бонуса я мог бы получить API, который можно было бы использовать со специальным for-syntax Scalas.

person John Nilsson    schedule 07.10.2008