×

On matrices and \(K\)-relations. (English) Zbl 07473199

Summary: 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.

MSC:

68N15 Theory of programming languages
68P15 Database theory
16Y60 Semirings

Software:

LaraDB; MATLANG
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995) · Zbl 0848.68031
[2] 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)
[3] Abo Khamis, M., Ngo, H., Rudra, A., Juggling functions inside a database, SIGMOD Record, 46, 1, 6-13 (2017) · doi:10.1145/3093754.3093757
[4] 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) · Zbl 1489.68071
[5] 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) · Zbl 07266044
[6] 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) · Zbl 07561467
[7] 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)
[8] 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)
[9] 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)
[10] 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)
[11] Libkin, L., Expressive power of SQL, Theor. Comput. Sci., 296, 3, 379-404 (2003) · Zbl 1045.68053 · doi:10.1016/S0304-3975(02)00736-3
[12] 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) · doi:10.1145/3277006.3277013
[13] 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) · Zbl 0754.03042 · doi:10.1007/BF00370681
[14] Marx, M., Venema, Y.: Multi-Dimensional Modal Logic. Springer (1997) · Zbl 0942.03029
[15] Otto, M.: Bounded Variable Logics and Counting: A Study in Finite Models, Lecture Notes in Logic, vol. 9. Springer (1997) · Zbl 0869.03018
[16] 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)
[17] Tarski, A., On the calculus of relations, J. Symb. Log., 6, 73-89 (1941) · JFM 67.0973.02 · doi:10.2307/2268577
[18] Tarski, A., Givant, S.: A Formalization of Set Theory Without Variables, AMS Colloquium Publications, vol. 41. American Mathematical Society (1987) · Zbl 0654.03036
[19] Van den Bussche, J.: FO^3 and the algebra of binary relations. https://databasetheory.org/node/94, Retrieved 22 July 2019
[20] 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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.