research-article

MATLANG: Matrix operations and their expressive power

Authors:

Robert Brijder,

Jan Van den Bussche,

Timmy WeerwagAuthors Info & Claims

ACM SIGMOD Record, Volume 48, Issue 1

Pages 60 - 67

https://doi.org/10.1145/3371316.3371331

Published: 05 November 2019 Publication History

Abstract

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.

References

[1]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[2]

M. Abo Khamis, H. Ngo, and A. Rudra. FAQ: questions asked frequently. In Proc. PODS 2016. ACM Press, 2016.

Digital Library

[3]

D. Arnon. Geometric reasoning with logic and algebra. Artif. Intell., 37:37--60, 1988.

Digital Library

[4]

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, second edition, 2008.

[5]

M. Boehm et al. SystemML: declarative machine learning on Spark. Proc. VLDB Endow, 9(13):1425--1436, 2016.

Digital Library

[6]

A. Bonato. A Course on the Web Graph, volume 89 of Graduate Studies in Mathematics. American Mathematical Society, 2008.

[7]

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.

[8]

R. Brijder, M. Gyssens, and J. Van den Bussche. On matrices and K-relations. arXiv:1904.03934, 2019.

[9]

S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Comput. Networks ISDN, 30:107--117, 1998.

Digital Library

[10]

L. Chen, A. Kumar, J. Naughton, and J. Patel. Towards linear algebra over normalized data. Proc. VLDB Endow, 10(11):1214--1225, 2017.

Digital Library

[11]

S. Datta, R. Kulkarni, A. Mukherjee, T. Schwentick, and T. Zeume. Reachability is in DynFO. J. ACM, 65(5):33:1--33:24, 2018.

Digital Library

[12]

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.

[13]

A. Dawar, M. Grohe, B. Holm, and B. Laubner. Logics with rank operators. In Proc. LICS 2009, pages 113--122, 2009.

Digital Library

[14]

G. Del Corso, A. Gulli, and F. Romani. Fast PageRank computation via a sparse linear system. Internet Math., 2(3):251--273, 2005.

[15]

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.

[16]

C. Godsil. Some graphs with characteristic polynomials which are not solvable by radicals. J. Graph Theory, 6:211--214, 1982.

[17]

G. Golub and C. Van Loan. Matrix Computations. The Johns Hopkins University Press, fourth edition, 2013.

[18]

T. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In Proc. PODS 2007, pages 31--40. ACM Press, 2007.

Digital Library

[19]

J. Hellerstein et al. The MADlib analytics library: Or MAD skills, the SQL. Proc. VLDB Endow, 5(12):1700--1711, 2012.

Digital Library

[20]

B. Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010.

[21]

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.

[22]

K. Iverson. A Programming Language. John Wiley & Sons, Inc., 1962.

Digital Library

[23]

P. Kanellakis, G. Kuper, and P. Revesz. Constraint query languages. J. Comput. Syst. Sci., 51(1):26--52, Aug. 1995.

Digital Library

[24]

M. Kim. TensorDB and Tensor-Relational Model for Efficient Tensor-Relational Operations. PhD thesis, Arizona State University, 2014.

[25]

A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM, 29(3):699--717, 1982.

Digital Library

[26]

P. Kolaitis. On the expressive power of logics on finite models. In Finite Model Theory and Its Applications, chapter 2. Springer, 2007.

[27]

A. Kunft, A. Alexandrov, A. Katsifodimos, and V. Markl. Bridging the gap: Towards optimization across linear and relational algebra. In Proc. BeyondMR 2016, pages 1:1--1:4, 2016.

Digital Library

[28]

G. Kuper, L. Libkin, and J. Paredaens, editors. Constraint Databases. Springer, 2000.

Digital Library

[29]

B. Laubner. The Structure of Graphs and New Logics for the Characterization of Polynomial Time. PhD thesis, Humboldt-Universit¨at zu Berlin, 2010.

[30]

L. Libkin. Expressive power of SQL. Theor. Comput. Sci., 296:379--404, 2003.

Digital Library

[31]

S. Luo, Z. Gao, M. Gubanov, L. L. Perez, and C. Jermaine. Scalable linear algebra on a relational database system. In Proc. ICDE 2017, pages 523--534. IEEE Computer Society, 2017.

[32]

W. Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen, 2015.

[33]

F. Rusu and Y. Cheng. A survey on array storage, query languages, and systems. arXiv:1302.0103, 2013.

[34]

T. Sato. Embedding Tarskian semantics in vector spaces. arXiv:1703.03193, 2017.

[35]

T. Sato. A linear algebra approach to datalog evaluation. Theory Pract. Log. Prog., 17(3):244--265, 2017.

[36]

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.

[37]

M. Schaefer and D. Stefankovic. Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst., 60(2):172--193, 2017.

Digital Library

[38]

M. Schleich, D. Olteanu, and R. Ciucanu. Learning linear regression models over factorized joins. In Proc. SIGMOD 2016, pages 3--18. ACM, 2016.

Digital Library

[39]

A. Thomas and A. Kumar. A comparative evaluation of systems for scalable linear algebra-based analytics. Proc. VLDB Endow, 11(13):2168--2182, 2018.

Digital Library

[40]

J. Van den Bussche, D. Van Gucht, and S. Vansummeren. A crash course in database queries. In Proc. PODS 2007, pages 143--154. ACM Press, 2007.

Digital Library

[41]

M. Vardi. The complexity of relational query languages. In Proc. STOC 1982, pages 137--146, 1982.

[42]

Y. Zhang, W. Zhang, and J. Yang. I/O-efficient statistical computing with RIOT. In Proc. ICDE 2010, pages 1157--1160, 2010.

Cited By

Aydoğdu MAydoğdu ÖPehlivan H(2024)MxPL: A Programming Language for Matrix-Related OperationsSymmetry10.3390/sym1602018116:2(181)Online publication date: 2-Feb-2024
https://doi.org/10.3390/sym16020181
Gillet ALeclercq ÉSavonnet MCullot NDesai BCho W(2020)Empowering big data analytics with polystore and strongly typed functional queriesProceedings of the 24th Symposium on International Database Engineering & Applications10.1145/3410566.3410591(1-10)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3410566.3410591

MATLANG: Matrix operations and their expressive power
1. Information systems
  1. Data management systems
2. Theory of computation

Recommendations

On the HSS iteration methods for positive definite Toeplitz linear systems

We study the HSS iteration method for large sparse non-Hermitian positive definite Toeplitz linear systems, which first appears in Bai, Golub and Ng's paper published in 2003 [Z.-Z. Bai, G.H. Golub, M.K. Ng, Hermitian and skew-Hermitian splitting ...
Accurate Eigenvalues and SVDs of Totally Nonnegative Matrices

We consider the class of totally nonnegative (TN) matrices---matrices all of whose minors are nonnegative. Any nonsingular TN matrix factors as a product of nonnegative bidiagonal matrices. The entries of the bidiagonal factors parameterize the set of ...
Shifted SSOR-like preconditioner for non-Hermitian positive definite matrices

Based on the SSOR-like iteration method of Bai (Numer. Linear Algebra Appl. 23, 37-60, 2016), we give a shifted SSOR-like preconditioner which is positive definite for solving the non-Hermitian positive definite linear system with a dominant Hermitian ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 48, Issue 1

March 2019

81 pages

ISSN:0163-5808

DOI:10.1145/3371316

Editors:
Yanlei Diao
University of Massachusetts Amherst
,
Rada Chirkova
North Carolina State University
,
Vanessa Braganholo
Universidade Federal Fluminense
,
Marco Brambilla
Politecnico di Milano
,
Chee Yong Chan
National University of Singapore
,
Zackary Ives
University of Pennsylvania
,
Anastasios Kementsietsidis
Google Research
,
Wim Martens
University of Bayreuth
,
Frank Neven
Hasselt University
,
Olga Papaemmanoui
Brandeis Univesity
,
Aditya Parameswaran
University of Illinois
,
Alkis Simitsis
HP Labs
,
Divesh Srivastava
ATT research
,
Pinar Tözü
IBM Almaden Research Center
,
Marianne Winslett
University of Illinois
,
Jun Yang
Duke University

Issue’s Table of Contents

Copyright © 2019 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2019

Published in SIGMOD Volume 48, Issue 1

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aydoğdu MAydoğdu ÖPehlivan H(2024)MxPL: A Programming Language for Matrix-Related OperationsSymmetry10.3390/sym1602018116:2(181)Online publication date: 2-Feb-2024
https://doi.org/10.3390/sym16020181
Gillet ALeclercq ÉSavonnet MCullot NDesai BCho W(2020)Empowering big data analytics with polystore and strongly typed functional queriesProceedings of the 24th Symposium on International Database Engineering & Applications10.1145/3410566.3410591(1-10)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3410566.3410591

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents