QUERY LANGUAGES FOR SEMI-ALGEBRAIC DATABASES BASED ON DESCRIPTIVE COMPLEXITY OVER ℝ

KLAUS MEER

Abstract. We propose the study of query languages for databases involving real numbers as data (called semi-algebraic databases in the sequel). As main new aspect our approach is based on real number complexity theory as introduced in [8] and descriptive complexity for the latter developed in [17]. Using this formal framework a uniform treatment of semi-algebraic query languages is obtained. Precise results about both the data- and the expressioncomplexity of several such query languages are proved. More explicitly, relying on descriptive complexity theory over ℝ gives the possibility to derive a hierarchy of complete languages for most of the important real number complexity classes. A clear correspondence between different logics and such complexity classes is established. In particular, it is possible to formalize queries involving in a uniform manner real spaces of different dimensions. This can be done in such a way that the logical description exactly reflects the computational complexity of a query. The latter might circumvent a problem appearing in some of the former approaches dealing with semi-algebraic databases (see [20] , [18]), where the use of first-order logic over real-closed fields can imply inefficiency as soon as the dimension of the underlying real space is not fixed - no matter whether the query under consideration is easy to compute or not.

1. Introduction

Semi-algebraic databases have raised increasing interest in recent years. Inspired by problems of computational and semi-algebraic geometry in the meanwhile there can be found many approaches dealing with real number data and real polynomial inequality constraints. To give a (by no means complete) list of references consider for example [20], [24], [19], [4], [5], [6], the survey paper [18] as well as the literature cited in there.

An important task in database theory is to study the complexity of queries asked to databases. In relation with finite model theory and descriptive complexity theory this led to numerous results on the complexity of several query languages described by logical means (see [1] for a survey). For the present work the papers [9] and [25] are of extreme interest. Here the notions of data- and expression-complexity were introduced and studied; important complexity classes in the Turing model were captured by the data- resp. expression-complexity of several such query languages. Our goal is to set up a similar theory for semialgebraic databases. However, in order to deal in a comparable manner with data- and expression-complexity also in connection with real number data problems arise. It seems not to be clear how to treat them appropriately as long as restricting to the so far used concepts. Thus, before starting with the mathematical reasoning let us consider an elementary example from computational geometry and explain some of these problems.

Example 1.1. Given n points in ℝ^{2} as database the task is to select those pairs that have the largest euclidean distance. Following the approach taken in the seminal paper [20] (and many others as well, for example [5],[14],[19],[24]) this problem would be modeled as follows: the database is a finite relation ℜ ⊂ ℝ^{2} consisting of the n points. It is given as a quantifier free first-order formula over the reals having two free variables (and the formula is true exactly for the points in the database). Now in order to check whether a pair (x, y) of points realizes the largest distance with respect to pairs in ℜ^{2} analyze the following firstorder formula over the reals with the additional symbol ℜ in the vocabulary (here x = (x_{1}, x_{2}) etc.):

\begin{matrix}ψ(x_{1}, x_{2}, y_{1}, y_{2}) ≡ ℜ(x_{1}, x_{2}) ∧ ℜ(y_{1}, y_{2}) ⋀ \{∀v_{1}, v_{2}, w_{1}, w_{2} ∈ ℝ \\ (ℜ(v_{1}, v_{2}) ∧ ℜ(w_{1}, w_{2})) ⇒ (x_{1} − y_{1})^{2} + (x_{2} − y_{2})^{2} ≥ (v_{1} − w_{1})^{2} + (v_{2} − w_{2})^{2}\} \end{matrix}

First of all the above problem is a real number problem; that is the point coordinates are real numbers and the complexity of the problem is depending on the quantity n of different points. Thus it is a problem perfectly suited to deal with in a corresponding model of computation. Such a model was introduced by Blum, Shub, and Smale (shortly: BSS) [8] and will be the starting point of our investigations. Second (and more important) consider the logical structure of ψ : the query is presented as a quantified first-order formula over the real closed field ℝ. In general, the complexity of evaluating such formulas is supposed to be tremendous since it results in quantifier elimination. In the BSS setting deciding existential first-order formulas with polynomials involved having at most degree 2 is already NP_{ℝ}-complete over ℝ ([8]). Hence the logical shape of the above query does not reflect its complexity. Though the query is easy to compute it is expressed by a (quantified) first-order formula. In [20] this problem is circumvented by considering only databases represented by relations in a fixed space ℝ^{k}. Thus if a query on such a database is analyzed a constant bound on the quantifier depth is obtained. In such a situation the corresponding (constantly many) quantifiers can be eliminated efficiently and tractability results on the data complexity of such a query are obtained (in fact, this complexity is in NC). However, one may argue that there is no necessity to consider the above largest distance problem only in ℝ^{2}. It makes perfect sense to regard it as a single geometrical problem being posed for sets in any ℝ^{k} and, in fact, computationally is not harder there (of course the complexity will depend on the number of points and the varying dimension k). Similarly, when analyzing the complexity of query languages over finite structures data-complexity is measured by fixing a query and evaluating it on different databases, where the latter are given as finite structures \underline{of different sizes} (see [25]). In the above formulation considering the dimension k as part of the input would cause serious troubles since then the complexity of quantifier elimination enters into the consideration though the query itself remains tractable. The above problem also sheds light on a further one; the quantifiers for v_{i} and w_{i} in a particular sense are “easy” since they only range over components of points in ℜ. In some of the approaches to real number databases such a difference is present when distinguishing between so-called natural and active domains (see [5],[6] as example). Here, very interesting work has been done to analyze when it is possible to replace the natural domain of a quantifier by the active one. However, even if it is possible to perform such a replacement this process once more can involve quantifier elimination and thus might destroy a possibly easy shape of a quantifier.

In the present paper we propose the use of descriptive complexity theory over the reals - as introduced in [17] - to study the complexity of query languages for semi-algebraic databases. It allows to set up precise relations between different such languages and real number complexity classes in the sense of [8]. Using meta-finite model theory [16] in a specific sense also separates “easy” from “difficult” quantifiers by allowing an exact distinction between discrete and continuous aspects of computations resp. queries. As a consequence formulas involving quantifiers which intrinsically range over an infinite domain will belong to a different logic than those incorporating bounded ones. For example the results show the (generalized) largest distance query to be describable by a firstorder fixed-point formula on so-called ℝ-structures; such formulas only involve bounded quantifiers, thereby directly implying the largest distance problem to be computable in polynomial time (over ℝ).

Parallelizing the foregoing in [25] the notions of data- and expression-complexity for semi-algebraic query languages are introduced. For the main logics on (ordered) ℝ-structures we study these quantities and give completeness results. In section 2 we recall the basics on the BSS model of computation over ℝ and on descriptive complexity theory for it. In Section 3 the notions of a semi-algebraic query, data- and expression-complexity and -completeness for a query language are introduced. Completeness results are proved in section 4.

2. Basic concepts: Complexity and descriptive complexity over ℝ

2.1. BSS complexity theory over the reals. We start this section by summarizing very briefly the main ideas of real number complexity theory. For a more intensive presentation see [8],[7], and also [22] for a survey on current results in this area.

Essentially a (real) Blum-Shub-Smale (shortly: BSS) machine can be considered as a Random Access Machine over ℝ which is able to perform the basic arithmetic operations at unit cost and which registers can hold arbitrary real numbers.

Definition 2.1 ([8]). a) Let Y ⊂ ℝ^{∞} := ⨁_{k∈ℕ} ℝ^{k}, i.e. the set of finite sequences of real numbers. A BSS-machine M over ℝ with admissible input set Y is given by a finite set I of instructions labelled by 1, …, N. A configuration of M is a quadruple (n, i, j, x) ∈ I ×ℕ×ℕ×ℝ^{∞} . Here n denotes the currently executed instruction, i and j are used as addresses (copy-registers) and x is the actual content of the registers of M. The initial configuration of M′s computation on input y ∈ Y is (1, 1, 1, y) . If n = N and the actual configuration is (N, i, j, x), the computation stops with output x . The instructions M is allowed to perform are of the following types : computation: : n : x_{s} ← x_{k} ∘_{n} x_{l}, where ∘_{n} ∈ {+, −, ∗,:} or

n : x_{s} ← α for some constant α ∈ ℝ .

The register x_{s} will get the value x_{k} ∘_{n} x_{l} or α resp. All other registerentries remain unchanged. The next instruction will be n + 1; moreover, the copy-register i is either incremented by one, replaced by 0, or remains unchanged. The same holds for copy-register j.

branch: : n: if x_{0} ≥ 0 goto β(n) else goto n + 1. According to the answer of the test the next instruction is determined (where β(n) ∈ I). All other registers are not changed.

copy: : n : x_{i} ← x_{j}, i.e. the content of the “read”-register is copied into the “write”-register. The next instruction is n + 1; all other registers remain unchanged.

b) The size of an x ∈ ℝ^{k} is size_{ℝ}(x) := k. The cost of any of the above operations is 1. The cost of a computation is the number of operations performed until the machine halts.

c) For some B ⊂ ℝ^{∞} we call a function f : B → ℝ^{∞} (BSS-) computable iff it is realized by a BSS machine over admissible input set B. Similarly, a set A ⊂ B ⊂ ℝ^{∞} is decidable in B iff its characteristic function is computable. (B, A) is called a decision problem.

Most of the well known boolean time-complexity classes can now be defined analogously over the reals. We here give precise definitions of three such classes and mention the others being important later on briefly.

Definition 2.2. i) A problem (B, A), A ⊂ B ⊂ ℝ^{∞} is in class P_{ℝ} (decidable in deterministic polynomial time), iff there exist a polynomial p and a (deterministic) BSS machine M deciding A (in B) such that T_{M}(y) ≤ p(size_{ℝ}(y)) ∀y ∈ B.

ii) (B, A) is in NP_{ℝ} (verifiable in non-deterministic polynomial time over ℝ) iff there exist a polynomial p and a BSS machine M working on input space B × ℝ^{∞} such that

a) Φ_{M}(y, z) ∈ {0, 1} ∀y ∈ B, z ∈ ℝ^{∞}

b) Φ_{M}(y, z) = 1 ⟹ y ∈ A

c) ∀y ∈ A ∃z ∈ ℝ^{∞} Φ_{M}(y, z) = 1 and T_{M}(y, z) ≤ p(size_{ℝ}(y)) iii) (B, A) is in DNP_{ℝ} (digital NP_{ℝ}) iff (B, A) ∈ NP_{ℝ} but the guess space is

reduced to be {0, 1}^{∞}.

It is obvious how to define further classes such as EXP_{ℝ}, NEXP_{ℝ}, DNEXP_{ℝ}. We will need as well some other classes which are defined similarly as their boolean counterparts. Among them are the real polynomial hierarchy PH_{ℝ} [10], the class PAT_{ℝ} of problems accepted in polynomial alternating time [10] and its digital counterpart DPAT_{ℝ} [11]; a set S ⊂ ℝ^{∞} is in class PAT_{ℝ} (resp. DPAT_{ℝ}) iff there exist a polynomial p and a BSS machine M such that

S = {x ∈ ℝ^{∞}|∀y_{1}∃z_{1} … ∀y_{p(|x|)}∃z_{p(|x|)} M accepts (x, y, z) in time p(|x|)}.

Here for PAT_{ℝ} the y_{i}, z_{i} range over ℝ whereas for DPAT_{ℝ} they range over {0, 1}.

Note that over the reals space resources alone do not provide meaningful complexity classes. Following [23] all decidable real number problems can be solved using a constant number of working registers. However, combining time and space resources makes sense [17]. We especially deal with the classes (P_{ℝ}, const) and (EXP_{ℝ}, const) resp. denoting those problems being decidable by a BSS machine working simultaneously both in polynomial (resp. exponential) time and constant space.

Finally, reducibility in complexity classes is defined as usual. For example, a NP_{ℝ}-complete problem w.r.t. polynomial time reductions is given by 4-F EAS (see [8]): given a (multivariate) polynomial f with real coefficients, deg(f) ≤ 4, does there exist a real zero of f?

Here we are mainly concerned with reductions in (P_{ℝ}, const). Our results support the suggestion in [17] to consider this class as a real counterpart of logspace.

2.2. Descriptive complexity for real number computations. Next we turn to the basic ideas of descriptive complexity over the reals and recall the notions of ℝ-structures and logics for them. This concept was first introduced in [17]; we refer to this paper as well as [12], [7] for a closer study of descriptive complexity in the BSS model.

We suppose the reader familiar with the main terminology of logic as well as with the concepts of vocabulary, first-order formula or sentence, interpretation and structure (see for example [15]).

Definition 2.3. Let L_{s}, L_{f} be finite vocabularies where L_{s} may contain relation and function symbols, and L_{f} contains function symbols only. A ℝ-structure of signature σ = (L_{s}, L_{f}) is a pair 𝔇 = (𝔄, 𝔉) consisting of

i) a finite structure 𝔄 of vocabulary L_{s}, called the skeleton of 𝔇, whose universe A will also be said to be the universe of 𝔇, and

ii) a finite set 𝔉 of functions X : A^{k} → ℝ interpreting the function symbols in L_{f}.

Definition 2.4. Let 𝔇 be a ℝ-structure with skeleton 𝔄. We denote by |A| and also by |𝔇| resp. the cardinality of the universe A of 𝔄. This number is called the size of the structure 𝔇. A ℝ-structure 𝔇 = (𝔄, 𝔉) is ranked if there is a unary function symbol r ∈ L_{f} whose interpretation ρ in 𝔉 bijects A with {0, 1, …, |A| − 1}. The function ρ is called ranking. We will write i < j for i, j ∈ A iff ρ(i) < ρ(j). A k-ranking on A is a bijection between A^{k} and {0, 1, …, |A|^{k} − 1}. It can easily be defined if a ranking is available. We denote by ρ^{k} the interpretation of the k-ranking induced by ρ.

Throughout this paper we suppose all ℝ-structures to be ranked (but see Remark 3.2 ). We therefore notationally suppress the symbol ≤ in the sets 𝔉 considered. The basic logic important for our work is first-order logic which we are going to define now.

Fix a countable set V = {v_{0}, v_{1}, …, } of variables. These variables range only over the skeleton; we do not use element variables taking values in ℝ. This is the reason why we will be able to obtain a finer distinction of queries than just dealing with first-order logic over real closed fields.

Definition 2.5. The language FO_{ℝ} contains, for each signature σ = (L_{s}, L_{f}) a set of formulas and terms. Each term t takes, when interpreted in some ℝstructure, values in either the skeleton, in which case we call it an index term, or in ℝ, in which case we call it a number term. Terms are defined inductively as follows

i) The set of index terms is the closure of the set V of variables under applications of function symbols of L_{s}.

ii) Any real number is a number term. iii) If h_{1}, …, h_{k} are index terms and X is a k-ary function symbol of L_{f} then

X(h_{1}, …, h_{k}) is a number term. iv) If t, t′ are number terms, then so are t + t′, t − t′, t × t′, t/t′ and sign(t).

Atomic formulas are equalities h_{1} = h_{2} of index terms, equalities t_{1} = t_{2} and inequalities t_{1} < t_{2} of number terms, and expressions P (h_{1}, …, h_{k}) where P is a k-ary predicate symbol in L_{s} and h_{1}, …, h_{k} are index terms.

The set of formulas of FO_{ℝ} is the smallest set containing all atomic formulas and which is closed under Boolean connectives and quantification (∃v)ψ and (∀v)ψ. Note that we do not consider formulas (∃x)ψ where x ranges over ℝ.

Example 2.6 (cf. [17]). Let L_{s} be the empty set and L_{f} be {r, X} where both function symbols have arity 1. Then, a simple class of ranked ℝ-structures with signature (L_{s}, L_{f}) is obtained by letting 𝔄 be a finite set A, r^{𝔇} any ranking on A and X^{𝔇} any unary function X^{𝔇} : A → ℝ. Since r^{𝔇} bijects A with {0, 1, …, n − 1} where n = |A|, this ℝ-structure is a point x_{𝔇} in ℝ^{∞}. Conversely, for each point x ∈ ℝ^{∞} there is an ℝ-structure 𝔇 such that x = x_{𝔇}. Thus, this class of structures models ℝ^{∞}.

On the other hand any ℝ-structure 𝔇 = (𝔄, 𝔉) can be identified with a vector e(𝔇) ∈ ℝ^{∞} using a natural encoding. To this aim choose a ranking on A. Without loss of generality the skeleton of 𝔇 can be assumed to consist of the plain set A only by replacing all functions and relations in L_{s} by their corresponding characteristic functions —the latter being considered as elements of the set 𝔉. Now using the ranking each of the functions X in 𝔉 can be represented by a vector v_{X} ∈ ℝ^{m} for some appropriate m. The concatenation of all these v_{X} yields the encoding e(𝔇) ∈ ℝ^{∞}. Note that the length of e(𝔇) is polynomially bounded in |A|; moreover for all ℝ-structures 𝔇, all rankings E on A and all functions X : A^{k} → ℝ the property that X represents the encoding e(𝔇) of 𝔇 with respect to E is first-order expressible (see [17]).

Example 2.6 allows us to speak about complexity classes among ℝ-structures. If S is a set of ℝ-structures closed under isomorphisms, we say that S belongs to a complexity class ℭ over the reals if the set {e(𝔇) | 𝔇 ∈ S} belongs to ℭ.

In order to describe different complexity classes by logical means we are going to define some further logics on ℝ-structures.

Definition 2.7. [[17],[12]] a) By F O_{ℝ}^{−} we denote the quantifier-free fragment of F O_{ℝ} logic.

b) We say that ψ is a second-order formula (of signature σ = (L_{s}, L_{f})) with free variables a ranging in some A^{s} if ψ(a) = Q_{1}Y_{1} … Q_{r}Y_{r}φ(a); here φ is a first-order formula in FO_{ℝ} of signature (L_{s}, L_{f} ∪ {Y_{1}, …, Y_{r}}) and Q_{i} ∈ {∃, ∀}. The symbols Y_{1}, …, Y_{r} will be called function variables. For a specific assignment ā the sentence ψ(ā) is true in a ℝ-structure 𝔇 of signature σ when there exist interpretations of Y_{1}, …, Y_{r} such that φ(ā) holds true on 𝔇. The set of second-order formulas will be denoted by SO_{ℝ}. Together with the interpretation above it constitutes second-order logic.

c) If in b) quantifiers of function variables are restricted to be existential we obtain existential second-order logic, denoted by ∃SO_{ℝ}.

d) If in an existential second-order formula all quantified function variables are supposed to have an image in {0, 1} we get existential digital second-order logic ∃DSO_{ℝ}.

Finally, we need to introduce fixed point logic for ℝ-structures. This is done by combining a maximization with a fixed-point rule.

Let F (s, t̄) be a number term with free variables s and t̄ = (t_{1}, …, t_{r}). Then max_{s} F (s, t̄) is also a number term with free variables t̄. Its interpretation in any ℝ-structure 𝔇 and for any point u ∈ A^{r} interpreting t̄ is the maximum of F^{𝔇}(a, u) where a ranges over A.

Next, fix a signature σ = (L_{s}, L_{f}), an integer r ≥ 1, and a pair (Z, D) of function symbols both of arity r and not contained in this signature. Let F (Z, t̄) and H(D, t̄) be number terms of signature (L_{s}, L_{f} ∪ {Z, D}) and free variables t̄= (t_{1}, …, t_{r}). Note that Z can appear several times in F and we do not require that its arguments are t_{1}, …, t_{r}. The only restriction is that the number of free variables in F coincides with the arity of Z. A similar remark holds for H and D.

For any ℝ-structure 𝔇 of signature σ and any interpretation ζ : A^{r} → ℝ of Z and Δ : A^{r} → ℝ of D respectively the number terms F (Z, t̄) and H(D, t̄) define functions

F_{ζ}^{𝔇}, H_{Δ}^{𝔇} : A^{r} → ℝ.

Let us consider the sequence of pairs {Δ^{i}, ζ^{i}}_{i≥0} with ζ^{i} : A^{r} → ℝ and Δ^{i} : A^{r} → ℝ inductively defined by

Δ^{0}(x) = 0  for all x ∈ A^{r}
ζ^{0}(x) = 0  for all x ∈ A^{r}
Δ^{i+1}(x) = \{ \begin{matrix}H_{Δ^{i}}^{𝔇}(x) & if Δ^{i}(x) = 0 \\ Δ^{i}(x) & otherwise \end{matrix}

ζ^{i+1}(x) = \{ \begin{matrix}F_{ζ^{i}}^{𝔇}(x) & if Δ^{i}(x) = 0 \\ ζ^{i}(x) & otherwise. \end{matrix}

Since Δ^{i+1}(x) only differs from Δ^{i}(x) in case the latter is zero, one has that Δ^{j} = Δ^{j+1} for some j < |A|^{r}. In this case, moreover, we also have that ζ^{j} = ζ^{j+1}. We denote these fixed points by Z^{∞} and D^{∞} and call them the fixed points of F (Z, t̄) and H(D, t̄) on 𝔇. We say that F^{𝔇} updates ζ.

Note that D plays the role of the characteristic function for the domain of Z and the different Δ^{i} determine the successive updatings of this domain. We say that Z^{∞} is defined on x if D^{∞}(x) ≠ 0.

The fixed point rule is now stated in the following way. If F (Z, t̄) and H(D, t̄) are number terms as above then

fp[Z(t̄) ← F (Z, t̄), H(D, t̄)](ū)

and

fp[D(t̄) ← H(D, t̄)](ū)

are number terms of signature (L_{s}, L_{f}). Their interpretations on a given ℝstructure 𝔇 are Z^{∞}(ū) and D^{∞}(ū) respectively.

Definition 2.8. Fixed point logic for ℝ-structures, denoted by FP_{ℝ}, is obtained by augmenting first-order logic FO_{ℝ} with the maximization rule and the fixed point rule.

The main results in [17] and [12] show that the logics introduced above are closely related to real number complexity classes in the following sense:

Theorem 2.9 ([17],[12]). Let (F, F^{+}) be a decision problem of (ranked) ℝ-struc-tures as explained in Example 2.6. Then (F, F^{+}) belongs to complexity class ℭ if and only if there exists an formula ψ in language 𝔏 such that F^{+} = {𝔇 ∈ F |𝔇 ⊧ ψ}. Here for ℭ and 𝔏 one can substitute one of the pairs (P_{ℝ}, FP_{ℝ}), (DNP_{ℝ}, ∃DSO_{ℝ}), (NP_{ℝ}, ∃SO_{ℝ}), and (PH_{ℝ}, SO_{ℝ}).

3. Semi-algebraic databases and queries; data- and expression complexity

Once having introduced descriptive complexity over ℝ it is straightforward how to base the notion of semi-algebraic databases and semi-algebraic queries on it. We closely follow the approaches in [9],[25],[1] by performing the changes necessary when working over the reals.

Definition 3.1. Fix a signature σ = (L_{s}, L_{f}) of finite vocabularies L_{s} and L_{f} where L_{s} may contain relation and function symbols and L_{f} contains function symbols only.

a) A semi-algebraic database of type σ is a (ranked) ℝ-structure 𝔇 = (𝔄, 𝔉) of signature σ.

b) Fix a natural number k. A semi-algebraic query Q of type (σ, k) is a partial map assigning (if defined) to every semi-algebraic database 𝔇 of type σ a relation of arity k defined on the finite universe of 𝔇.

c) A semi-algebraic query is computable if it is BSS-computable with respect to the usual encoding of ℝ-structures as inputs for BSS machines [17].

Remark 3.2. a) Semi-algebraic queries could be defined more generally by mapping 𝔇 to another database of (possibly) different signature. The expositions in [1] and in [25] for such a restriction mutis mutandis in our setting hold as well.

b) Just as in descriptive complexity theory over finite structures the problem of genericity in our setting appears as well (see [17]). In principle one can think about similar ways to deal with it in connection with ℝ-structures such as defining generic queries (cf. [1]) or extending the definition of special devices such as “generic machines” [2] or reflectional relational machines [3] to the BSS model. Since we want to focus on outlining our approach for semi-algebraic databases throughout this paper we assume all ℝ-structures to be ranked.

In this paper we are considering semi-algebraic query languages arising from different logics on ℝ-structures. Given a formula ρ(a_{1}, …, a_{s}) in a particular logic for ℝ-structures of signature σ and with free variables a_{1}, …, a_{s} ranging over the finite universe, the corresponding query Q_{ρ} is defined by assigning to an ℝ-structure 𝔇 of signature σ that relation of arity s determined by all assignments for the a_{i} making ρ a true sentence in 𝔇.

Definition 3.3 (cf. [25]). a) Given a semi-algebraic query Q_{ρ} of signature (σ, k) and corresponding to a formula ρ in the above sense its graph is the set Gr(Q_{ρ}) := {(a, 𝔇)|a ∈ A^{k}, 𝔇 ⊧ ρ(a)}. b) Given a semi-algebraic database 𝔇 of signature σ its graph with respect to

a language L is the set Gr_{L}(𝔇) := {(a, ρ)|ρ is a formula in L of arity s, a ∈ A^{s}, 𝔇 ⊧ ρ(a)}.

We are interested in the BSS complexity of deciding membership in one of the two graph sets defined above. This means either the language is fixed and we measure the complexity for varying semi-algebraic databases as function in the size of the database; or vice versa the database is fixed and the complexity for varying formulas in a given language is studied as function in the formula length. In the following the notion of completeness of particular languages refers to reduction algorithms running simultaneously in polynomial real time and constant space. Our results substantiate that the according class (P_{ℝ}, const) can be seen as an analogue of logspace in the BSS setting.

Definition 3.4 (cf. [25]). a) The data-complexity of a language L for semialgebraic databases is the BSS complexity of deciding membership of (a, 𝔇) in Gr(Q_{ρ}) for any fixed ρ ∈ L. A language L is data-complete for a real number complexity class ℭ if ∀ρ ∈ L deciding membership in Gr(Q_{ρ}) is in ℭ and furthermore there exists a ρ_{0} ∈ L such that the latter problem for the graph Gr(Q_{ρ_{0}}) is complete in ℭ with respect to reductions in (P_{ℝ}, const).

b) The expression-complexity of a language L for semi-algebraic databases is the BSS complexity of deciding membership of (a, ρ) in Gr_{L}(𝔇) for any fixed ℝ-structure 𝔇 and ρ ∈ L is a formula over the corresponding signature. A language L is expression-complete for a real number complexity class ℭ if for any fixed semi-algebraic database 𝔇 the graph membership problem is in ℭ and furthermore there exists a semi-algebraic database 𝔇_{0} such that the latter problem with respect to 𝔇_{0} is complete in ℭ under reductions in (P_{ℝ}, const). Here complexity is measured in the length of a given formula ρ. The latter intuitively is the number of symbols necessary to write down ρ, where quantifiers, symbols from the signature, logical and real arithmetic operation symbols and - most important - real numbers are supposed to have unit size. We skip a formal definition which is easily done by induction.

In the following we will notationally identify a language for semi-algebraic databases and the semi-algebraic queries resulting from it.

4. Completeness results

For most of the logics introduced in [17] and [12] completeness results for both data- and expression-complexity are shown now. The results especially settle a precise correspondence between the logical structure of a semi-algebraic query and its complexity. This removes the difficulties arising when formalizing easy queries already with first order logic for real closed fields.

Theorem 4.1. The language FO_{ℝ}^{−} of first order logic without quantifiers is both data-complete and expression-complete in (P_{ℝ}, const).

Proof. Since we consider reductions in class (P_{ℝ}, const) for both statements it suffices to show membership of the corresponding graph problem in (P_{ℝ}, const). Let a formula ρ ∈ FO_{ℝ}^{−} with s free variables be fixed. Consider a semi-algebraic database 𝔇 = (𝔄, F) of size n and an a ∈ A^{s} as input. Evaluating ρ in a can be done in a number of steps proportional to the length of ρ, which is independent of n. Hence there exists a BSS algorithm working in polynomial (even constant) time and constant space.

Now let the semi-algebraic database be fixed and consider as input an a ∈ A^{s} together with ρ ∈ FO_{ℝ}^{−} of length n. In order to evaluate ρ in a we can proceed as in [21] for evaluating Boolean expressions. However, the corresponding algorithm has to be performed simultaneously in polynomial time and constant space. (Note that Michaux’ result [23] guarantees this task to be executable in constant space, but his algorithm in general might result in a super-polynomial slow-down). Nevertheless, a closer analysis of Lynch’s method shows that in this particular situation Michaux’ foregoing will not result in a slow-down: The basic ingredient of Lynch’s method is the organization of how to cycle through the sub-formulas of ρ. To this aim in the Turing model at most O(log n) many columns are introduced to record specific sub-results (i.e. values in {0, 1}) and to indicate which part is going to be evaluated next. Hence, we get at most O(log n) integers of bounded value (independently of n) to store. This means that the entire information can be stored in a single integer of magnitude at most 2^{2^{n}} (as a very crude upper bound). The key point with respect to Michaux’ coding argument now is that there is only one single integer M ≤ 2^{2^{n}} holding all the necessary information. In this particular situation his method works without super-polynomial time trade-off; the information in M can be decoded and encoded in polynomial time (using repeated squaring). Thus, an adaption of Lynch’s algorithm for FO_{ℝ}^{−} can be performed in (P_{ℝ}, const).

Next we consider full first order logic on ℝ-structures.

Theorem 4.2. The language FO_{ℝ} of first order logic is data-complete in (P_{ℝ}, const). It is expression-complete in DPAT_{ℝ}, the class of problems decidable in polynomial digital alternating time over ℝ ([11]).

Proof. Concerning data-complexity we again only have to show containment of the graph membership problem in (P_{ℝ}, const). Since all semi-algebraic databases considered here by convention are ordered one can cycle through all possible tuples of assignments of those variables quantified in the given formula

ρ(a) ≡ Q_{1}x_{1}Q_{2}x_{2} … Q_{k}x_{k} ψ(x_{1}, …, x_{k}, a) , Q_{i} ∈ {∀, ∃} and ψ ∈ FO_{ℝ}^{−}.

Since the number of quantifiers in ρ is fixed and since FO_{ℝ} quantifiers only range over the finite universe there are polynomially (namely n^{k}) many different assignments for the x_{i} only (where n denotes the size of the database). For each of them ψ(x, a) can be evaluated in (P_{ℝ}, const) according to the last theorem. It remains to plug together the polynomially many truth values and to check whether they satisfy the quantifier prefix. Again an argument on the magnitude of integers coding all this information yields the claim: Given the quantifier prefix consider all those subsets T of assignments for the x_{i}’s with the following property: ρ(a) is evaluated “true” if exactly for all x ∈ T the sentence ψ(x, a) is true. Such a T can be coded by an integer ≤ 2^{n^{k}} and all such subsets can be represented via a single integer ≤ 2^{2^{n^{k}}}. Since integers of such magnitude are computable in time O(n^{k}) in the BSS model, all the information about the truth values of ψ necessary to make ρ true can be coded in polynomial time in a single register. As above, it follows that for given (𝔇, a) 𝔇 ⊧ ρ(a) can be checked in (P_{ℝ}, const).

Next, consider a semi-algebraic database 𝔇 to be given. We want to show that deciding membership in Gr_{FO_{ℝ}}(𝔇) is in class DPAT_{ℝ}. To this aim we have to show (see [11]) the existence of a polynomial p and a BSS machine M such that

(a, ρ) ∈ Gr_{FO_{ℝ}}(𝔇) ⟺ ∃y_{1}∀z_{1}∃y_{2}∀z_{2} … ∃y_{p(|ρ|)}∀z_{p(|ρ|)} M accepts the input (a, ρ, y_{1}, z_{1}, …, y_{p(|ρ|)}, z_{p(|ρ|)}) in time ≤ p(|ρ|) .

W.l.o.g. we assume the universe of 𝔇 to be A := {0, 1}. Let a formula ρ(a) ≡ Q_{1}x_{1} … Q_{k}x_{k}ψ(a, x) ∈ FO_{ℝ} of length n be given; clearly, k ≤ n. Thus we can choose a linear polynomial p in the definition of DPAT_{ℝ} satisfying the following: For any formula ρ of length n the machine M on input (a, ρ) first matches the quantifier shape Q_{1} … Q_{k} with a corresponding shape in ∃y_{1} … ∀z_{p(|ρ|)} and then evaluates ψ on (x_{1}, …, x_{k}, a, ρ) in linear time.

Let us turn to completeness. The following problem QBSCP (quantified binary satisfiability circuit problem) is complete under (P_{ℝ}, const) reduction in class DPAT_{ℝ}: given an algebraic circuit 𝔅 with n inputs and a quantifier prefix Q_{1} … Q_{n} ∈ {∃, ∀}^{n}, decide whether Q_{1}x_{1} … Q_{n}x_{n} 𝔅 accepts (x_{1}, …, x_{n}). Here the x_{i} range over {0, 1}. Its completeness can be easily established in a similar manner the existence of a DNP_{ℝ}-complete problem is shown in [11]. Just note that the Lagrange polynomials used therein can be evaluated in (P_{ℝ}, const). QBSCP can be obtained as a membership problem for a particular Gr_{FO_{ℝ}}(𝔇_{0}). Choose a semi-algebraic database 𝔇_{0} := (𝔄_{0}, 𝔉_{0}) where the universe is A_{0} = {0, 1}, the finite structure associated with 𝔄_{0} is empty and 𝔉_{0} consists of the constant nullary function 1 ∈ ℝ only. Any OBSCP instance can then be expressed as a membership task for Gr_{FO_{ℝ}}(𝔇_{0}) by representing the given algebraic circuit by a FO_{ℝ}^{−} formula of polynomially bounded length.

As shown in [17] (see Theorem 2.9) over ordered ℝ-structures first order fixedpoint logic captures P_{ℝ}. This implies

Theorem 4.3. The language FP_{ℝ} of first order fixed-point logic is data-complete in P_{ℝ} and expression-complete in EXP_{ℝ}.

Proof. For data-completeness membership in P_{ℝ} is a consequence from [17]. Completeness follows by reduction from the problem SUBS of deciding, whether a system of quadratic polynomial equations and inequalities over ℝ is solvable by substitution (see [13]). The P P T reduction algorithm used in [13] in order to establish P_{ℝ}-completeness of SUBS can be performed in (P_{ℝ}, const) as well: the time used by each processor in those reductions is constant.

Concerning expression-complexity membership in EXP_{ℝ} is immediate by combining the arguments in the proofs of Theorem 4.1 and 4.2. Cycling through all possible assignments of the quantified variables works in time EXP_{ℝ} and the same holds true for evaluating a fixed-point construct. Completeness is established by reducing any EXP_{ℝ} problem to the membership problem for Gr_{FP_{ℝ}}(𝔇_{0}) where 𝔇_{0} is as in the proof of Theorem 4.2. This works exactly as in [17] describing the actions of an EXP_{ℝ} machine M by a function Z : A^{m} → ℝ for a suitable m ∈ ℕ being linear in the size of the current input for M. The steps performed by M as usually are simulated using the fixed-point rule. Since for a given problem in EXP_{ℝ} M is fixed this reduction works within complexity class (P_{ℝ}, const).

Consider once more Example 1.1. In our approach the problem is represented by a semi-algebraic database 𝔇 = (𝔄, 𝔉) where A = {1, …, n} and 𝔉 consists of one function symbol X : A^{2} → ℝ; here X(•, j) for fixed j represents the j-th point of the database ℜ (for simplicity we have chosen here the dimension ℝ^{n} equal to the number of points. This can be generalized without difficulty). Now the largest distance problem is expressed by a FP_{ℝ} formula: for two points X(•, i) and X(•, j) ∈ ℝ^{n} in ℜ (i.e. i, j ∈ A and X(k, i) is the k-th component of X(•, i)) define a function which sums up the n components (X(k, i)−X(k, j))^{2}, 1 ≤ k ≤ n. The latter function is describable as a fixpoint. Thus the related query can be seen to be computable in polynomial time according to Theorem 2.9 just by analyzing its logical form. No quantifier elimination over a real closed field is involved in the logical description.

We next turn to logics involving second order constructs. This means one can quantify over functions from the finite universe to ℝ. Thus second order logic is related to quantifier elimination problems for real closed fields and therefore to nondeterminism as defined in the BSS model.

Theorem 4.4. The language ∃SO_{ℝ} of existential second order logic is datacomplete in NP_{ℝ} and expression-complete in NEXP_{ℝ}.

Proof. Containment in the corresponding complexity classes follows from [17] by guessing the existentially quantified functions and evaluating the remaining FO_{ℝ} formula. Completeness is shown as in Theorem 4.3.

Without proof we mention the digital version of existential second order logic to capture the digital analogues of NP_{ℝ} and NEXP_{ℝ}.

Corollary 4.5. The language ∃DSO_{ℝ} of digital existential second order logic is data-complete in DNP_{ℝ} and expression-complete in DNEXP_{ℝ}.

Finally, we treat SO_{ℝ} logic.

Theorem 4.6. The language SO_{ℝ} of second order logic is data-complete in PH_{ℝ} and expression-complete in PAT_{ℝ}, the class of problems decidable in polynomial alternating time over ℝ.

Proof. This is almost the same as that for Theorem 4.2. Now the second order quantifiers range over elements in ℝ (more precisely: over function variables), the reason why on the data-complexity side one jumps to the polynomial hierarchy. For expression-complexity it yields in replacing the binary quantifiers by “full” ones, i.e. switching from DPAT_{ℝ} to PAT_{ℝ}.

We have seen that using descriptive complexity theory over the real numbers as ground tool for dealing with queries to semi-algebraic databases allows a uniform treatment both of data- and expression-complexity issues. A strong correspondence between the logic on ℝ-structures necessary to describe a query and the complexity of computing the latter can be settled. Especially it is possible to treat queries for semi-algebraic databases whose data belong to real euclidean spaces of different dimension. The following table summarizes our results:

Logic

data-complete in expression-complete in

FO_{ℝ}^{−}  (P_{ℝ}, const)  (P_{ℝ}, const)
FO_{ℝ}  (P_{ℝ}, const)  DPAT_{ℝ}
FP_{ℝ}  P_{ℝ}  EXP_{ℝ}
∃DSO_{ℝ}  DNP_{ℝ}  DNEXP_{ℝ}
∃SO_{ℝ}  NP_{ℝ}  NEXP_{ℝ}
SO_{ℝ}  PH_{ℝ}  PAT_{ℝ}

Similar results can be obtained for the other logics considered in [17] and [12]. We would like to stress that the basic concept of k-ary generalized tuples

introduced in [20] is captured by our foregoing as well. If in the former setting a geometric object is given by a finite collection of quantifier free formulas, in the latter we can easily describe these formulas (resp. the polynomials involved) as a ℝ-structure (see [17]). Moreover, the size of this ℝ-structure is determined by the important quantities influencing complexity issues, namely the number of variables (which has not to be fixed), the degree of the polynomials in the describing formula and the number of constraints.

An important area for further research in our opinion is the closer study of unranked ℝ-structures, combined with the above mentioned idea to deal with genericity. Here we believe an extension of the ideas developed in [2] and [3] to be promising.

5. Acknowledgement

This work was done while the author was staying at the Mathematical Sciences Research Institute, Berkeley, US. The stay was made possible by partial support both from the MSRI and the Deutsche Forschungsgemeinschaft, AZ: Me 1424/3-1. Thanks go to C. Michaux for helpful discussions.

References

[1] S. Abiteboul, R. Hull, V. Vianu: Foundations of Databases. Addison-Wesley (1995).

[2] S. Abiteboul, V. Vianu: Generic Computation and its Complexity. Proc. 23rd STOC (1991), 209–219.

[3] S. Abiteboul, C.H. Papadimitriou, V. Vianu: The Power of Reflectional Relational Machines. Proc. LICS (1994).

[4] M. Benedikt, G. Dong, L. Libkin, L. Wong: Relational Expressive Power of Constraint Query Languages. Journal of the ACM 45, No.1 (1998), 1–34.

[5] M. Benedikt, L. Libkin: On the Structure of Queries in Constraint Query Languages, Proc. LICS 1996, 25–34.

[6] M. Benedikt, L. Libkin: Languages for Relational Databases over Interpreted Structures, Proc. PODS 1997, 87–98.

[7] L. Blum, F. Cucker, M. Shub, S. Smale: Complexity and Real Computation. Springer-Verlag (1998).

[8] L. Blum, M. Shub, S. Smale: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin American Mathematical Society 21 (1989), 1–46.

[9] A.K. Chandra, D. Harel: Computable Queries for Relational Data Bases. Journal of Computer and System Sciences 21 (1980), 156–178.

[10] F. Cucker: On the complexity of quantifier elimination: the structural approach. The Computer Journal 36 (1993), 400–408.

[11] F. Cucker and M. Matamala: On digital nondeterminism. Mathematical Systems Theory 29 (1996), 635–647.

[12] F. Cucker, K. Meer: Logics which capture complexity classes over the reals. To appear in: Journal of Symbolic Logic.

[13] F. Cucker, A. Torrecillas: Two P-complete Problems in the Theory of the Reals. Journal of Complexity 8 (1992), 454–466.

[14] F. Dumortier, M. Gyssens, L. Vandeurzen, D. van Gucht: On the decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases. Proc. PODS (1997), 68–77.

[15] H.D. Ebbinghaus, J. Flum: Finite Model Theory. Springer-Verlag (1995).

[16] E. Grädel and Y. Gurevich. Metafinite model theory. In: D. Leivant (ed.), Logic and Computational Complexity. Springer-Verlag (1996), 313–366.

[17] E. Grädel, K. Meer: Descriptive complexity theory over the real numbers. Proc. STOC (1995) 315–324. Full paper version in: J. Renegar, M. Shub, and S. Smale (editors): The Mathematics of Numerical Analysis, Lectures in Applied Mathematics 32, American Mathematical Society (1996), 381–404.

[18] S. Grumbach, J. Su: Queries with arithmetical constraints. Theoretical Computer Science 173 (1997), 151–181.

[19] M. Gyssens, J. van den Bussche, D. van Gucht: Complete geometrical query languages. Proc. PODS (1997), 62–67.

[20] P.C. Kanellakis, G.M. Kuper, P.Z. Revesz: Constraint Query Languages, Journal of Computer and System Sciences 51 (1995), 26–52.

[21] N. Lynch: Logspace recognition and translation of parenthesis languages. Journal of the ACM 24 (1977), 583–590.

[22] K. Meer, C. Michaux: A Survey on Real Structural Complexity Theory. Bulletin of the Belgian Mathematical Society Simon Stevin 4 (1997), 113– 148.

[23] C. Michaux: Une remarque à propos des machines sur ℝ introduites par Blum, Shub et Smale. C. R. Acad. Sci. Paris, 309, Série I (1989), 435–437.

[24] J. Paredaens, J. Van den Bussche, D. van Gucht: First-order queries on finite structures over the reals. SIAM Journal on Computing 27, no.6 (1998), 1747–1763.

[25] M. Vardi: Complexity of relational query languages. Proc. 14th STOC (1982), 137–146.

Klaus Meer, Lehrstuhl C fuer Mathematik, RWTH Aachen, Templergraben 55, D-52062 Aachen, Germany

E-mail address: meer@rwth-aachen.de