{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:13Z","timestamp":1787337553925,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>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 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.<\/jats:p>","DOI":"10.1137\/s0097539701390859","type":"journal-article","created":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T09:06:04Z","timestamp":1088672764000},"page":"1052-1066","source":"Crossref","is-referenced-by-count":6,"title":["Solving Equations in the Relational Algebra"],"prefix":"10.1137","volume":"33","author":[{"given":"Joachim","family":"Biskup","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Paredaens","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and G. Hillebrand,\n                      Space usage in functional query languages\n                      , in Database Theory\u2014ICDT\u201995, G. Gottlob and M. Y. Vardi, eds., Lecture Notes in Comput. Sci. 893, Springer\u2010Verlag, New York, 1995, pp. 439\u2013454.","DOI":"10.1007\/3-540-58907-4_33"},{"key":"R2","unstructured":"S. Abiteboul, R. Hull, and V. Vianu,\n                      Foundations of Databases\n                      , Addison\u2010Wesley, Reading, MA, 1995."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Eric Allender, The complexity of sparse sets in P (preliminary report), Lecture Notes in Comput. Sci., Vol. 223, Springer, Berlin, 1986, 1\u201311854886","DOI":"10.1007\/3-540-16486-3_85"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu,\n                      Generic computation and its complexity\n                      , in Proceedings of the 23rd ACM Symposium on the Theory of Computing, New Orleans, LA, 1991, pp. 209\u2013219.","DOI":"10.1145\/103418.103444"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"H.\u2010D. Ebbinghaus and J. Flum,\n                      Finite Model Theory\n                      , Springer, New York, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"R6","unstructured":"Ronald Fagin, Generalized first\u2010order spectra and polynomial\u2010time recognizable sets, Amer. Math. Soc., Providence, R.I., 1974, 0\u20130, 43\u201373. SIAM\u2010AMS Proc., Vol. VII51:7840"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2882"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1058"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90041-G"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Phokion Kolaitis, Implicit definability on finite structures and unambiguous computations (preliminary report), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 168\u20131801099170","DOI":"10.1109\/LICS.1990.113743"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-47.2.337"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/128765.128768"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1526"},{"key":"R14","unstructured":"S. Thomas and P. Fischer,\n                      Nested relational structures\n                      , in The Theory of Databases, P. Kanellakis, ed., JAI Press, Greenwich, CT, 1986, pp. 269\u2013307."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00301-1"},{"key":"R16","volume-title":"Finite permutation groups","author":"Wielandt Helmut","year":"1964"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539701390859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:01Z","timestamp":1787336221000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539701390859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0097539701390859"],"URL":"https:\/\/doi.org\/10.1137\/s0097539701390859","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}