Solving equations in the relational algebra
<|reference_start|>Solving equations in the relational algebra: Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query language for nested relational databases, equivalent to the well-known powerset algebra. We study \emph{sparse} equations, which are equations with at most polynomially many solutions. We look at their complexity, and compare their expressive power with that of similar notions in the powerset algebra.<|reference_end|>
@article{biskup2001solving,
    title={Solving equations in the relational algebra},
    author={Joachim Biskup, Jan Paredaens, Thomas Schwentick, Jan Van den Bussche},
    journal={arXiv preprint arXiv:cs/0106034},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0106034},
    primaryClass={cs.LO cs.DB}
}