A Non-Deterministic Multiset Query Language

We develop a multiset query and update language executable in a termrewriting system. Its most remarkable feature, besides non-standard approach toquantification and introduction of fresh values, is non-determinism - a queryresult is not uniquely determined by the database. We argue that this featureis very useful, e.g., in modelling user choices during simulation orreachability analysis of a data-centric business process - the intendedapplication of our work. Query evaluation is implemented by converting thequery into a terminating term rewriting system and normalizing the initial termwhich encapsulates the current database. A normal form encapsulates a queryresult. We prove that our language can express any relational algebra query.Finally, we present a simple business process specification framework (and anexample specification). Both syntax and semantics of our query language isimplemented in Maude.Comment: 40 pages, version edited by Fundamenta Informatica