Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/30378
Title: | On the Expressive Power of Query Languages for Matrices | Authors: | BRIJDER, Robert GEERTS, Floris VAN DEN BUSSCHE, Jan WEERWAG, Timmy |
Issue Date: | 2019 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | ACM TRANSACTIONS ON DATABASE SYSTEMS, 44 (4) (Art N° 15) | 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 for 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. It is defined such that for each eigenvalue a set of mutually orthogonal eigenvectors is returned that span the eigenspace of that eigenvalue. 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. Finally, the evaluation problem for MATLANG + eigen is shown to be complete for the complexity class ∃R. | Keywords: | Matrix query languages;relational algebra with aggregates;query evaluation problem;graph queries | Document URI: | http://hdl.handle.net/1942/30378 | ISSN: | 0362-5915 | e-ISSN: | 1557-4644 | DOI: | 10.1145/3331445 | ISI #: | WOS:000535714000003 | Rights: | © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. | Category: | A1 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
matlang-crc.pdf | Peer-reviewed author version | 875.03 kB | Adobe PDF | View/Open |
3331445.pdf Restricted Access | Published version | 762.28 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
13
checked on Oct 19, 2024
Page view(s)
60
checked on Sep 7, 2022
Download(s)
52
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.