Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/28196
Title: | On the expressive power of query languages for matrices | Authors: | BRIJDER, Robert GEERTS, Floris VAN DEN BUSSCHE, Jan WEERWAG, Timmy |
Issue Date: | 2018 | Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | Source: | Kimelfeld, Benny; Amsterdamer, Yael (Ed.). 21st International Conference on Database Theory (ICDT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, (Art N° 10) | Series/Report: | Leibniz International Proceedings in Informatics (LIPIcs) | Series/Report no.: | 98 | 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 Exists R. | Keywords: | matrix query languages; relational algebra with aggregates; query evaluation problem; graph queries | Document URI: | http://hdl.handle.net/1942/28196 | ISBN: | 9783959770637 | DOI: | 10.4230/LIPIcs.ICDT.2018.10 | Rights: | © Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag; licensed under Creative Commons License CC-BY | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-ICDT-2018-10.pdf | Published version | 464.21 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
4
checked on Sep 2, 2020
Page view(s)
84
checked on Sep 7, 2022
Download(s)
110
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.