  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.

Logic in Computer Science;Software Engineering