The Monoid Algebra

The following are the algebraic operators used by lambda-DB:

• get( monoid, extent_name, range_variable, predicate ): Captures the OQL query: select * from range_variable in extent_name where predicate. It creates a collection, where each tuple has only one component, range_variable, bound to an object of this extent. The predicate has the form and(p1,...,pn) to indicate the conjunction of the predicates pi. The predicates are not allowed to contain nested queries (all forms of query nesting are eliminated).

• reduce( monoid, expr, variable, head, predicate ): For each tuple in the collection expr that satisfies the predicate, it evaluates the head. Then it reduces the resulting collection to a value (bound to variable) or a collection (where each tuple binds variable to the value of head), depending on the output monoid.

• join( monoid, left, right, predicate, keep ): The relational join operator. It concatenates the tuples of the left and right collections if they satisfy the predicate and creates a new collection out of the new tuples. keep indicates which variables to keep from left (if any) in case of a left outerjoin (if no tuple is joined with the value of a keep variable, the latter is joined with null).

• unnest( monoid, expr, variable, path, predicate, keep ): It unnests the inner collection path of the outer collection expr and filters out all tuples that do not satisfy the predicate. For example, if expr is of type set(<x: <name:string, children:set(person)>>) and path=x.children, then the output of this operation has type set(<name:string, children:set(person), variable:person>). keep plays the same role as for joins.

• nest( monoid, expr, variable, head, groupby, predicate ): It groups the expr by the variables in groupby. Then, for each different binding of the groupby variables, it creates a tuple extented with the binding of variable to the value reduce(monoid,plan,variable,head,predicate).

• merge( monoid, left, right ): Merges the (union-compatible) input expressions.

For example, the OQL query

select distinct struct( E: e.name,
			M: ( select c.name
			     from c in e.children
			    where c.age > 18 ) )
from e in Employees
where e.name = "Smith";

reduce(set,
       nest(bag,
            unnest(bag,
                   get(set,
                       Employees,
                       e,
                       and(eq(project(e,name),"Smith"))),
                   c,
                   project(e,children),
                   and(gt(project(c,age),18)),
                   e),
            x,
            project(c,name),
            e,
            and()),
       y,
       struct(bind(E,project(e,name)),bind(M,x)),
       and())

get     -> bag(< e: Employee >)
unnest  -> bag(< e: Employee, c: Person >)
nest    -> bag(< e: Employee, x: bag(string) >)
reduce  -> set(< E: string, M: bag(string) >)