Document Open Access Logo

On the Expressive Power of Query Languages for Matrices

Authors Robert Brijder, Floris Geerts, Jan Van den Bussche, Timmy Weerwag

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2018.10.pdf
  • Filesize: 464 kB
  • 17 pages

Document Identifiers

Author Details

Robert Brijder
Floris Geerts
Jan Van den Bussche
Timmy Weerwag

Cite AsGet BibTex

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 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICDT.2018.10

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 of 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, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. 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. The evaluation problem for MATLANG + eigen is shown to be complete for the complexity class Exists R.
Keywords
  • matrix query languages
  • relational algebra with aggregates
  • query evaluation problem
  • graph queries

Metrics

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

References

  1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  2. D.S. Arnon. Geometric reasoning with logic and algebra. Artificial Intelligence, 37:37-60, 1988. Google Scholar
  3. S. Axler. Linear Algebra Done Right. Springer, third edition, 2015. Google Scholar
  4. S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, second edition, 2008. Google Scholar
  5. M. Boehm, M.W. Dusenberry, D. Eriksson, A.V. Evfimievski, F.M. Manshadi, N. Pansare, B. Reinwald, F.R. Reiss, P. Sen, A.C. Surve, and S. Tatikonda. SystemML: Declarative machine learning on Spark. Proceedings of the VLDB Endowment, 9(13):1425-1436, 2016. Google Scholar
  6. A. Bonato. A Course on the Web Graph, volume 89 of Graduate Studies in Mathematics. American Mathematical Society, 2008. Google Scholar
  7. S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30:107-117, 1998. Google Scholar
  8. L. Chen, A. Kumar, J. Naughton, and J.M. Patel. Towards linear algebra over normalized data. Proceedings of the VLDB Endowment, 10(11):1214-1225, 2017. Google Scholar
  9. S. Datta, R. Kulkarni, A. Mukherjee, T. Schwentick, and T. Zeume. Reachability is in DynFO. In M.M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Proceedings 42nd International Colloquium on Automata, Languages and Programming, Part II, volume 9135 of Lecture Notes in Computer Science, pages 159-170. Springer, 2015. Google Scholar
  10. A. Dawar. On the descriptive complexity of linear algebra. In W. Hodges and R. de Queiroz, editors, Logic, Language, Information and Computation, Proceedings 15th WoLLIC, volume 5110 of Lecture Notes in Computer Science, pages 17-25. Springer, 2008. Google Scholar
  11. A. Dawar, M. Grohe, B. Holm, and B. Laubner. Logics with rank operators. In Proceedings 24th Annual IEEE Symposium on Logic in Computer Science, pages 113-122, 2009. Google Scholar
  12. G.M. Del Corso, A. Gulli, and F. Romani. Fast PageRank computation via a sparse linear system. Internet Mathematics, 2(3):251-273, 2005. Google Scholar
  13. C.D. Godsil. Some graphs with characteristic polynomials which are not solvable by radicals. Journal of Graph Theory, 6:211-214, 1982. Google Scholar
  14. G.H. Golub and C.F. Van Loan. Matrix Computations. The Johns Hopkins University Press, fourth edition, 2013. Google Scholar
  15. E. Grädel, E. Rosen, and M. Otto. Undecidability results on two-variable logics. Archive of Mathematical Logic, 38:313-354, 1999. Google Scholar
  16. D.J. Hand, H. Mannila, and P. Smyth. Principles of Data Mining. MIT Press, 2001. Google Scholar
  17. Lauri Hella, Leonid Libkin, Juha Nurmonen, and Limsoon Wong. Logics with aggregate operators. J. ACM, 48(4):880-907, 2001. URL: http://dx.doi.org/10.1145/502090.502100.
  18. B. Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010. Google Scholar
  19. D. Hutchison, B. Howe, and D. Suciu. LaraDB: A minimalist kernel for linear and relational algebra computation. In F.N. Afrati and J. Sroka, editors, Proceedings 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, pages 2:1-2:10, 2017. Google Scholar
  20. K.E. Iverson. A Programming Language. John Wiley &Sons, Inc., 1962. Google Scholar
  21. Paris C. Kanellakis, Gabriel M. Kuper, and Peter Z. Revesz. Constraint query languages. J. Comput. Syst. Sci., 51(1):26-52, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1051.
  22. M. Kim. TensorDB and Tensor-Relational Model for Efficient Tensor-Relational Operations. PhD thesis, Arizona State University, 2014. Google Scholar
  23. A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. jacm, 29(3):699-717, 1982. Google Scholar
  24. Ph.G. Kolaitis. On the expressive power of logics on finite models. In Finite Model Theory and Its Applications, chapter 2. Springer, 2007. Google Scholar
  25. G. Kuper, L. Libkin, and J. Paredaens, editors. Constraint Databases. Springer, 2000. Google Scholar
  26. B. Laubner. The Structure of Graphs and New Logics for the Characterization of Polynomial Time. PhD thesis, Humboldt-Universität zu Berlin, 2010. Google Scholar
  27. J. Leskovec, A. Rajaraman, and J.D. Ullman. Mining of Massive Datasets. Cambridge University Press, second edition, 2014. Google Scholar
  28. Leonid Libkin. Expressive power of SQL. Theor. Comput. Sci., 296(3):379-404, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(02)00736-3.
  29. H.Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. In-database factorized learning. In J.L. Reutter and D. Srivastava, editors, Proceedings 11th Alberto Mendelzon International Workshop on Foundations of Data Management, volume 1912 of CEUR Workshop Proceedings, 2017. Google Scholar
  30. W. Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen, 2015. Google Scholar
  31. F. Rusu and Y. Cheng. A survey on array storage, query languages, and systems. arXiv:1302.0103, 2013. Google Scholar
  32. T. Sato. Embedding Tarskian semantics in vector spaces. arXiv:1703.03193, 2017. Google Scholar
  33. T. Sato. A linear algebra approach to datalog evaluation. Theory and Practice of Logic Programming, 17(3):244-265, 2017. Google Scholar
  34. M. Schaefer. Complexity of some geometric and topological problems. In D. Eppstein and E.R. Gansner, editors, Graph Drawing, volume 5849 of Lecture Notes in Computer Science, pages 334-344. Springer, 2009. Google Scholar
  35. M. Schaefer and D. Štefankovič. Fixed points, Nash equilibria, and the existential theory of the reals. Theory of Computing Systems, 60(2):172-193, 2017. Google Scholar
  36. M. Schleich, D. Olteanu, and R. Ciucanu. Learning linear regression models over factorized joins. In Proceedings 2016 International Conference on Management of Data, pages 3-18. ACM, 2016. Google Scholar
  37. J. Van den Bussche, D. Van Gucht, and S. Vansummeren. A crash course in database queries. In Proceedings 26th ACM Symposium on Principles of Database Systems, pages 143-154. ACM Press, 2007. Google Scholar
  38. M. Vardi. The complexity of relational query languages. In Proceedings 14th ACM Symposium on the Theory of Computing, pages 137-146, 1982. Google Scholar
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 Imprint Privacy Contact