Abstract
We show that the matrix query language MATLANG corresponds to a natural fragment of the positive relational algebra on K-relations. The fragment is defined by introducing a composition operator and restricting K-relation arities to 2. We then proceed to show that MATLANG can express all matrix queries expressible in the positive relational algebra on K-relations, when intermediate arities are restricted to 3. Thus we offer an analogue, in a model with numerical data, to the situation in classical logic, where the algebra of binary relations is equivalent to first-order logic with three variables.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995)
Abo Khamis, M., Ngo, H., Rudra, A.: FAQ: Questions asked frequently. In: Milo, T., Tan, W. (eds.) Proceedings 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Databases, pp. 13–28, San Francisco (2016)
Abo Khamis, M., Ngo, H., Rudra, A.: Juggling functions inside a database. SIGMOD Record 46(1), 6–13 (2017)
Brijder, R., Geerts, F., Van den Bussche, J., Weerwag, T.: On the expressive power of query languages for matrices. In: Kimelfeld, B., Amsterdamer, Y. (eds.) Proceedings 21st International Conference on Database Theory, LIPIcs vol. 98, pp. 10:1–10:17, Vienna. Schloss Dagstuhl-Leibniz Center for Informatics (2018)
Brijder, R., Gyssens, M., Van den Bussche, J.: On matrices and K-relations. In: Herzig, A., Kontinen, J. (eds.) Proceedings 11th International Symposium on Foundations of Information and Knowledge Systems, Lecture Notes in Computer Science, vol. 12012, pp. 42–57. Dortmund, Springer (2020)
Geerts, F.: On the expressive power of linear algebra on graphs. In: Barcelo, P., Calautti, M. (eds.) Proceedings 22nd International Conference on Database Theory, LIPIcs vol. 127, pp. 7:1–7:19, Lisbon. Schloss Dagstuhl–Leibniz Center for Informatics (2019)
Green, T., Karvounarakis, G., Tannen, V.: Provenance semirings. In: Libkin, L. (ed.) Proceedings 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp 31–40, Beijing (2007)
Hutchison, D., Howe, B., Suciu, D.: LaraDB: A minimalist kernel for linear and relational algebra computation. In: Afrati, F., Sroka, J. (eds.) Proceedings 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, pp 2:1–2:10 (2017)
Jananthan, H., Zhou, Z., Gadepally, V., Hutchison, D., Kim, S., Kepner, J.: Polystore mathematics of relational algebra. In: Nie, J.Y., Obradovic, Z., Suzumura, T., Ghosh, R., Nambiar, R., Wang, C., Zang, H., Baeza-Yates, R., Hu, X., Kepner, J., Cuzzocrea, A., Tang, J., Toyoda, M. (eds.) Proceedings 2017 IEEE International Conference on Big Data, pp. 3180–3189, Boston (2017)
Joglekar, M., Puttagunta, R., Ré, C.: AJAR: Aggregations and joins over annotated relations. In: Milo, T., Tan, W. (eds.) Proceedings 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Databases, pp. 91–106, San Francisco (2016)
Libkin, L.: Expressive power of SQL. Theor. Comput. Sci. 296(3), 379–404 (2003)
Luo, S., Gao, Z., Gubanov, M., Perez, L., Jermaine, C.: Scalable linear algebra on a relational database system. SIGMOD Record 47(1), 24–31 (2018)
Maddux, R.: The origin of relation algebras in the development and axiomatization of the calculus of relations. Stud. Log. 50(3/4), 421–455 (1991)
Marx, M., Venema, Y.: Multi-Dimensional Modal Logic. Springer (1997)
Otto, M.: Bounded Variable Logics and Counting: A Study in Finite Models, Lecture Notes in Logic, vol. 9. Springer (1997)
Pratt, V.: Origins of the calculus of binary relations. In: Proceedings 7th Annual IEEE Symposium on Logic in Computer Science, pp 248–254, Santa Cruz (1992)
Tarski, A.: On the calculus of relations. J. Symb. Log. 6, 73–89 (1941)
Tarski, A., Givant, S.: A Formalization of Set Theory Without Variables, AMS Colloquium Publications, vol. 41. American Mathematical Society (1987)
Van den Bussche, J.: FO3 and the algebra of binary relations. https://databasetheory.org/node/94, Retrieved 22 July 2019
Yan, Z., Tannen, V., Ives, Z.: Fine-grained provenance for linear algebra operators. In: Boulakia, S.C. (ed.) 8Th USENIX Workshop on the Theory and Practice of Provenance, Washington (2016)
Acknowledgements
We thank Floris Geerts for inspiring discussions.
We also thank the anonymous reviewers for their comments which were very helpful in improving this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This is a revised and extended version of the conference paper “On matrices and K-relations” presented at the 11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2020), Dortmund, Germany, February 17–21, 2020 [5].
Robert Brijder has done this work as a Postdoctoral Fellow of the Research Foundation – Flanders (FWO).
Rights and permissions
About this article
Cite this article
Brijder, R., Gyssens, M. & Van den Bussche, J. On matrices and K-relations. Ann Math Artif Intell 90, 181–210 (2022). https://doi.org/10.1007/s10472-021-09760-4
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-021-09760-4