On the expressiveness of LARA: A proposal for unifying linear and relational algebra

Simple item page
dc.contributor.authorBarcelo, Pablo
dc.contributor.authorHiguera, Nelson
dc.contributor.authorPerez, Jorge
dc.contributor.authorSubercaseaux, Bernardo
dc.date.accessioned2025-01-20T21:01:35Z
dc.date.available2025-01-20T21:01:35Z
dc.date.issued2022
dc.description.abstractWe 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. Since LARA is parameterized by a set of user-defined functions which allow to transform values in tables, known as extension functions, the exact expressive power of the language depends on how these functions are defined. We start by showing LARA to be expressive complete with respect to a syntactic fragment of relational algebra with aggregation (under the mild assumption that extension functions in LARA can cope with traditional relational algebra operations such as selection and renaming). We then look further into the expressiveness of LARA based on different classes of extension functions, and distinguish two main cases depending on the level of genericity that queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning pipelines. 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 some versions of the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain.
dc.fuente.origenWOS
dc.identifier.doi10.1016/j.tcs.2022.09.003
dc.identifier.eissn1879-2294
dc.identifier.issn0304-3975
dc.identifier.urihttps://doi.org/10.1016/j.tcs.2022.09.003
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/92916
dc.identifier.wosidWOS:000869995700006
dc.language.isoen
dc.pagina.final127
dc.pagina.inicio105
dc.revistaTheoretical computer science
dc.rightsacceso restringido
dc.subjectLanguages for linear and relational algebra
dc.subjectExpressive power
dc.subjectRelational algebra with aggregation
dc.subjectQuery genericity
dc.subjectLocality of queries
dc.subjectSafety
dc.titleOn the expressiveness of LARA: A proposal for unifying linear and relational algebra
dc.typeartículo
dc.volumen935
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas