代码之家 › 专栏 › 技术社区 › John Nilsson

实现关系代数的语言特性

database-relations type-systems dsl scala orm

John Nilsson · 技术社区 · 17 年前

我一直在尝试用Scala编码一个关系代数(据我所知,Scala是最先进的类型系统之一),但似乎找不到一种方法来达到我想要的目的。

由于我在编程语言设计的学术领域没有那么丰富的经验,我真的不知道该寻找什么特性。

那么,实现静态验证的关系代数需要哪些语言特性,哪些语言具有这些特性?

一些要求: 元组是一个函数,它将有关元组的一组静态定义的有效名称映射到由名称指定的类型的值。让我们调用此名称类型设置域。

关系是具有相同域的元组的集合,因此任何元组的范围在集合中都是唯一的

到目前为止,该模型在Scala中可以简单地通过

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

元组中的vals、vars和defs是上面定义的名称类型集。但是元组中不应该有两个同名的def。同时,vars和不纯def也应该受到限制。

现在对于棘手的部分:

两个关系的联接是一种关系,其中元组的域是操作数元组的域的并集。这样,只有在域的交集上具有相同范围的元组才被保留。

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

应该会成功的。

关系的投影是一种关系,其中元组的域是操作数元组域的子集。

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

这就是我不确定是否有可能找到解决方法的地方。你怎么认为?定义项目需要哪些语言特性?

当然,上面暗示的是API必须是可用的。一层又一层的样板是不可接受的。

5 回复 | 直到 17 年前

Daniel Spiewak 17 年前

你的要求是能够在结构上定义一个类型为差异其他两种类型(原始关系和投影定义)。我真的想不出任何语言能让你这么做。类型可以在结构上累积( A with B )自从 A和B 是两者的结构子类型 A 和 B . 但是,如果你仔细想想,一个类型操作 A less B 实际上是一个超型属于 一个 ,而不是子类型。您要求在自然协变类型上有任意的、反变的类型关系。它甚至没有被证明是有意义的存在类型的声音,更不用说结构声明点类型。

我以前做过这种建模,我采取的方法是将投影约束到三个域中的一个: P == T , 第页 == {F} where F in T , 第页 == {$_1} where $_1 anonymous . 第一个是投影与输入类型等价的地方,这意味着它是一个no-op( SELECT * ). 第二种说法是投影是包含在输入类型中的单个字段。第三个是棘手的问题。它是说您允许声明某种匿名类型 $_1 它没有 静止的 与输入类型的关系。可能它将由委托给输入类型的字段组成,但我们不能强制执行。这大概就是LINQ采取的策略。

对不起,我帮不了你。我希望能按你的要求去做,这会带来很多非常好的可能性。

Andrew not the Saint 17 年前

Tutorial D 与语言的关系理论一样简单和紧密。

Yardena 17 年前

HaskellDB 对如何创建类型安全的关系代数DSL有一些想法,您可能会发现它很有用。

AivarAivar 17 年前

也许你觉得smth在这里很有用: http://research.microsoft.com/en-us/um/people/simonpj/papers/list-comp/list-comp.pdf

它展示了如何添加“group by”和“orderby”来列出理解。

John Nilsson 17 年前

我想我已经决定使用常规的工具来为项目部分绘制集合。客户端只是指定一个函数 [T<:Tuple](t:T) => P

使用一些java技巧来获得P类,我应该能够使用反射来实现查询逻辑。

对于join,我可能会使用DynamicProxy来实现映射函数。

作为一个额外的好处,我可能可以让API与Scalas一起使用,特别是语法。