Solving Equations in the Relational Algebra
Copyright policy )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.
Minor revision, accepted for publication in SIAM Journal on Computing
- Hasselt University Belgium
- University of Antwerp Belgium
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, nested relation, Fagin's theorem, F.4.2; H.2.3, Database theory, Model theory of finite structures, equation, Databases (cs.DB), Graphs and abstract algebra (groups, rings, fields, etc.), Logic in Computer Science (cs.LO), H.2.3, Computer Science - Databases, parity, sparse expression, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), F.4.2, relational algebra
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, nested relation, Fagin's theorem, F.4.2; H.2.3, Database theory, Model theory of finite structures, equation, Databases (cs.DB), Graphs and abstract algebra (groups, rings, fields, etc.), Logic in Computer Science (cs.LO), H.2.3, Computer Science - Databases, parity, sparse expression, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), F.4.2, relational algebra
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).6 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!