DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2018.10

On the Expressive Power of Query Languages for Matrices

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

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)

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.

Cite as

Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag. On the Expressive Power of Query Languages for Matrices. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brijder_et_al:LIPIcs.ICDT.2018.10,
  author =	{Brijder, Robert and Geerts, Floris and Van den Bussche, Jan and Weerwag, Timmy},
  title =	{{On the Expressive Power of Query Languages for Matrices}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.10},
  URN =		{urn:nbn:de:0030-drops-86007},
  doi =		{10.4230/LIPIcs.ICDT.2018.10},
  annote =	{Keywords: matrix query languages, relational algebra with aggregates, query evaluation problem, graph queries}
}

Search Results

Documents authored by Weerwag, Timmy

On the Expressive Power of Query Languages for Matrices

Abstract

Cite as

Thanks for your feedback!

Could not send message