# The OQL Algebra

The following are the logical NFNF operators used by ODB:

- `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 inputs if they satisfy the `predicate`. If `keep=left`, then it behaves like an left-outer join (it concatenates the left tuple with null values), if `keep=right` it behaves like a right-outer join, while if`keep=none`, it is a regular join.
- `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>)`. If there are no values, or no value satisfies the predicate, and `keep=true`, then the tuple is padded with a null value.
- `nest( monoid, expr, variable, head, groupby, nestvars, predicate )`: It groups the `expr` by the variables in `groupby`. (`groupby` has the form: `vars(v1,...,vn)`, where a `vi` is a variable defined in `expr`.) 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)` and with the values of the `nestvars` variables (which are the nest variables in `expr`).
- `map( monoid, expr, variable, function )`: maps the function (that depends on the variable) over expr. It is a simpler version of `reduce`.
- `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";

has the following algebraic form:

    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)),
                       true),
                x,
                project(c,name),
                vars(e),
                vars(),
                and()),
           y,
           struct(bind(E,project(e,name)),bind(M,x)),
           and())

and each of the above operations yields values of the following types:

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

Notice that the unnest operation has `keep=true`, i.e., it keeps every employee even if this employee has no children older than 18. In that case, `c` is bound to null. This null value is converted to the empty bag (the zero of the bag monoid) during the nest operation.