On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra

Authors Pablo Barceló , Nelson Higuera, Jorge Pérez, Bernardo Subercaseaux



PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.6.pdf
  • Filesize: 0.67 MB
  • 20 pages

Document Identifiers

Author Details

Pablo Barceló
  • IMC, Pontificia Universidad Católica de Chile, Santiago, Chile
  • IMFD, Santiago, Chile
Nelson Higuera
  • Department of Computer Science, University of Chile, Santiago, Chile
  • IMFD, Santiago, Chile
Jorge Pérez
  • Department of Computer Science, University of Chile, Santiago, Chile
  • IMFD, Santiago, Chile
Bernardo Subercaseaux
  • Department of Computer Science, University of Chile, Santiago, Chile
  • IMFD, Santiago, Chile

Cite As Get BibTex

Pablo Barceló, Nelson Higuera, Jorge Pérez, and Bernardo Subercaseaux. On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICDT.2020.6

Abstract

We study the expressive power of the Lara language - a recently proposed unified model for expressing relational and linear algebra operations - both in terms of traditional database query languages and some analytic tasks often performed in machine learning pipelines. We start by showing Lara to be expressive complete with respect to first-order logic with aggregation. Since Lara is parameterized by a set of user-defined functions which allow to transform values in tables, the exact expressive power of the language depends on how these functions are defined. We distinguish two main cases depending on the level of genericity queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning operations. This language is also local, and thus cannot express operations such as matrix inverse that exhibit a recursive behavior. For expressing convolution, one can relax the genericity requirement by adding an underlying linear order on the domain. This, however, destroys locality and turns the expressive power of the language much more difficult to understand. In particular, although under complexity assumptions the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain.

Subject Classification

ACM Subject Classification
  • Information systems → Query languages
Keywords
  • languages for linear and relational algebra
  • expressive power
  • first order logic with aggregation
  • matrix convolution
  • matrix inverse
  • query genericity
  • locality of queries
  • safety

Metrics

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

References

  1. Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag. On the Expressive Power of Query Languages for Matrices. In ICDT, pages 10:1-10:17, 2018. Google Scholar
  2. Mariano P. Consens and Alberto O. Mendelzon. Low Complexity Aggregation in GraphLog and Datalog. Theor. Comput. Sci., 116(1):95-116, 1993. Google Scholar
  3. Stephen A. Cook. A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control, 64(1-3):2-21, 1985. Google Scholar
  4. Serge Abiteboul et al. Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151). Dagstuhl Manifestos, 7(1):1-29, 2018. Google Scholar
  5. Ronald Fagin, Larry J. Stockmeyer, and Moshe Y. Vardi. On Monadic NP vs. Monadic co-NP. Inf. Comput., 120(1):78-92, 1995. Google Scholar
  6. Floris Geerts. On the Expressive Power of Linear Algebra on Graphs. In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 7:1-7:19, 2019. Google Scholar
  7. Martin Grohe and Thomas Schwentick. Locality of Order-Invariant First-Order Formulas. In MFCS, pages 437-445, 1998. Google Scholar
  8. Stephan Hoyer, Joe Hamman, and xarray developers. xarray Development roadmap, 2018. Available at http://xarray.pydata.org/en/stable/roadmap.html, retrieved on March 2019. URL: http://xarray.pydata.org/en/stable/roadmap.html.
  9. Dylan Hutchison, Bill Howe, and Dan Suciu. Lara: A Key-Value Algebra underlying Arrays and Relations. CoRR, abs/1604.03607, 2016. Google Scholar
  10. Dylan Hutchison, Bill Howe, and Dan Suciu. LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation. In Proceedings of BeyondMR@SIGMOD 2017, pages 2:1-2:10, 2017. Google Scholar
  11. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. Google Scholar
  12. Andreas Kunft, Alexander Alexandrov, Asterios Katsifodimos, and Volker Markl. Bridging the gap: towards optimization across linear and relational algebra. In Proceedings of BeyondMR@SIGMOD 2016, page 1, 2016. Google Scholar
  13. Leonid Libkin. Expressive power of SQL. Theor. Comput. Sci., 296(3):379-404, 2003. Google Scholar
  14. Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. Google Scholar
  15. Alexander M. Rush. Tensor Considered Harmful. Technical report, Harvard NLP Blog, 2019. Available at http://nlp.seas.harvard.edu/NamedTensor, retrieved on March 2019. URL: http://nlp.seas.harvard.edu/NamedTensor.
  16. Alexander M. Rush. Tensor Considered Harmful Pt. 2. Technical report, Harvard NLP Blog, 2019. Available at http://nlp.seas.harvard.edu/NamedTensor2, retrieved on March 2019. URL: http://nlp.seas.harvard.edu/NamedTensor2.
  17. Thomas Schwentick. On Winning Ehrenfeucht Games and Monadic NP. Ann. Pure Appl. Logic, 79(1):61-92, 1996. 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