On the expressive power of query languages for matrices

DOI10.4230/LIPICS.ICDT.2018.10zbMATH Open1489.68071arXiv1709.08359OpenAlexW2962762811MaRDI QIDQ3305355FDOQ3305355

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

Publication date: 6 August 2020

Abstract: We investigate the expressive power of $mathsfMATLANG$, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation $mathsfinv$ of inverting a matrix. In $mathsfMATLANG+mathsfinv$ 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 $mathsfeigen$ for diagonalizing a matrix, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. We show that $mathsfinv$ can be expressed in $mathsfMATLANG+mathsfeigen$. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in $mathsfMATLANG+mathsfeigen$ but not in $mathsfMATLANG+mathsfinv$. The evaluation problem for $mathsfMATLANG+mathsfeigen$ is shown to be complete for the complexity class $existsmathbfR$.

Full work available at URL: https://arxiv.org/abs/1709.08359

Recommendations

• On the expressive power of linear algebra on graphs
• The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
• Relative expressive power of navigational querying on graphs using transitive closure
• The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs
• scientific article; zbMATH DE number 219206

zbMATH Keywords

graph queriesmatrix query languagesquery evaluation problemrelational algebra with aggregates

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of some geometric and topological problems
• Undecidability results on two-variable logics
• Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions
• Geometric reasoning with logic and algebra
• Fixed points, Nash equilibria, and the existential theory of the reals
• Title not available (Why is that?)
• A linear algebraic approach to Datalog evaluation
• Logics with aggregate operators
• Fast PageRank Computation via a Sparse Linear System
• Some graphs with characteristic polynomials which are not solvable by radicals
• Expressive power of SQL.
• On the Descriptive Complexity of Linear Algebra
• Linear algebra done right
• Reachability is in DynFO

Cited In (4)

• On the expressive power of linear algebra on graphs
• On the expressive power of message-passing neural networks as global feature map transformers
• On matrices and \(K\)-relations
• On the expressive power of linear algebra on graphs

Uses Software

• APL
• MATLANG
• LaraDB

This page was built for publication: On the expressive power of query languages for matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3305355)