On the expressive power of query languages for matrices

DOI10.4230/LIPICS.ICDT.2018.10MaRDI QIDQ3305355zbMATH OpenOpenAlexFDO

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

Publication date 6 August 2020

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

zbMATH Keywords

graph queriesmatrix query languagesquery evaluation problemrelational algebra with aggregates

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(4)

• On the expressive power of linear algebra on graphs
• 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

Describes a project that uses

Uses Software

• LaraDB
• MATLANG
• APL

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)