实现关系代数的语言特性
我一直在尝试用 Scala 编码关系代数（据我所知，Scala 是最先进的类型系统之一），但似乎找不到一种方法来达到我想要的效果。
由于我在编程语言设计的学术领域没有那么丰富的经验，所以我真的不知道要寻找什么功能。
那么，要实现静态验证的关系代数，需要哪些语言功能，以及哪些语言具有这些功能？
一些要求： 元组是一个函数，将名称从相关元组的一组静态定义的有效名称映射到该名称指定的类型的值。 让我们将此名称类型集称为域。
关系是具有相同域的元组集合，使得任何元组的范围在集合中都是唯一的
到目前为止，模型可以在 Scala 中简单地通过以下方式建模
trait Tuple
trait Relation[T<Tuple] extends Set[T]
元组中的 vals、vars 和 defs 是定义的名称类型集多于。 但是 Tuple 中不应该有两个同名的 def。 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 必须可用。 层层样板是不可接受的。
I've been trying to encode a relational algebra in Scala (which to my knowlege has one of the most advanced type systems) and just don't seem to find a way to get where I want.
As I'm not that experienced with the academic field of programming language design I don't really know what feature to look for.
So what language features would be needed, and what language has those features, to implement a statically verified relational algebra?
Some of the requirements:
A Tuple is a function mapping names from a statically defined set of valid names for the tuple in question to values of the type specified by the name. Lets call this name-type set the domain.
A Relation is a Set of Tuples with the same domain such that the range of any tuple is uniqe in the Set
So far the model can eaisly be modeled in Scala simply by
trait Tuple
trait Relation[T<Tuple] extends Set[T]
The vals, vars and defs in Tuple is the name-type set defined above. But there should'n be two defs in Tuple with the same name. Also vars and impure defs should probably be restricted too.
Now for the tricky part:
A join of two relations is a relation where the domain of the tuples is the union of the domains from the operands tuples. Such that only tuples having the same ranges for the intersection of their domains is kept.
def join(r1:Relation[T1],r2:Relation[T2]):Relation[T1 with T2]
should do the trick.
A projection of a Relation is a Relation where the domain of the tuples is a subset of the operands tuples domain.
def project[T2](r:Relation[T],?1):Relation[T2>:T]
This is where I'm not sure if it's even possible to find a sollution. What do you think? What language features are needed to define project?
Implied above offcourse is that the API has to be usable. Layers and layers of boilerplate is not acceptable.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我想我已经决定只使用正常的设施来为项目部分绘制地图集合。 客户端只需指定一个函数
[T<:Tuple](t:T) =>; P通过一些java技巧来获取PI的类应该能够使用反射来实现查询逻辑。
对于连接，我可能会使用 DynamicProxy 来实现映射功能。
作为奖励，我也许能够让 API 与 Scala 特殊的 for 语法一起使用。
I think I have settled on just using the normal facilities for mapping collection for the project part. The client just specify a function
[T<:Tuple](t:T) => PWith some java trickery to get to the class of P I should be able to use reflection to implement the query logic.
For the join I'll probably use DynamicProxy to implement the mapping function.
As a bonus I might be able to get the API to be usable with Scalas special for-syntax.
您所要求的是能够在结构上将类型定义为其他两种类型（原始关系和投影定义）的差异。 老实说，我想不出任何语言可以让你做到这一点。 类型可以在结构上累积（
A with B），因为A with B是A和B< 的结构子类型/代码>。 但是，如果您仔细想想，类型操作A less B实际上是A的超类型，而不是子类型。 您要求在自然协变类型上建立任意的逆变类型关系。 甚至还没有证明这种事情对于名义存在类型来说是合理的，更不用说结构声明点类型了。我以前从事过此类建模，我采取的路线是将投影限制到三个域之一：
P==T，P< /code> =={F}，其中 F in T，P=={$_1}，其中 $_1 匿名。 第一个是投影相当于输入类型，这意味着它是一个无操作 (SELECT *)。 第二个是说投影是输入类型中包含的单个字段。 第三个是棘手的。 这表示您允许声明某种与输入类型没有静态关系的匿名类型$_1。 据推测，它将由委托给输入类型的字段组成，但我们不能强制执行。 这大致就是LINQ采取的策略。抱歉，我无法提供更多帮助。 我希望能够做到你所要求的，这会带来很多非常巧妙的可能性。
What your asking for is to be able to structurally define a type as the difference of two other types (the original relation and the projection definition). I honestly can't think of any language which would allow you to do that. Types can be structurally cumulative (
A with B) sinceA with Bis a structural sub-type of bothAandB. However, if you think about it, a type operationA less Bwould actually be a supertype ofA, rather than a sub-type. You're asking for an arbitrary, contravariant typing relation on naturally covariant types. It hasn't even been proven that sort of thing is sound with nominal existential types, much less structural declaration-point types.I've worked on this sort of modeling before, and the route I took was to constraint projections to one of three domains:
P==T,P=={F} where F in T,P=={$_1} where $_1 anonymous. The first is where the projection is equivalent to the input type, meaning it is a no-op (SELECT *). The second is saying that the projection is a single field contained within the input type. The third is the tricky one. It is saying that you are allowing the declaration of some anonymous type$_1which has no static relationship to the input type. Presumably it will consist of fields which delegate to the input type, but we can't enforce that. This is roughly the strategy that LINQ takes.Sorry I couldn't be more helpful. I wish it were possible to do what you're asking, it would open up a lot of very neat possibilities.