{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:52:52Z","timestamp":1775638372913,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2019,11,5]]},"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 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 9R.<\/jats:p>","DOI":"10.1145\/3371316.3371331","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T18:56:07Z","timestamp":1572980167000},"page":"60-67","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["MATLANG"],"prefix":"10.1145","volume":"48","author":[{"given":"Robert","family":"Brijder","sequence":"first","affiliation":[{"name":"Hasselt University, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[{"name":"Hasselt University, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timmy","family":"Weerwag","sequence":"additional","affiliation":[{"name":"Hasselt University, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases . Addison-Wesley , 1995 . S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"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":"Algorithms in Real Algebraic Geometry","author":"Basu S.","year":"2008","unstructured":"S. Basu , R. Pollack , and M.-F. Roy . Algorithms in Real Algebraic Geometry . Springer , second edition, 2008 . S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, second edition, 2008."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007279"},{"key":"e_1_2_1_6_1","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/089","volume-title":"A Course on the Web Graph","author":"Bonato A.","year":"2008","unstructured":"A. Bonato . A Course on the Web Graph , volume 89 of Graduate Studies in Mathematics . American Mathematical Society , 2008 . A. Bonato. A Course on the Web Graph, volume 89 of Graduate Studies in Mathematics. American Mathematical Society, 2008."},{"key":"e_1_2_1_7_1","volume-title":"ACM TODS","author":"Brijder R.","year":"2019","unstructured":"R. Brijder , F. Geerts , J. Van den Bussche, and T. Weerwag. On the expressive power of query languages for matrices . ACM TODS , 2019 . To appear. R. Brijder, F. Geerts, J. Van den Bussche, and T. Weerwag. On the expressive power of query languages for matrices. ACM TODS, 2019. To appear."},{"key":"e_1_2_1_8_1","volume-title":"On matrices and K-relations. arXiv:1904.03934","author":"Brijder R.","year":"2019","unstructured":"R. Brijder , M. Gyssens , and J. Van den Bussche . On matrices and K-relations. arXiv:1904.03934 , 2019 . R. Brijder, M. Gyssens, and J. Van den Bussche. On matrices and K-relations. arXiv:1904.03934, 2019."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137633"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212685"},{"key":"e_1_2_1_12_1","series-title":"LNCS","first-page":"17","volume-title":"Proc. WoLLIC","author":"Dawar A.","year":"2008","unstructured":"A. Dawar . On the descriptive complexity of linear algebra . In W. Hodges and R. de Queiroz, editors, Proc. WoLLIC 2008 , volume 5110 of LNCS , pages 17 -- 25 . Springer , 2008. A. Dawar. On the descriptive complexity of linear algebra. In W. Hodges and R. de Queiroz, editors, Proc. WoLLIC 2008, volume 5110 of LNCS, pages 17--25. Springer, 2008."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.24"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129108"},{"key":"e_1_2_1_15_1","volume-title":"Proc. ICDT 2019","volume":"127","author":"Geerts F.","year":"2019","unstructured":"F. Geerts . On the expressive power of linear algebra on graphs . In Proc. ICDT 2019 , volume 127 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , 2019 . F. Geerts. On the expressive power of linear algebra on graphs. In Proc. ICDT 2019, volume 127 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060216"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix Computations","author":"Golub G.","year":"2013","unstructured":"G. Golub and C. Van Loan . Matrix Computations . The Johns Hopkins University Press , fourth edition, 2013 . G. Golub and C. Van Loan. Matrix Computations. The Johns Hopkins University Press, fourth edition, 2013."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367510"},{"key":"e_1_2_1_20_1","volume-title":"University of Cambridge","author":"Holm B.","year":"2010","unstructured":"B. Holm . Descriptive Complexity of Linear Algebra. PhD thesis , University of Cambridge , 2010 . B. Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010."},{"key":"e_1_2_1_21_1","first-page":"1","volume-title":"Proc. BeyondMR 2007","author":"Hutchison D.","year":"2007","unstructured":"D. Hutchison , B. Howe , and D. Suciu . LaraDB: a minimalist kernel for linear and relational algebra computation . In Proc. BeyondMR 2007 , pages 2: 1 -- 2 :10, 2007 . D. Hutchison, B. Howe, and D. Suciu. LaraDB: a minimalist kernel for linear and relational algebra computation. In Proc. BeyondMR 2007, pages 2:1--2:10, 2007."},{"key":"e_1_2_1_22_1","volume-title":"Inc.","author":"Iverson K.","year":"1962","unstructured":"K. Iverson . A Programming Language. John Wiley & Sons , Inc. , 1962 . K. Iverson. A Programming Language. John Wiley & Sons, Inc., 1962."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"e_1_2_1_24_1","volume-title":"Arizona State University","author":"Kim M.","year":"2014","unstructured":"M. Kim . TensorDB and Tensor-Relational Model for Efficient Tensor-Relational Operations. PhD thesis , Arizona State University , 2014 . M. Kim. TensorDB and Tensor-Relational Model for Efficient Tensor-Relational Operations. PhD thesis, Arizona State University, 2014."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322332"},{"key":"e_1_2_1_26_1","volume-title":"Finite Model Theory and Its Applications","author":"Kolaitis P.","year":"2007","unstructured":"P. Kolaitis . On the expressive power of logics on finite models . In Finite Model Theory and Its Applications , chapter 2. Springer , 2007 . P. Kolaitis. On the expressive power of logics on finite models. In Finite Model Theory and Its Applications, chapter 2. Springer, 2007."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926534.2926540"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04031-7","volume-title":"Constraint Databases","author":"Kuper G.","year":"2000","unstructured":"G. Kuper , L. Libkin , and J. Paredaens , editors . Constraint Databases . Springer , 2000 . G. Kuper, L. Libkin, and J. Paredaens, editors. Constraint Databases. Springer, 2000."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00736-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.108"},{"key":"e_1_2_1_33_1","volume-title":"A survey on array storage, query languages, and systems. arXiv:1302.0103","author":"Rusu F.","year":"2013","unstructured":"F. Rusu and Y. Cheng . A survey on array storage, query languages, and systems. arXiv:1302.0103 , 2013 . F. Rusu and Y. Cheng. A survey on array storage, query languages, and systems. arXiv:1302.0103, 2013."},{"key":"e_1_2_1_34_1","volume-title":"arXiv:1703.03193","author":"Sato T.","year":"2017","unstructured":"T. Sato . Embedding Tarskian semantics in vector spaces. arXiv:1703.03193 , 2017 . T. Sato. Embedding Tarskian semantics in vector spaces. arXiv:1703.03193, 2017."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000023"},{"key":"e_1_2_1_36_1","series-title":"LNCS","first-page":"334","volume-title":"Graph Drawing","author":"Schaefer M.","year":"2009","unstructured":"M. Schaefer . Complexity of some geometric and topological problems . In D. Eppstein and E. Gansner, editors, Graph Drawing , volume 5849 of LNCS , pages 334 -- 344 . Springer , 2009 . M. Schaefer. Complexity of some geometric and topological problems. In D. Eppstein and E. Gansner, editors, Graph Drawing, volume 5849 of LNCS, pages 334--344. Springer, 2009."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9662-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284963"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265551"},{"key":"e_1_2_1_41_1","first-page":"137","volume-title":"Proc. STOC 1982","author":"Vardi M.","year":"1982","unstructured":"M. Vardi . The complexity of relational query languages . In Proc. STOC 1982 , pages 137 -- 146 , 1982 . M. Vardi. The complexity of relational query languages. In Proc. STOC 1982, pages 137--146, 1982."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447819"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371316.3371331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:05Z","timestamp":1750204385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371331"}},"subtitle":["Matrix operations and their expressive power"],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,11,5]]}},"alternative-id":["10.1145\/3371316.3371331"],"URL":"https:\/\/doi.org\/10.1145\/3371316.3371331","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11,5]]},"assertion":[{"value":"2019-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}