Реляционная алгебра эквивалентности и язык Тьюринга

Question

Я начинаю проект, в котором я хочу попытаться распознать реляционную алгебру в Java-подобном языке программирования.

Например, даны два отношения: AmericanActor (Имя) EuropianActor (Имя)

Следующее выражение в 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

Вы можете реализовать реляционную алгебру так:

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

Answer 2

Лично я не знаю никаких программных библиотек, которые делают это.Но если бы I собирался сделать что-то подобное, я бы написал парсер, который разбивает ваши выражения реляционной алгебры на токены.Затем назовите ваш «RAMethod», который вы написали, чтобы создать реляционную алгебру за кулисами, основываясь на которой операторы реляционной алгебры находятся в списке токенов.