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

Question

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

То, что вы запрашиваете, - это возможность структурно определить тип как разницу двух других типов (исходное отношение и определение проекции). Я, честно говоря, не могу придумать ни одного языка, который позволил бы вам сделать это. Типы могут быть структурно кумулятивными (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.

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

В качестве бонуса я мог бы использовать API со специальным синтаксисом Scalas.