Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/28196
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | BRIJDER, Robert | - |
dc.contributor.author | GEERTS, Floris | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.contributor.author | WEERWAG, Timmy | - |
dc.date.accessioned | 2019-05-08T12:14:49Z | - |
dc.date.available | 2019-05-08T12:14:49Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Kimelfeld, Benny; Amsterdamer, Yael (Ed.). 21st International Conference on Database Theory (ICDT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, (Art N° 10) | - |
dc.identifier.isbn | 9783959770637 | - |
dc.identifier.issn | 1868-8969 | - |
dc.identifier.uri | http://hdl.handle.net/1942/28196 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | - |
dc.relation.ispartofseries | Leibniz International Proceedings in Informatics (LIPIcs) | - |
dc.rights | © Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag; licensed under Creative Commons License CC-BY | - |
dc.subject.other | matrix query languages; relational algebra with aggregates; query evaluation problem; graph queries | - |
dc.title | On the expressive power of query languages for matrices | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Kimelfeld, Benny | - |
local.bibliographicCitation.authors | Amsterdamer, Yael | - |
local.bibliographicCitation.conferencedate | March 26-29, 2018 | - |
local.bibliographicCitation.conferencename | 21st International Conference on Database Theory (ICDT 2018) | - |
local.bibliographicCitation.conferenceplace | Vienna, Austria | - |
local.bibliographicCitation.jcat | C1 | - |
local.publisher.place | Dagstuhl, Germany | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.relation.ispartofseriesnr | 98 | - |
local.bibliographicCitation.artnr | 10 | - |
dc.identifier.doi | 10.4230/LIPIcs.ICDT.2018.10 | - |
local.bibliographicCitation.btitle | 21st International Conference on Database Theory (ICDT 2018) | - |
item.fulltext | With Fulltext | - |
item.contributor | BRIJDER, Robert | - |
item.contributor | GEERTS, Floris | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.contributor | WEERWAG, Timmy | - |
item.accessRights | Open Access | - |
item.fullcitation | BRIJDER, Robert; GEERTS, Floris; VAN DEN BUSSCHE, Jan & WEERWAG, Timmy (2018) On the expressive power of query languages for matrices. In: Kimelfeld, Benny; Amsterdamer, Yael (Ed.). 21st International Conference on Database Theory (ICDT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, (Art N° 10). | - |
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.