{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:24Z","timestamp":1778807724094,"version":"3.51.4"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T00:00:00Z","timestamp":1571097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>We investigate the expressive power of MATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation inv for inverting a matrix. In MATLANG + inv, we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed, we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation eigen for diagonalizing a matrix. It is defined such that for each eigenvalue a set of mutually orthogonal eigenvectors is returned that span the eigenspace of that eigenvalue. We show that inv can be expressed in MATLANG + eigen. We put forward the open question whether there are Boolean queries about matrices, or generic queries about graphs, expressible in MATLANG + eigen but not in MATLANG + inv. Finally, the evaluation problem for MATLANG + eigen is shown to be complete for the complexity class \u2203 R.<\/jats:p>","DOI":"10.1145\/3331445","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T16:35:58Z","timestamp":1571157358000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["On the Expressive Power of Query Languages for Matrices"],"prefix":"10.1145","volume":"44","author":[{"given":"Robert","family":"Brijder","sequence":"first","affiliation":[{"name":"Hasselt University, Martelarenlaan, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Antwerp, Middelheimlaan, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan Van Den","family":"Bussche","sequence":"additional","affiliation":[{"name":"Hasselt University, Martelarenlaan, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timmy","family":"Weerwag","sequence":"additional","affiliation":[{"name":"Hasselt University, Martelarenlaan, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.  S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings 35th ACM Symposium on Principles of Database Systems, T. Milo and W.-C. Tan (Eds.). ACM, 13--28","author":"Abo Khamis M.","unstructured":"M. Abo Khamis , H.Q. Ngo , and A. Rudra . 2016. FAQ: Questions asked frequently . In Proceedings 35th ACM Symposium on Principles of Database Systems, T. Milo and W.-C. Tan (Eds.). ACM, 13--28 . M. Abo Khamis, H.Q. Ngo, and A. Rudra. 2016. FAQ: Questions asked frequently. In Proceedings 35th ACM Symposium on Principles of Database Systems, T. Milo and W.-C. Tan (Eds.). ACM, 13--28."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90049-5"},{"key":"e_1_2_1_4_1","volume-title":"Linear Algebra Done Right","author":"Axler S.","unstructured":"S. Axler . 2015. Linear Algebra Done Right ( third ed.). Springer . S. Axler. 2015. Linear Algebra Done Right (third ed.). Springer."},{"key":"e_1_2_1_5_1","volume-title":"Algorithms in Real Algebraic Geometry","author":"Basu S.","unstructured":"S. Basu , R. Pollack , and M.-F. Roy . 2008. Algorithms in Real Algebraic Geometry ( second ed.). Springer . S. Basu, R. Pollack, and M.-F. Roy. 2008. Algorithms in Real Algebraic Geometry (second ed.). Springer."},{"key":"e_1_2_1_6_1","volume-title":"Real Algebraic Geometry","author":"Bochnak J.","unstructured":"J. Bochnak , M. Coste , and M.-F. Roy . 1998. Real Algebraic Geometry . Springer-Verlag . J. Bochnak, M. Coste, and M.-F. Roy. 1998. Real Algebraic Geometry. Springer-Verlag."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007279"},{"key":"e_1_2_1_8_1","volume-title":"Graduate Studies in Mathematics","volume":"89","author":"Bonato A.","year":"2008","unstructured":"A. Bonato . 2008 . A Course on the Web Graph . Graduate Studies in Mathematics , Vol. 89 . American Mathematical Society. A. Bonato. 2008. A Course on the Web Graph. Graduate Studies in Mathematics, Vol. 89. American Mathematical Society."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 21st International Conference on Database Theory (LIPIcs)","volume":"98","author":"Brijder R.","unstructured":"R. Brijder , F. Geerts , J. Van den Bussche, and T. Weerwag. 2018. On the expressive power of query languages for matrices . In Proceedings of the 21st International Conference on Database Theory (LIPIcs) , Vol. 98 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 10:1--10:17. R. Brijder, F. Geerts, J. Van den Bussche, and T. Weerwag. 2018. On the expressive power of query languages for matrices. In Proceedings of the 21st International Conference on Database Theory (LIPIcs), Vol. 98. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 10:1--10:17."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"R. Brijder M. Gyssens and J. Van den Bussche. 2019. On matrices and -relations. arXiv:1904.03934.  R. Brijder M. Gyssens and J. Van den Bussche. 2019. On matrices and -relations. arXiv:1904.03934.","DOI":"10.1007\/978-3-030-39951-1_3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807271"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137633"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings 42nd International Colloquium on Automata, Languages and Programming, Part II (Lecture Notes in Computer Science), M. M. Halld\u00f3rsson, K. Iwama, N. Kobayashi, and B. Speckmann (Eds.)","volume":"9135","author":"Datta S.","unstructured":"S. Datta , R. Kulkarni , A. Mukherjee , T. Schwentick , and T. Zeume . 2015. Reachability is in DynFO . In Proceedings 42nd International Colloquium on Automata, Languages and Programming, Part II (Lecture Notes in Computer Science), M. M. Halld\u00f3rsson, K. Iwama, N. Kobayashi, and B. Speckmann (Eds.) , Vol. 9135 . Springer, 159--170. S. Datta, R. Kulkarni, A. Mukherjee, T. Schwentick, and T. Zeume. 2015. Reachability is in DynFO. In Proceedings 42nd International Colloquium on Automata, Languages and Programming, Part II (Lecture Notes in Computer Science), M. M. Halld\u00f3rsson, K. Iwama, N. Kobayashi, and B. Speckmann (Eds.), Vol. 9135. Springer, 159--170."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212685"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings 15th WoLLIC (Lecture Notes in Computer Science), W. Hodges and R. de Queiroz (Eds.)","volume":"5110","author":"Dawar A.","year":"2008","unstructured":"A. Dawar . 2008 . On the descriptive complexity of linear algebra. In Logic, Language, Information and Computation , Proceedings 15th WoLLIC (Lecture Notes in Computer Science), W. Hodges and R. de Queiroz (Eds.) , Vol. 5110 . Springer, 17--25. A. Dawar. 2008. On the descriptive complexity of linear algebra. In Logic, Language, Information and Computation, Proceedings 15th WoLLIC (Lecture Notes in Computer Science), W. Hodges and R. de Queiroz (Eds.), Vol. 5110. Springer, 17--25."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. 113--122","author":"Dawar A.","unstructured":"A. Dawar , M. Grohe , B. Holm , and B. Laubner . 2009. Logics with rank operators . In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. 113--122 . A. Dawar, M. Grohe, B. Holm, and B. Laubner. 2009. Logics with rank operators. In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. 113--122."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1471"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129108"},{"key":"e_1_2_1_22_1","first-page":"1252","article-title":"Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph","volume":"11","author":"Furman M. E.","year":"1970","unstructured":"M. E. Furman . 1970 . Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph . Soviet Mathematics Doklady 11 , 5 (1970), 1252 . M. E. Furman. 1970. Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Soviet Mathematics Doklady 11, 5 (1970), 1252.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 22nd International Conference on Database Theory (LIPIcs)","volume":"127","author":"Geerts F.","year":"2019","unstructured":"F. Geerts . 2019 . On the expressive power of linear algebra on graphs . In Proceedings of the 22nd International Conference on Database Theory (LIPIcs) , Vol. 127 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 7:1--7:19. F. Geerts. 2019. On the expressive power of linear algebra on graphs. In Proceedings of the 22nd International Conference on Database Theory (LIPIcs), Vol. 127. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 7:1--7:19."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060216"},{"key":"e_1_2_1_25_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"G. H. Golub and C. F. Van Loan . 2013. Matrix Computations ( fourth ed.). The Johns Hopkins University Press . G. H. Golub and C. F. Van Loan. 2013. Matrix Computations (fourth ed.). The Johns Hopkins University Press."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 24th EACSL Annual Conference on Computer Science Logic (CSL). 390--404","author":"Gr\u00e4del E.","unstructured":"E. Gr\u00e4del and W. Pakusa . 2015. Rank logic is dead, long live rank logic&excl; . In Proceedings of the 24th EACSL Annual Conference on Computer Science Logic (CSL). 390--404 . E. Gr\u00e4del and W. Pakusa. 2015. Rank logic is dead, long live rank logic&excl;. In Proceedings of the 24th EACSL Annual Conference on Computer Science Logic (CSL). 390--404."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050130"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 26th ACM Symposium on Principles of Database Systems. 31--40","author":"Green T. J.","unstructured":"T. J. Green , G. Karvounarakis , and V. Tannen . 2007. Provenance semirings . In Proceedings of the 26th ACM Symposium on Principles of Database Systems. 31--40 . T. J. Green, G. Karvounarakis, and V. Tannen. 2007. Provenance semirings. In Proceedings of the 26th ACM Symposium on Principles of Database Systems. 31--40."},{"key":"e_1_2_1_29_1","volume-title":"32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 1--12","author":"Grohe M.","unstructured":"M. Grohe and W. Pakusa . 2017. Descriptive complexity of linear equation systems and applications to propositional proof complexity . In 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 1--12 . M. Grohe and W. Pakusa. 2017. Descriptive complexity of linear equation systems and applications to propositional proof complexity. In 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 1--12."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502100"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367510"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, F. N. Afrati and J. Sroka (Eds.). 2:1--2:10","author":"Hutchison D.","unstructured":"D. Hutchison , B. Howe , and D. Suciu . 2017. LaraDB: A minimalist kernel for linear and relational algebra computation . In Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, F. N. Afrati and J. Sroka (Eds.). 2:1--2:10 . D. Hutchison, B. Howe, and D. Suciu. 2017. LaraDB: A minimalist kernel for linear and relational algebra computation. In Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, F. N. Afrati and J. Sroka (Eds.). 2:1--2:10."},{"key":"e_1_2_1_34_1","volume-title":"A Programming Language","author":"Iverson K. E.","unstructured":"K. E. Iverson . 1962. A Programming Language . John Wiley 8 Sons, Inc. K. E. Iverson. 1962. A Programming Language. John Wiley 8 Sons, Inc."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322332"},{"key":"e_1_2_1_38_1","first-page":"27","article-title":"On the expressive power of logics on finite models. In Finite Model Theory and Its Applications. Springer","volume":"2","author":"Kolaitis Ph. G.","year":"2007","unstructured":"Ph. G. Kolaitis . 2007 . On the expressive power of logics on finite models. In Finite Model Theory and Its Applications. Springer , Chapter 2 , 27 -- 123 . Ph. G. Kolaitis. 2007. On the expressive power of logics on finite models. In Finite Model Theory and Its Applications. Springer, Chapter 2, 27--123.","journal-title":"Chapter"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. 1:1--1:4.","author":"Kunft A.","unstructured":"A. Kunft , A. Alexandrov , A. Katsifodimos , and V. Markl . 2016. Bridging the gap: Towards optimization across linear and relational algebra . In Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. 1:1--1:4. A. Kunft, A. Alexandrov, A. Katsifodimos, and V. Markl. 2016. Bridging the gap: Towards optimization across linear and relational algebra. In Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. 1:1--1:4."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"G. Kuper L. Libkin and J. Paredaens (Eds.). 2000. Constraint Databases. Springer.  G. Kuper L. Libkin and J. Paredaens (Eds.). 2000. Constraint Databases. Springer.","DOI":"10.1007\/978-3-662-04031-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"J. Leskovec A. Rajaraman and J. D. Ullman. 2014. Mining of Massive Datasets (second ed.). Cambridge University Press.  J. Leskovec A. Rajaraman and J. D. Ullman. 2014. Mining of Massive Datasets (second ed.). Cambridge University Press.","DOI":"10.1017\/CBO9781139924801"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00736-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3277006.3277013"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 33rd International Conference on Data Engineering. IEEE Computer Society, 523--534","author":"Luo S.","unstructured":"S. Luo , Z. J. Gao , M. N. Gubanov , L. Leopoldo Perez , and C. M. Jermaine . 2017. Scalable linear algebra on a relational database system . In Proceedings of the 33rd International Conference on Data Engineering. IEEE Computer Society, 523--534 . S. Luo, Z. J. Gao, M. N. Gubanov, L. Leopoldo Perez, and C. M. Jermaine. 2017. Scalable linear algebra on a relational database system. In Proceedings of the 33rd International Conference on Data Engineering. IEEE Computer Society, 523--534."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"M. Marx and Y. Venema. 1997. Multi-Dimensional Modal Logic. Springer.  M. Marx and Y. Venema. 1997. Multi-Dimensional Modal Logic. Springer.","DOI":"10.1007\/978-94-011-5694-3"},{"key":"e_1_2_1_47_1","unstructured":"J. Matou\u0161ek. 2014. Intersection graphs of segments and &exist;R. arXiv:1406.2636.  J. Matou\u0161ek. 2014. Intersection graphs of segments and &exist;R. arXiv:1406.2636."},{"key":"e_1_2_1_48_1","unstructured":"Microsoft SQL Server R Services. 2019.  Microsoft SQL Server R Services. 2019."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management (CEUR Workshop Proceedings), J. L. Reutter and D. Srivastava (Eds.)","volume":"1912","author":"Ngo H. Q.","unstructured":"H. Q. Ngo , X. Nguyen , D. Olteanu , and M. Schleich . 2017. In-database factorized learning . In Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management (CEUR Workshop Proceedings), J. L. Reutter and D. Srivastava (Eds.) , Vol. 1912 . H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. 2017. In-database factorized learning. In Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management (CEUR Workshop Proceedings), J. L. Reutter and D. Srivastava (Eds.), Vol. 1912."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90128-7"},{"key":"e_1_2_1_52_1","unstructured":"Oracle R. Enterprise. 2019.  Oracle R. Enterprise. 2019."},{"key":"e_1_2_1_53_1","series-title":"Lecture Notes in Logic","volume-title":"Bounded Variable Logics and Counting: A Study in Finite Models","author":"Otto M.","unstructured":"M. Otto . 1997. Bounded Variable Logics and Counting: A Study in Finite Models . Lecture Notes in Logic , Vol. 9 . Springer . M. Otto. 1997. Bounded Variable Logics and Counting: A Study in Finite Models. Lecture Notes in Logic, Vol. 9. Springer."},{"key":"e_1_2_1_55_1","unstructured":"F. Rusu and Y. Cheng. 2013. A survey on array storage query languages and systems. arXiv:1302.0103.  F. Rusu and Y. Cheng. 2013. A survey on array storage query languages and systems. arXiv:1302.0103."},{"key":"e_1_2_1_56_1","unstructured":"T. Sato. 2017. Embedding Tarskian semantics in vector spaces. arXiv:1703.03193.  T. Sato. 2017. Embedding Tarskian semantics in vector spaces. arXiv:1703.03193."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000023"},{"key":"e_1_2_1_58_1","volume-title":"Graph Drawing (Lecture Notes in Computer Science)","author":"Schaefer M.","unstructured":"M. Schaefer . 2009. Complexity of some geometric and topological problems . In Graph Drawing (Lecture Notes in Computer Science) , D. Eppstein and E. R. Gansner (Eds.), Vol. 5849 . Springer , 334--344. M. Schaefer. 2009. Complexity of some geometric and topological problems. In Graph Drawing (Lecture Notes in Computer Science), D. Eppstein and E. R. Gansner (Eds.), Vol. 5849. Springer, 334--344."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9662-0"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data. ACM, 3--18","author":"Schleich M.","unstructured":"M. Schleich , D. Olteanu , and R. Ciucanu . 2016. Learning linear regression models over factorized joins . In Proceedings of the 2016 International Conference on Management of Data. ACM, 3--18 . M. Schleich, D. Olteanu, and R. Ciucanu. 2016. Learning linear regression models over factorized joins. In Proceedings of the 2016 International Conference on Management of Data. ACM, 3--18."},{"key":"e_1_2_1_61_1","volume-title":"AMS Colloquium Publications","volume":"41","author":"Tarski A.","unstructured":"A. Tarski and S. Givant . 1987. A Formalization of Set Theory without Variables . AMS Colloquium Publications , Vol. 41 . American Mathematical Society. A. Tarski and S. Givant. 1987. A Formalization of Set Theory without Variables. AMS Colloquium Publications, Vol. 41. American Mathematical Society."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284963"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of the 26th ACM Symposium on Principles of Database Systems. ACM Press, 143--154","author":"Van den Bussche J.","unstructured":"J. Van den Bussche , D. Van Gucht , and S. Vansummeren . 2007. A crash course in database queries . In Proceedings of the 26th ACM Symposium on Principles of Database Systems. ACM Press, 143--154 . J. Van den Bussche, D. Van Gucht, and S. Vansummeren. 2007. A crash course in database queries. In Proceedings of the 26th ACM Symposium on Principles of Database Systems. ACM Press, 143--154."},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 14th ACM Symposium on the Theory of Computing. 137--146","author":"Vardi M.","year":"1982","unstructured":"M. Vardi . 1982 . The complexity of relational query languages . In Proceedings of the 14th ACM Symposium on the Theory of Computing. 137--146 . M. Vardi. 1982. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on the Theory of Computing. 137--146."},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science, A. M. Borzyszkowski and S. Soko\u0142owski (Eds.). Springer","author":"Wagner D.","unstructured":"D. Wagner and F. Wagner . 1993. Between min cut and graph bisection . In Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science, A. M. Borzyszkowski and S. Soko\u0142owski (Eds.). Springer , Berlin, 744--750. D. Wagner and F. Wagner. 1993. Between min cut and graph bisection. In Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science, A. M. Borzyszkowski and S. Soko\u0142owski (Eds.). Springer, Berlin, 744--750."},{"key":"e_1_2_1_67_1","unstructured":"B. Westerbaan. 2016. Python implementation of Tarjan\u2019s algorithm. https:\/\/pypi.org\/project\/tarjan\/.  B. Westerbaan. 2016. Python implementation of Tarjan\u2019s algorithm. https:\/\/pypi.org\/project\/tarjan\/."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the 2010 IEEE 26th International Conference on Data Engineering (ICDE\u201910)","author":"Zhang Y.","unstructured":"Y. Zhang , W. Zhang , and J. Yang . 2010. I\/O-efficient statistical computing with RIOT . In Proceedings of the 2010 IEEE 26th International Conference on Data Engineering (ICDE\u201910) . 1157--1160. Y. Zhang, W. Zhang, and J. Yang. 2010. I\/O-efficient statistical computing with RIOT. In Proceedings of the 2010 IEEE 26th International Conference on Data Engineering (ICDE\u201910). 1157--1160."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3331445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:28Z","timestamp":1750207408000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,15]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3331445"],"URL":"https:\/\/doi.org\/10.1145\/3331445","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,15]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}