A More Expressive Deterministic Query Language With Efficient Symmetry-Based Choice Construct

. In this paper, symmetry-based choice mechanisms are exploited to compute deterministic queries. We investigate a particular form of these choice mechanisms, called specified symmetry choice. This mechanism is efficient (i.e. computable in polynomial time) and can be added to Fixpoint Logic to give a language that is more powerful than the extension of Fixpoint with Counting. 1 Introduction Non-deterministic mechanisms can sometimes be used to compute more efficiently deterministic queries. Such queries are computed by non-deterministic programs which happen to produce an unique output for each input. This property, called functionality, is crucial if one wants to use non-deterministic programs to compute deterministic queries. Evidently, if this property is checkable, it will be a promising approach to the problem of finding efficient languages, that are more powerful than known deterministic database languages, such as Fixpoint or Fixpoint+Counting. Unfortunately, it was shown that..