等价关系代数和图灵语言

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

我个人不知道执行此操作的任何软件库。但是，如果I要做这样的事情，我将编写一个解析器，将您的关系代数表达式拆分为标记。然后调用您编写的“ 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 = (++)