CODEWITHSUNDEEP
relational-algebraequivalence
KeyboardDrummer
KeyboardDrummer

Reputation: 587

Equivalence relational algebra and turing language

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.

Upvotes: -1

Views: 329

Answers (2)

sdcvvc
sdcvvc

Reputation: 25654

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

Upvotes: 1

Matt Phillips
Matt Phillips

Reputation: 11519

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.

Upvotes: 1

Related Questions