Возможности языка для реализации реляционной алгебры
Я пытался закодировать реляционную алгебру в Scala (которая, насколько мне известно, имеет одну из самых продвинутых систем типов), и, похоже, просто не нашел способа добраться туда, где я хочу.
Поскольку у меня нет большого опыта в академической области дизайна языков программирования, я действительно не знаю, какую функцию искать.
Итак, какие языковые функции потребуются и какой язык имеет эти функции для реализации статически проверенной реляционной алгебры?
Некоторые требования: Кортеж - это функция, отображающая имена из статически определенного набора допустимых имен для рассматриваемого кортежа в значения типа, указанного в имени. Назовем этот набор имен-типов доменом.
Отношение - это набор кортежей с одним и тем же доменом, так что диапазон любого кортежа является уникальным в наборе.
Пока что модель может быть легко смоделирована на Scala, просто
trait Tuple
trait Relation[T<Tuple] extends Set[T]
Vals, vars и defs в Tuple - это набор типов имени, определенный выше. Но в Tuple не должно быть двух defs с одинаковым именем. Также, вероятно, следует ограничить vars и нечистые defs.
А теперь самое сложное:
Соединение двух отношений - это отношение, в котором область значений кортежей представляет собой объединение областей из кортежей операндов. Таким образом, сохраняются только кортежи, имеющие одинаковые диапазоны для пересечения их доменов.
def join(r1:Relation[T1],r2:Relation[T2]):Relation[T1 with T2]
должен сделать свое дело.
Проекция Отношения - это Отношение, в котором домен кортежей является подмножеством домена кортежей операндов.
def project[T2](r:Relation[T],?1):Relation[T2>:T]
Вот где я не уверен, можно ли вообще найти решение. Что вы думаете? Какие языковые особенности необходимы для определения проекта?
Выше подразумевается, что API должен быть пригодным для использования. Слои и слои шаблона недопустимы.
Ответы 5
Вы просите иметь возможность структурно определить тип как разница двух других типов (исходное отношение и определение проекции). Честно говоря, я не могу придумать ни одного языка, который позволил бы вам это сделать. Типы могут быть структурно кумулятивными (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, который не имеет отношения статический к типу ввода. Предположительно, он будет состоять из полей, которые делегируют типу ввода, но мы не можем этого добиться. Это примерно стратегия, которую использует LINQ.
Извини, я ничем не мог помочь. Хотелось бы, чтобы можно было делать то, о чем вы просите, это открыло бы много очень интересных возможностей.
Учебник D примерно такой же простой и тесно связанный с теорией отношений, какой только может быть язык.
Учебник D - мое вдохновение для этого. Но я надеялся избежать написания нового языка и просто встроить API в какой-нибудь язык GP. Scala в данном случае.
Тем не менее, написание плагина компилятора для Scala находится на моем радаре. Даже в этом случае я бы хотел, чтобы это было более общей функцией, чем просто компилятор Tutorial D.
Думаю, я остановился на использовании обычных средств для сбора карт для части проекта. Клиент просто указывает функцию [T<:Tuple](t:T) => P
С помощью некоторых уловок java для перехода к классу P я смогу использовать отражение для реализации логики запроса.
Для соединения я, вероятно, использую DynamicProxy для реализации функции сопоставления.
В качестве бонуса я мог бы получить возможность использовать API со специальным синтаксисом for Scalas.
У HaskellDB есть некоторые идеи, как создать типобезопасный DSL реляционной алгебры, вы можете найти его полезным.
Может быть, отсюда вы найдете что-то полезным: http://research.microsoft.com/en-us/um/people/simonpj/papers/list-comp/list-comp.pdf
он показывает, как добавить «группировать по» и «по порядку» для перечисления пониманий.
Я хотел бы, чтобы вы предоставили мне несколько ключей, чтобы расшифровать то, что вы написали во втором абзаце ..