Document Open Access Logo

When Can Matrix Query Languages Discern Matrices?

Author Floris Geerts

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.12.pdf
  • Filesize: 0.59 MB
  • 18 pages

Document Identifiers

Author Details

Floris Geerts
  • University of Antwerp, Belgium

Acknowledgements

I want to thank Lieven Le Bruyn for inspiring discussions and for pointing me to the connections to linear control theory.

Cite As Get BibTex

Floris Geerts. When Can Matrix Query Languages Discern Matrices?. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICDT.2020.12

Abstract

We investigate when two graphs, represented by their adjacency matrices, can be distinguished by means of sentences formed in MATLANG, a matrix query language which supports a number of elementary linear algebra operators. When undirected graphs are concerned, and hence the adjacency matrices are real and symmetric, precise characterisations are in place when two graphs (i.e., their adjacency matrices) can be distinguished. Turning to directed graphs, one has to deal with asymmetric adjacency matrices. This complicates matters. Indeed, it requires to understand the more general problem of when two arbitrary matrices can be distinguished in MATLANG. We provide characterisations of the distinguishing power of MATLANG on real and complex matrices, and on adjacency matrices of directed graphs in particular. The proof techniques are a combination of insights from the symmetric matrix case and results from linear algebra and linear control theory.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query languages (principles)
  • Mathematics of computing → Graph theory
Keywords
  • matrix query languages
  • linear algebra
  • expressive power

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Albert Atserias and Elitza N. Maneva. Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM J. Comput., 42(1):112-137, 2013. URL: https://doi.org/10.1137/120867834.
  2. Sheldon Axler. Linear Algebra Done Right. Springer, third edition, 2015. URL: https://doi.org/10.1007/978-3-319-11080-6.
  3. Pablo Barceló, Nelson Higuera, Jorge Pérez, and Bernardo Subercaseaux. On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra. In 23nd International Conference on Database Theory, ICDT 2020, volume 155 of LIPIcs, pages 6:1-6:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICDT.2020.6.
  4. Matthias Boehm, Michael W. Dusenberry, Deron Eriksson, Alexandre V. Evfimievski, Faraz Makari Manshadi, Niketan Pansare, Berthold Reinwald, Frederick R. Reiss, Prithviraj Sen, Arvind C. Surve, and Shirsih Tatikonda. SystemML: Declarative machine learning on Spark. Proceedings of the VLDB Endowment, 9(13):1425-1436, 2016. URL: https://doi.org/10.14778/3007263.3007279.
  5. Matthias Boehm, Arun Kumar, and Jun Yang. Data Management in Machine Learning Systems. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2019. URL: https://doi.org/10.2200/S00895ED1V01Y201901DTM057.
  6. Matthias Boehm, Berthold Reinwald, Dylan Hutchison, Prithviraj Sen, Alexandre V. Evfimievski, and Niketan Pansare. On Optimizing Operator Fusion Plans for Large-scale Machine Learning in SystemML. Proceedings of the VLDB Endowment, 11(12):1755-1768, 2018. URL: https://doi.org/10.14778/3229863.3229865.
  7. Robert Brijder, Floris Geerts, Jan Van Den Bussche, and Timmy Weerwag. On the Expressive Power of Query Languages for Matrices. ACM Trans. Database Syst., 44(4), 2019. URL: https://doi.org/10.1145/3331445.
  8. Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag. On the Expressive Power of Query Languages for Matrices. In 21st International Conference on Database Theory, ICDT, pages 10:1-10:17, 2018. URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.10.
  9. Robert Brijder, Marc Gyssens, and Jan Van den Bussche. On Matrices and K-Relations. In Andreas Herzig and Juha Kontinen, editors, Proceedings of 11th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2020, volume 12012 of Lecture Notes in Computer Science, pages 42-57. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-39951-1_3.
  10. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
  11. Ada Chan and Chris D. Godsil. Symmetry and eigenvectors, pages 75-106. Springer Netherlands, 1997. URL: https://doi.org/10.1007/978-94-015-8937-6_3.
  12. Lingjiao Chen, Arun Kumar, Jeffrey Naughton, and Jignesh M. Patel. Towards Linear Algebra over Normalized Data. Proceedings of the VLDB Endowment, 10(11):1214-1225, 2017. URL: https://doi.org/10.14778/3137628.3137633.
  13. Martin J. Corless and Art Frazho. Linear Systems and Control: An Operator Perspective. Series: & Hall/CRC Pure and Applied Mathematics. CRC Press, 2003. Google Scholar
  14. Mohammed Dahleh, Munther A. Dahleh, and George Verghese. Lectures Notes on Dynamic Systems and Control (MIT OpenCourseWare), 2004. Google Scholar
  15. Anuj Dawar. On the Descriptive Complexity of Linear Algebra. In Proceedings of the 15th International Workshop on Logic, Language, Information and Computation, WoLLIC, pages 17-25, 2008. URL: https://doi.org/10.1007/978-3-540-69937-8_2.
  16. Anuj Dawar, Erich Grädel, and Wied Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, ICALP, pages 112:1-112:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.112.
  17. Anuj Dawar, Martin Grohe, Bjarki Holm, and Bastian Laubner. Logics with Rank Operators. In Proceedings of the 24th Annual IEEE Symposium on Logic In Computer Science, LICS, pages 113-122, 2009. URL: https://doi.org/10.1109/LICS.2009.24.
  18. Anuj Dawar and Bjarki Holm. Pebble games with algebraic rules. Fund. Inform., 150(3-4):281-316, 2017. URL: https://doi.org/10.3233/FI-2017-1471.
  19. Ahmed Elgohary, Matthias Boehm, Peter J. Haas, Frederick R. Reiss, and Berthold Reinwald. Compressed linear algebra for large-scale machine learning. The VLDB Journal, pages 1-26, 2017. URL: https://doi.org/10.1007/s00778-017-0478-1.
  20. Floris Geerts. On the Expressive Power of Linear Algebra on Graphs. In Proceedings of the 22nd International Conference on Database Theory, ICDT, volume 127 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:19. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.7.
  21. Chris Godsil. Cospectral Graph Complements and Generating Function of Walks. Mathematics Stack Exchange. URL: https://math.stackexchange.com/q/2600510.
  22. Erich Grädel and Wied Pakusa. Rank Logic is Dead, Long Live Rank Logic! In Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, CSL, pages 390-404, 2015. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.390.
  23. Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781139028868.
  24. Martin Grohe, Kristian Kersting, Martin Mladenov, and Erkal Selman. Dimension Reduction via Colour Refinement. In 22th Annual European Symposium on Algorithms, ESA, pages 505-516, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_42.
  25. Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80(3):797-844, 2015. URL: http://doi.org/10.1017/jsl.2015.28.
  26. Martin Grohe and Wied Pakusa. Descriptive complexity of linear equation systems and applications to propositional proof complexity. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 1-12, 2017. URL: https://doi.org/10.1109/LICS.2017.8005081.
  27. Bjarki Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010. Google Scholar
  28. Roger A. Horn and Charles R. Johnson. Matrix Analysis 2nd ed. Cambridge University Press, 2013. Google Scholar
  29. Dylan Hutchison, Bill Howe, and Dan Suciu. 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, BeyondMR, pages 2:1-2:10, 2017. URL: https://doi.org/10.1145/3070607.3070608.
  30. Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization. In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, pages 59-81. Springer, 1990. URL: https://doi.org/10.1007/978-1-4612-4478-3_5.
  31. Dimitrije Jankov, Shangyu Luo, Binhang Yuan, Zhuhua Cai, Jia Zou, Chris Jermaine, and Zekai J. Gao. Declarative Recursive Computation on an RDBMS. Proceedings of the VLDB Endowment, 12(7):822-835, 2019. URL: http://www.vldb.org/pvldb/vol12/p822-jankov.pdf, URL: https://doi.org/10.14778/3317315.3317323.
  32. Naihuan Jing. Unitary and orthogonal equivalence of sets of matrices. Linear Algebra and its Applications, 481:235-242, 2015. URL: https://doi.org/10.1016/j.laa.2015.04.036.
  33. Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. In-Database Learning with Sparse Tensors. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 325-340, 2018. URL: https://doi.org/10.1145/3196959.3196960.
  34. Andreas Kunft, Alexander Alexandrov, Asterios Katsifodimos, and Volker Markl. 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, BeyondMR, pages 1:1-1:4, 2016. URL: https://doi.org/10.1145/2926534.2926540.
  35. Andreas Kunft, Asterios Katsifodimos, Sebastian Schelter, Tilmann Rabl, and Volker Markl. BlockJoin: Efficient Matrix Partitioning Through Joins. Proceedings of the VLDB Endowment, 10(13):2061-2072, 2017. URL: https://doi.org/10.14778/3151106.3151110.
  36. Shangyu Luo, Zekai J. Gao, Michael N. Gubanov, Luis Leopoldo Perez, and Christopher M. Jermaine. Scalable Linear Algebra on a Relational Database System. IEEE Trans. Knowl. Data Eng., 31(7):1224-1238, 2019. URL: https://doi.org/10.1109/TKDE.2018.2827988.
  37. Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1-3):247-265, 1994. URL: https://doi.org/10.1016/0012-365X(94)90241-0.
  38. Edward R. Scheinerman and Daniel H. Ullman. Fractional Graph Theory: a Rational Approach to the Theory of Graphs. John Wiley & Sons, 1997. URL: https://www.ams.jhu.edu/ers/wp-content/uploads/sites/2/2015/12/fgt.pdf.
  39. Maximilian Schleich, Dan Olteanu, and Radu Ciucanu. Learning Linear Regression Models over Factorized Joins. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD, pages 3-18, 2016. URL: https://doi.org/10.1145/2882903.2882939.
  40. Maximilian Schleich, Dan Olteanu, Mahmoud Abo Khamis, Hung Q. Ngo, and XuanLong Nguyen. A Layered Aggregate Engine for Analytics Workloads. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, pages 1642-1659, 2019. URL: https://doi.org/10.1145/3299869.3324961.
  41. Yaroslav Shitov. An improved bound for the lengths of matrix algebras. Algebra Number Theory, 13(6):1501-1507, 2019. URL: https://doi.org/10.2140/ant.2019.13.1501.
  42. Mario Thüne. Eigenvalues of matrices and graphs. PhD thesis, University of Leipzig, 2012. Google Scholar
  43. Erwin R. van Dam, Willem H. Haemers, and Jack H. Koolen. Cospectral graphs and the generalized adjacency matrix. Linear Algebra and its Applications, 423(1):33-41, 2007. URL: https://doi.org/10.1016/j.laa.2006.07.017.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact