Publication
Title
On the expressive power of query languages for matrices
Author
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 9R.
Language
English
Source (journal)
LIPIcs : Leibniz International Proceedings in Informatics. - Place of publication unknown
Source (book)
21st International Conference on Database Theory (ICDT 2018) / Kimelfeld, Benny [edit.]; et al.
Publication
Germany : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , 2018
ISSN
1868-8969
ISBN
978-3-95977-063-7
DOI
10.4230/LIPICS.ICDT.2018.10
Volume/pages
98 (2018) , p. 10:1-10:17
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Record
Identifier
Creation 06.12.2018
Last edited 17.06.2024
To cite this reference