A Non-Deterministic Multiset Query Language

Article type: Research Article

Authors: Zieliński, Bartosz^{; *}

Affiliations: Department of Computer Science, Faculty of Physics and Applied Informatics, University of Łódź, Pomorska 149/153 90-236 Łódź, Poland. bartosz.zielinski@fis.uni.lodz.pl

Correspondence: [*] Address for correspondence: Department of Computer Science, Faculty of Physics and Applied Informatics, University of Łódź, Pomorska 149/153 90-236 Łódź, Poland.

Abstract: We develop a multiset query and update language executable in a term rewriting system. Its most remarkable feature, besides non-standard approach to quantification and introduction of fresh values, is non-determinism — a query result is not uniquely determined by the database. We argue that this feature is very useful, e.g., in modelling user choices during simulation or reachability analysis of a data-centric business process — the intended application of our work. Query evaluation is implemented by converting the query into a terminating term rewriting system and normalizing the initial term which encapsulates the current database. A normal form encapsulates a query result. We prove that our language can express any relational algebra query. Finally, we present a simple business process specification framework (and an example specification). Both syntax and semantics of our query language is implemented in Maude.

Keywords: term rewriting, query languages, business process modelling

DOI: 10.3233/FI-2021-2095

Journal: Fundamenta Informaticae, vol. 184, no. 2, pp. 141-180, 2021