等价关系代数和图灵语言

Question

我正在启动一个项目，我想尝试用类似 java 的编程语言来识别关系代数。

例如，给定两个关系： 美国演员(姓名) EuropianActor(Name)

RA 中的以下表达式：

AmericanActor U EuropianActor

应等效于以下程序：

void RAMethod(Set<Name> AmericanActors, Set<Name> EuropianActors) {
  Set<Name> xs = new Set<Name>();

  for(R r : rs) {
     xs.Add(r);
  }

  for(S s : ss) {
     xs.Add(s);
  }

  return xs;
}

我正在寻找有关此主题的任何出版物。

Answer 1

我个人不知道有任何软件库可以做到这一点。
但是，如果我要做这样的事情，我会编写一个解析器，将关系代数表达式拆分为标记。然后调用您编写的“RAMethod”，以便根据令牌列表中的关系代数运算符在幕后执行关系代数。

Answer 2

你可以这样实现关系代数：

 Set<T> union(Set<T> a, Set<T> b) {
    Set<T> res = new Set<T>();
    for (T i: a) res.Add(i);
    for (T i: b) res.Add(i);
    return res;
 }

 Set<T> projection(Set<Pair<T,U>> a) {
    Set<T> res = new Set<T>();
    for (Pair<T,U> i: a) x.Add(i.first);
    return res;
 }

 Set<T> selection(Set<T> a, Predicate<T> p) {
    Set<T> res = new Set<T>();
    for (T i: a) if (p.Call(i)) x.Add(i);
    return res;
 }

 Set<Pair<T,U>> cross(Set<T> a, Set<U> b) {
    Set<Pair<T,U>> res = new Set<Pair<T,U>>();
    for (T i: a) for (U j: b) x.Add(Pair(i,j));
    return res;
 }

然后直接在代码中编写关系代数：

selection(projection(union(A,B)), isPositive)

基本上“投影”对应“地图”，“选择”对应“过滤器”。

显然并不是每个代码都对应一个关系代数表达式。如果您限制语言没有 while、异常等，您可以将条件转换为选择，将多个嵌套循环转换为叉积，添加到联合等。形式化这是另一个故事。

您可能更喜欢使用更具声明性的语言，例如 Haskell 或 ML；这是使用列表的实现：

type Database a = [a]
select :: (a -> Bool) -> Database a -> Database a
select = filter

projectFirst :: Database (a,b) -> Database a
projectFirst = map fst

projectSecond :: Database (a,b) -> Database b
projectSecond = map snd

union :: Database a -> Database a -> Database a
union = (++)