Equivalence relational algebra and turing langauge

Question

Hi,

I'm starting a project where I want to try to recognize relational algebra's in java-like programming language.

For example, given two relations: AmericanActor(Name) EuropianActor(Name)

The following expression in RA:

AmericanActor U EuropianActor

should be equivalent to the following program:

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;
}

I'm looking for any publications about this topic. Anything in the right direction is helpfull.

Answer 1

I don't know personally any software libraries that do this. But if I was going to do something like this, I would write a parser that splits up your relational algebra expressions into tokens. Then call your "RAMethod" that you wrote in order to do the relational algebra behind the scenes based on which relational algebra operators are in the token list.

Answer 2

You can implement relational algebra like this:

 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;
 }

and then directly write relational algebra in code:

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

basically "projection" corresponds to "map" and "selection" to "filter".

Obviously not every code corresponds to a relational algebra expression. If you constrain to language without while, exceptions etc. you could translate conditionals to selection, multiple nested loops to cross product, adding to union etc. Formalising that is another story.

You might be more comfortable with a more declarative language, like Haskell or ML; here's an implementation using lists:

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 = (++)