Methods and apparatus for generating and using safe constraint queries

[0002] The present application is related to U.S. patent application respectively entitled: “Methods and Apparatus for Providing Aggregation Operations in Constraint Databases,” filed concurrently herewith.

[0003] The invention relates to database management systems and, more particularly, to methods and apparatus for generating and using safe constraint queries in accordance with relational and spatial database management systems.

[0004] The power of classical query languages is linked to the fact that they express a restricted class of declarative programs. The class of semantic objects expressible through queries in the relational calculus is limited in a number of helpful ways, for example, each such query is polynomial-time computable. Although relational calculus queries may not return finite results, a natural subclass of the relational calculus does, namely, the class of range-restricted queries. This class gives guarantees of finite output and is complete in that it captures all relational calculus queries whose outputs are always finite, i.e., safe queries. The class of range-restricted queries provides an effective syntax for safe queries, as every safe query is equivalent to a range-restricted one. However, the question of whether a relational calculus query is safe or not is known to be undecidable in conventional database systems.

[0005] The relational theory on which these results are based deals only with pure relational queries, that is, those containing no interpreted predicates. Practical query languages, in contrast, contain interpreted functions such as + and *. The resulting queries, then, make use of the domain semantics, rather than being independent of them as are pure relational queries. For example, if the underlying structure is the field of real numbers , +, *, 0,1, <, the extension of relational calculus is achieved by using polynomial (in)equalities. For example, the query φ(x, y)≡∃z·R (x, z)R(z, y)x²+y²=z defines a subset of the self-join operation with the condition that in joinable tuples (x, z) and (z, y), z must be the sum of squares of x and y. A natural question, then, is what sort of restrictions still apply to queries given with interpreted structure.

[0006] A problem related to safety is that of state-safety, that is, for a query and a database, determine if the output is finite. Unlike the safety problem, which are undecidable, the state-safety problem is decidable for some domains, such as natural numbers with the order relation. However, there are interpreted structures (even with decidable first-order theory) for which this problem is undecidable and for which the class of safe queries cannot be described syntactically.

[0007] Accordingly, there is a need for methods and apparatus for generating relational calculus queries in the context of certain types of database systems that are considered safe and thus solve the issues of undecidability and the lack of effective syntax.

[0008] The present invention provides for methods and apparatus for ensuring that queries presented to a database are safe thus providing solutions to both the undecidability and lack of effective syntax issues mentioned above. In a broad aspect of the invention, a method for use in a database system includes obtaining an original query entered by a user. The invention then provides for pre-processing the query before submittal to a database engine associated with the database system wherein a result of the pre-processing operation is to ensure that a query provided to the engine is safe. As mentioned above, safety has a different meaning depending on the application. For example, safety may include ensuring that a query will return an output with finite results or it may include ensuring that certain geometric properties in the query are preserved in the output.

[0009] In a first embodiment of the invention, the pre-processing step includes automatically modifying the original query to ensure a return of finite results from the database by inserting at least one range-restriction in the original query. The range-restriction specifies an upper bound on the results to be returned by the database as a set of roots of polynomials with coefficients coming from an active domain of the database and a finite set of constants. Preferably, the range-restriction is inserted regardless of whether the original query would have returned a finite result.

[0010] In a second embodiment, the original query is a conjunctive query and the pre-processing step includes analyzing the original conjunctive query to determine if the original conjunctive query would return finite results from the database. Further, the pre-processing step includes prompting the user to restrict the original conjunctive query, if the original query would not return finite results, by inserting at least one range-restriction in the original query. Again, the range-restriction specifies an upper bound on the results to be returned by the database as a set of roots of polynomials with coefficients coming from an active domain of the database and a finite set of constants.

[0011] In a third embodiment, the original query contains at least one geometric property and the pre-processing step includes coding the original query with effective syntax to ensure preservation of the at least one geometric property in results returned from the database. Thus, whenever a query includes a certain type of geometric object, the result returned by the database engine will include only that type of geometric object.

[0012] The invention applies to the standard relational calculus with interpreted functions on finite structures; we then applied these results to get structural restrictions on the behavior of queries in the constraint database model of Kanellakis, Kuper and Revesz, “Constraint Query Languages,” Journal of Computer and System sciences, 51 (1995), 26-52 (extended abstract in PODS'90, pp. 299-313). This model is motivated by new applications involving spatial and temporal data, which require storing and querying infinite collections. It extends the relational model by means of “generalized relations.” These are possibly infinite sets defined by quantifier-free first-order formulae in the language of some underlying infinite structure M=U,Ω. Here U is a set (assumed to be infinite), and Ω is a signature that consists of a number of interpreted functions and predicates over U. For example, in spatial applications, M is usually the real field , +, *, 0,1, <, and generalized relations describe sets in ⁿ.

[0013] A database given by a quantifier-free formula α(x₁, . . . ,x_n) in the language of Ω defines a (possibly infinite) subset of Uⁿgiven by D_α={{right arrow over (α)} ∈ Uⁿ| M α ({right arrow over (α)})}. Such databases are called finitely representable, as the formula α provides a finitary means fox representing an infinite set. For example, if α(x, y)≡(x²+y²≦1), then D_αis the circle of radius 1 with the center in (0, 0).

[0014] Relational calculus can be extended in a straightforward manner to this model, by incorporating atomic formulas which are Ω-constraints, that is, atomic Ω-formulae. For example, φ(x, y)≡(D (x, z)y=x²) is a first-order query which, on D_αdefined above, returns the intersection of the circle with the graph of the function y=x².

[0015] For the constraint model, the invention enforces safety in the sense of the preservation of restricted geometric classes of databases within powerful constraint query languages. In particular, we deal with enforcing that polynomial constraint queries preserve linear constraint databases and subclasses thereof. Linear constraints are used to represent spatial data in many applications. Linear constraints have several advantages over polynomial: the quantifier-elimination procedure is less costly, and numerous algorithms have been developed to deal with figures represented by linear constraints. At the same time, the extension of relational calculus with linear constraints has severely limited power as a query language. Thus, it is natural to use a more powerful language, such as relational calculus with polynomial constraints, to query databases represented by linear constraints. We also consider polynomial constraints over the smaller class of convex polyhedra, the latter being an even more restricted class that still captures spatial figures that are important for geometric modeling.

[0016] Since the class of constraints used in queries is more general than the class used to define databases, we encounter the safety problem again: the output of a polynomial when applied to a linear constraint database may fail to be a linear constraint database, and similarly the output of a polynomial constraint query on a convex polyhedron may fail to be a convex polyhedron. Generally, if spatial databases are required to have certain geometric properties, then the safety problem is whether those properties are preserved by a given query language. The invention provides means for enforcing that polynomial constraint queries do preserve geometric properties, in particular for the classes of convex polytopes, convex polyhedra, and compact semi-linear sets. It also provides means to determine whether a conjunctive polynomial constraint query does preserve the classes listed above.

[0017] FIG. 1 is a block diagram of a relational spatial database management system according to an illustrative embodiment of the present invention;

[0018] FIG. 2 is a flow diagram of a method of automatic safe query translation according to an illustrative embodiment of the present invention;

[0019] FIGS. 3A and 3B is a flow diagram of a method of safe query analysis and user-input query restriction according to an illustrative embodiment of the present invention; and

[0020] FIGS. 4A and 4B is a flow diagram of a method of effective syntax query translation according to an illustrative embodiment of the present invention.

[0021] The present invention is described below in the context of generation and use of safe queries in a spatial database. As is known, spatial databases store information related to spatial locations. Examples of spatial databases are computer aided design (CAD) databases (i.e., database for storing design information about how objects are constructed) and geographic databases (i.e., database for storing geographic information such as, for example, maps) referred to as Geographic Information Systems (GIS). Information associated with spatial databases is typically made up of geometric constructs (e.g., lines, triangles, polygons, etc.). It is to be appreciated that the teachings of the invention discussed herein are not limited to these specific examples but rather are also applicable to all databases having information with properties similar to geometric information, e.g., integer databases that support addition, multiplication and/or ordering operations. It is also to be noted that the invention is applicable to relational databases. As is known, a relational database is a database that stores data in the form of “relations,” which may be viewed as tables of data items. An “attribute” of a relation refers to a specific category of data in a relation. The term “tuple” refers to a particular data item or record stored in a table or other type of relation. A “query” is a request for information in some form entered by a user to the database system.

[0022] Further, as used herein, the term “processor” is intended to include any processing device, including a CPU (central processing unit) and associated memory. Accordingly, software instructions or code associated with implementing the methodologies of the present invention may be stored in associated memory and, when ready to be utilized, retrieved and executed by an appropriate CPU.

[0023] Referring initially to FIG. 1, a block diagram of a relational spatial database management system according to an illustrative embodiment of the present invention is shown. The system 10 includes a user interface and control unit 14 with which a user 12 of the system interacts to enter queries and view results associated with the database system 10. The user interface can include any conventional computer input/output devices. For example, the user interface and control unit 14 may include a keyboard and/or mouse for entering and modifying queries and data and a video terminal for viewing query results and other data associated with the other components of the system 10.

[0024] The database system 10 also includes a query pre-processor 16 coupled to the user interface 14. As will be explained in detail below, the query pre-processor 16 performs query analysis and translation operations according to the invention. For instance, the pre-processor 16 analyzes a user input query to determine if the ranges associated with the query are restricted to ensure safety. Also, the pre-processor 16 performs transformations (i.e., translates) on a user input query to return a query that is restricted to ensure safety.

[0025] The database system 10 also includes a spatial database engine 18 coupled to the user interface 14. As will be explained in detail below, the spatial database engine 18 controls the storage of spatial information such as, for example, Point and Region data in a data store 20 coupled thereto. Also, the spatial database engine 18 processes queries received from the user interface 14.

[0026] It is to be appreciated that the components depicted in the relational spatial database management system 10 may be implemented in accordance with one or more general or special purpose processors. Depending on the amount and complexity of the spatial data, the system 10 may be embodied in a variety of processor-based machines, e.g., one or more personal computers, workstations, microcomputers, etc.

[0027] For ease of reference, the remainder of the detailed description will be divided into sections as follows: (I) Notations; (II) Data Structure Qualities; (III) Automatic Safe Query Translation; (IV) Safe Query Analysis and User-Input Query Restriction; (V) Effective Syntax Query Translation Via Preservation of Geometric Properties.

[0028] I. Notations

[0029] It is to be appreciated that new applications of database technology, such as Geographical Information Systems (GIS), have spurred a considerable amount of research into generalizations of the standard relational database model to deal with the manipulation of geometric or spatial data. One common approach to modeling spatial database is to consider input databases as given by a set of well-behaved relations in euclidean space, for example, by a set of semi-linear or semi-algebraic sets. There are a number of proposed query languages that extend classical relational algebra to this setting, languages that allow the use of various geometric operations in manipulating spatial databases. One of the most well-developed models for spatial queries is the constraint database model as disclosed in P. Kanellakis, G. Kuper, and P. Revesz, “Constraint Query Languages,” JCSS,51 (1995), 26-52, extended abstract in PODS'90, pages 299-313. In this model, spatial databases are represented as sets of linear or polynomial constraints. Databases are queried using standard relational calculus with linear or polynomial inequalities as selection criteria. These languages, denoted by FO+LIN and FO+POLY, have become the dominant ones in the constraint database literature. FO+EXP+POLY is another. These languages have a very important closure property: the application of a FO+LIN query to a linear constraint set yields a new set of linear constraints; similarly FO+POLY queries on sets definable with polynomial constraints produce sets that can still be defined with polynomial constraints.

[0030] The notations we use are fairly standard in the literature on databases. We study databases over infinite structures. Let M=U,Ω be an infinite structure, where U is an infinite set, called a carrier (in the database literature it is often called domain), and Ω is a set of interpreted functions, constants, and predicates. For example, for the real field , +, *, 0,1, <, the carrier is (the set of real numbers), and the signature consists of the functions + and *, constants 0 and 1, and predicate <.

[0031] A (relational) database schema SC is a nonempty collection of relation names {S₁, . . . ,S₁} with associated arities p₁, . . . ,p₁>0. Given M, an instance of SC over M is a family of finite sets, {R₁, . . . ,R₁}, where R_i⊂U^pi. That is, each schema symbol of arity p_iis interpreted as a finite p_i-ary relation over U. Given an instance D, adom (D) denotes its active domain, that is, the set of all elements that occur in the relations in D. We normally assume adom (DB) is not empty.

[0032] As our basic query language, we consider relational calculus, or first-order logic, FO, over the underlying models and the database schema. In what follows, L (SC, Ω) stands for the language that contains all symbols of SC and Ω; by FO (SC, Ω) we mean the class of all first-order formulae built up from the atomic SC and Ω-formulae by using Boolean connectives ,, and quantifiers ∀, ∃ and ∀x ∈adom, ∃x ∈adom . When Ω is (+,−,0,1,<), (+,*,0,1, <), or (+,*,e^x, 0,1, <), we use the standard abbreviations FO+LIN, FO+POLY, or FO+EXP, respectively, often omitting the schema when it is understood. Regardless of whether we are in the “classical” setting, where these queries are applied to finite databases, or in the constraint query setting discussed herein, we will refer to the syntactic query languages as relational calculus with constraints Ω.

[0033] The semantics are as follows. For a structure M and a SC-instance D, the notion of (M, D) φ is defined in a standard way for FO (SC, Ω) formulae, where ∃x ∈adom is the active-domain quantification. That is, (M, D) ∃x φ(x,•) if for some α ∈ U we have (M, D) φ(α, •), and (M, D) ∃x ∈ adom φ(x , •) if for some α ∈ adom (D) we have (M, D) φ(α, •). If M is understood, we write D φ. The output of a query φ(x₁, . . . ,x_n) on D is {{right arrow over (α)}=(α₁, . . . ,α_n) ∈ Uⁿ|D φ({right arrow over (α)})}, and it is denoted by φ[D]. For example, φ(x,y)≡(S(x,y) y=x * x) is a FO+POLY query over the schema that contains one binary relation S; and φ[D] is the set of pairs in (x, y) in D where y=x².

[0034] We now say that a FO (SC, Ω) query φ({right arrow over (x)}) is safe for a SC-database D if it has finitely many satisfiers for D; that is, φ[D] is finite. A query is safe if it is safe for all databases.

[0035] As previously explained, we need to distinguish a class of “well-behaved” models. We use o-minimality and quantifier-elimination, as are known in the art, for this purpose. We say that M is o-minimal, if every definable set is a finite union of points and open intervals {x | α<x<b} (we assume that < is in Ω). Definable sets are those of the form {x | M φ(x)}, where φ is a first-order formula in the language of M, possibly supplemented with symbols for constants from M. We say that M admits quantifier-elimination (QE) if, for every formula φ({right arrow over (x)}), there is an equivalent quantifier-free formula ψ({right arrow over (x)}) such that M ∀{right arrow over (x)}·φ({right arrow over (x)}) ψ({right arrow over (x)}). Below we list the most important examples of classes of interpreted structures and constraints often used in applications:

[0036] Linear Constraints: , +, −, 0,1, < is o-minimal, has QE, and its first-order theory is decidable.

[0037] Polynomial Constraints: The real field , +, *, 0,1, < is o-minimal, has QE, and its first-order theory is decidable. This follows from Tarski's theorem, as is known in the art.

[0038] Exponential Constraints: , +, *, e^x, 0,1, < is o-minimal.

[0039] The following are results about o-minimal structures that will be used herein:

[0040] Fact 1.1 (Uniform Bounds)

[0041] If M is o-minimal, and φ(x, {right arrow over (y)}) is a first-order formula in the language of M, possibly supplemented with symbols for constants from M, then there is an integer K such that, for each vector {right arrow over (α)} from M, the set {x | M φ(x, {right arrow over (α)})} is composed of fewer than K intervals.

[0042] If only quantifiers ∀x ∈adom and ∃x ∈adom are used in a query, it is called an active-semantics (or active-domain) query. This is the usual semantics for databases, and it will be the one used in most of the results here. If quantification over the entire infinite universe is allowed, we speak of a natural-semantics query. Active-semantics queries admit the standard bottom-up evaluation, while for natural-semantics it is not clear a priori if they can be evaluated at all. However, in many cases one can restrict one's attention to active-semantics queries. The following result was first shown for the pure case (no interpreted structure), for linear constraints, and then for a large class of structures as follows:

[0043] Fact 1.2 (Natural-Active Collapse)

[0044] If M is o-minimal and has QE, and φ is an arbitrary FO (SC, Ω) query, then there exists an equivalent FO (SC, Ω) active-semantics query φ_act. Moreover, if the first-order theory of M is decidable and QE is effective, then the translation φ→φ_actis effective.

[0045] We now define the classes of conjunctive queries (CQ), unions of conjunctive queries (UCQ) and Boolean combination of conjunctive queries (BCCQ) in the interpreted setting. CQs are built up from atomic SC formulae and arbitrary Ω-formulae by using and quantifiers ∃x and ∃x ∈adom. Note that we can always assume that parameters of each SC relation are variables, as Ω-terms can be eliminated by using existential (active-domain) quantifiers. It is easy to see that each CQ can be represented in the form:

[0046] φ({right arrow over (z)})≡∃{right arrow over (x)}∃{right arrow over (y)}∈adom S₁({right arrow over (u)}₁) . . . S_k({right arrow over (u)}_k)γ({right arrow over (x)}, {right arrow over (y)}, {right arrow over (z)})

[0047] where S₁'s are schema relations (not necessarily distinct), {right arrow over (u)}_iis a vector of variables from {right arrow over (x)}, {right arrow over (y)}, {right arrow over (z)} of appropriate arity, and γ is a Ω-formula. If Ω=0 and {right arrow over (x)}=0, this is the usual notion of conjunctive queries. If γ is quantifier-free, this is another notion of conjunctive queries.

[0048] We define UCQs to be built up from atomic SC formulae and arbitrary Ω-formulae by using , , and quantifiers ∃x and ∃x ∈adom. Again, it is easy to see that those are precisely the queries of the form φ₁ . . . φ_kwhere each φ_iis a CQ. Finally, BCCQ are arbitrary Boolean combinations of CQs.

[0049] Although we could define active domain versions of conjunctive queries, the results we state here (e.g., decidability of safety) for the more general classes above will imply the corresponding results for the more restricted class of active-domain conjunctive queries.

[0050] II. Data Structure Qualities

[0051] As previously mentioned, the present invention is applicable to databases containing spatial information. In particular embodiments to be discussed below in Sections III, IV and V, the particular type of data includes geometric constructs. However, the invention finds broader application in databases having a data model or structure that exhibits certain qualities. That is, analysis and safe query translation according to the methodologies of the invention is applicable to databases having such qualities. These preferred qualities will be described below. This section further shows that what kind of interpreted structure one uses does matter, when one studies query safety. As a by-product, we show that the state-safety problem is decidable over certain structures. We study safe translations defined as follows.

[0052] Definition 2.1

[0053] We say that there is a safe translation of (active-semantics) first-order queries over M if there is a function φ→φ_safeon (active-semantics) formulae such that for every φ:

[0054] (1) φ_safeis safe, and

[0055] (2) If φ is safe for D, then φ[D]=φ_safe[D].

[0056] A translation is canonical if φ_safe[D]=0 whenever φ is not safe on D. A translation is recursive if the function φ→φ_safesafe is recursive.

[0057] It is known that there are domains over which safe translations do not exist. However, we restrict our attention to active-domain quantification. To this end, the following are generalized results.

[0058] Pre-processing Construction 2.1

[0059] Let M be: (i) o-minimal; (ii) based on a dense order; (iii) admit effective QE; and (iv) have a decidable theory. Then it can be proven that there exists a recursive canonical safe translation of active-semantics formulae over M.

[0060] The above construction is achieved in the following manner. Let α (x) be a formula defining the active domain of the output of φ. Let Ψ₀be the sentence: ∃x₁, x₂((x₁<x₂)(∀x x₁<x<x₂→α(x))) and let Ψ be an equivalent active-semantics sentence, as above. We then define φ_safeas (φΨ. The construction then follows from the following statement: D Ψ if and only if φ[D] is finite. Examples of structures satisfying the conditions of the above construction are ,+,−,0,1,< and , +, *, 0,1, <.

[0061] Corollary 2.1

[0062] An immediate corollary to the above-proposition is as follows. That is, let M be as in the above proposition. Then, the state-safety problem, previously explained, over M is decidable. This is proven, as above, by demonstrating that the active-semantics sentence Ψ tests if φ[D] is finite.

[0063] It is to be appreciated that safe translations, recursive or not, need not exist even when one restricts one's attention to active-semantics queries, and all predicates in the signature Ω are computable. It is to be further appreciated that in the remainder of the detailed description, we concentrate on “well-behaved” structures, typically, o-minimal ones. For computability, we often impose QE and decidability of first-order theory.

[0064] III. Automatic Safe Query Translation

[0065] In a first embodiment, the invention provides for taking an input query entered by a user and automatically translating the query into a safe query. This is accomplished in accordance with the query pre-processor 16 (FIG. 1). As will be explained and illustrated in the context of FIG. 2, the query pre-processor automatically adds restrictions or filters to the user's original query to ensure that the query is of a form that will return only finite results when provided to the spatial database engine 18. This operation is referred to herein as range-restriction. It is to be appreciated that the added restriction or restrictions may be redundant, that is, the query entered by the user may have been safe to begin with, however, by automatically adding the restrictions, the pre-processor advantageously guarantees safety.

[0066] It is to be appreciated that the following is a mathematical explanation of range-restriction according to the invention in the context of the notation described in the previous sections. An illustrative scenario will follow this explanation. It is to be further appreciated that, given such detailed explanation of the invention, one of ordinary skill in the art may generate software code for implementing such principles for execution by a query pre-processor.

[0067] Let us informally describe the concept of range-restriction for databases over interpreted structures. It can be seen as a generalization, to arbitrary structures, of the idea of finiteness dependencies. Consider a query (o (x) over a database which is a finite set S of real numbers:

[0068] φ(x,y)≡∃z[S(z)(z>y)(x>0)(x*x=z)(y+y=z)]

[0069] This query defines a set of pairs of reals. It is safe, as the size of its output is at most twice the size of the input. Moreover, and this is a key observation, from the query φ and any database S, one can compute an upper bound on the output φ [S]: indeed, every element in adom (φ [S]) is either {square root over (α)} or α/2 for some element α ∈ S. Equivalently, in this upper bound every element is a solution to either x²=α or 2x=α when α ranges over S. That is, an upper bound on the result of a safe query is found as the set of roots of polynomials with coefficients coming from the active domain of the database and a finite set of constants.

[0070] This is essentially the idea of range-restriction: we find, for a safe query, a set of formulae defining an upper bound on the output. We are interested in how the underlying structure interacts with queries. For example, the invention provides that not only a set of range-restriction formulae exists for any query over a well-behaved structure, but also, under some conditions, it can be found effectively. Further, the invention provides that the upper bound works not only for safe queries, but for arbitrary queries, provided they are safe on a given database.

[0071] It is to be understood that an analog of the set of roots of polynomials must be found when dealing with arbitrary structures (e.g., , +, *, e^x). The solution to this is provided below by the model-theoretic notion of algebraic formulae in subsection (a). The range-restriction conversion technique is provided in subsection (b). Then, in subsection (c), we give two examples: the pure case, where our main result trivially translates into a classical relational theory result, and a much less trivial FO+POLY case, where we demonstrate that the upper bound is a set of roots of polynomials. Subsection (d) provides some extensions of the main result.

[0072] (a) Algebraic formulae over o-minimal structures

[0073] Here we consider formulae over M, that is, first-order formulae in the language L(Ω). We consider formulae φ({right arrow over (x)};{right arrow over (y)}) with distinguished parameter variables {right arrow over (y)}; we use “;” to separate those variables. Assume that {right arrow over (x)}is of length n and {right arrow over (y)} is of length m. Such a formula (in the language Ω and constants for elements U) is called algebraic if for each {right arrow over (b)} in U^mthere are only finitely many satisfiers of φ({right arrow over (x)};{right arrow over (b)}); that is, the set {{right arrow over (α)} ∈ Uⁿ| M φ({right arrow over (x)}; {right arrow over (b)})} is finite. A collection of formulae is algebraic if each of its elements is algebraic.

[0074] We need a syntax for algebraic formulae that will be used in the algorithms that guarantees safety. This syntax is provided below.

[0075] Let Ξ={ξ₁(x;{right arrow over (y)}), . . . ,ξ_k(x;{right arrow over (y)})} be a collection of formulae. Let: ${\mathrm{same}}_{\Xi }\left(x,x^{\prime };\overrightarrow{y}\right)\equiv \underset{i=1}{\overset{k}{⩓}}({\xi }_i\left(x;\overrightarrow{y}\right)\leftrightarrow {\xi }_i\left(x^{\prime };\overrightarrow{y}\right)$

[0076] Now define:

[0077] β₈₅(x;{right arrow over (y)})≡∀x′, x″·x′<x<x″→(∃zx′≦x″ same_Ξ (x,z;{right arrow over (y)}))

[0078] Proposition 3.1

[0079] Let M be an o-minimal structure based on a dense order. Then a formula φ(x;{right arrow over (y)}) is algebraic (over M) if and only if there exists a collection of formulae Ξ such that φ is equivalent to β_Ξformula φ({right arrow over (x)};{right arrow over (y)}) is algebraic if and only if there exists a collection of formulae Ξ in variables ({right arrow over (x)}; {right arrow over (y)}) and a formula ψ({right arrow over (x)}; {right arrow over (y)}) such that φ is equivalent to β_Ξ(x₁;{right arrow over (y)}) . . . β_Ξ(x_n;{right arrow over (y)})ψ({right arrow over (x)}; {right arrow over (y)}).

[0080] The one-variable case can be proven as follows. Let Ξ be a collection of formulae, and assume that β_Ξis not algebraic. That is, for some {right arrow over (b)} over U, β_Ξ(M; {right arrow over (b)})={α |M β_Ξ(α;{right arrow over (b)})} is infinite. Since M is o-minimal, β_Ξ(M; {right arrow over (b)}) is a finite union of points and intervals. Since < is dense, it means that there exist α₀<b₀∈ U such that [α₀, b₀]⊂β_Ξ(M; {right arrow over (b)}). We now consider the formulae ξ′_i(x)=ξ_i(x; {right arrow over (b)}) for all ξ_i∈Ξ. Since both ξ_i(M) and ξ′_i(M) are finite unions of intervals and < is dense, for every non-degenerate interval I, it is the case that either I ∩ ξ′_i(M) or I ∩ξ′_i(M) contains an infinite (closed) interval. Using this, we construct a sequence of intervals as follows: I₀=[α₀, b₀], I_i⊂I₀is an interval that is contained either in I₀∩ ξ′_i(M) or in I₀∩ξ′_i(M) . At the jth step, I_j⊂I_j-1is an interval that is contained either in I_j-1∩ ξ′_i(M) or in I_j-1∩ξ′_i(M). Let I=I_k. Then, for any c, d ∈ I, M ξ_i(c; {right arrow over (b)}) ξ_i(d;{right arrow over (b)}) .

[0081] Since I=[α′, b′] ⊂[α₀, b₀] and M β_Ξ(c;{right arrow over (b)}) for all c ∈ I, we obtain that, for every c ∈ [α′b′], there exists d ∈ [α′, b′] such that M same (c, d; {right arrow over (b)}). That is, for some ξ_i∈ Ξ, M (ξ_i(c; {right arrow over (b)})ξ_i(d; {right arrow over (b)})), which is impossible by construction of I. This proves that β_Ξis algebraic.

[0082] For the converse, we let, for any β (x; {right arrow over (y)}), Ξ consist of just β. That is, β_Ξ(x; {right arrow over (y)}) is:

[0083] ∀x′, x″·x′<x<x″→(∃z·x′≦z≦x″(β(x; {right arrow over (y)})β(z; {right arrow over (y)})))

[0084] We claim that β and β_Ξare equivalent, if β is algebraic. Fix any {right arrow over (b)} of the same length as {right arrow over (y)}, and assume that β (a; {right arrow over (b)}) holds. If β_Ξ(a; {right arrow over (b)}) does not hold, then there exist α′<α<α″ <α<α″ such that for every c ∈ [α′, α″], β(c;{right arrow over (b)})β(z; {right arrow over (b)}) holds; thus β (c;{right arrow over (b)}) holds for infinitely many c, contradicting algebraicity of β. Hence, β_Ξ(a; {right arrow over (b)}) holds. Conversely, assume that β_Ξ(a; {right arrow over (b)}) holds. If β (a; {right arrow over (b)}) does not hold, then there is an interval containing a on which β (•;{right arrow over (b)}) does not hold. Indeed, β (M;{right arrow over (b)}) is a finite union of intervals, whose complement is a finite set of points, so the above observation follows from the density. We now pick α′<α″ such that β (•; {right arrow over (b)}) does not hold on [α′, α″]. Since β_Ξ(a;{right arrow over (b)}) holds, we find c ∈ [α′, α″] such that (β(α; {right arrow over (b)})β(c; {right arrow over (b)})) holds, that is, β(c;{right arrow over (b)}) holds for c ∈ [α′, α″], which is impossible. Thus, we conclude that β (α; {right arrow over (b)}) holds, proving that β and β_Ξare equivalent, and finishing the one variable case.

[0085] For the multi-variable case, we note that algebraicity of β_Ξimplies that φ′({right arrow over (x)};{right arrow over (y)})=β_Ξ(x₁; {right arrow over (y)}) . . . β_Ξ(x_n;{right arrow over (y)}) ψ({right arrow over (x)};{right arrow over (y)}) is algebraic. Conversely, let φ({right arrow over (x)}; {right arrow over (y)}) be algebraic. Consider:

[0086] φ_i(x_i; {right arrow over (y)})=∃x₁. . . ∃x_i−1∃x_i+1. . . ∃x_n·φ(x₁, . . . , x_i, . . . , x_n; {right arrow over (y)})

[0087] Let X(x; {right arrow over (y)}) be φ₁(x; {right arrow over (y)}) . . . φ_n(x; {right arrow over (y)}) . Obviously each φ_iis algebraic, and thus X(x; {right arrow over (y)}) is algebraic. Hence, X(x; {right arrow over (y)}) is equivalent to β_Ξ(x; {right arrow over (y)}) for some finite collection Ξ of formulae in (x; {right arrow over (y)}). Note that if φ({right arrow over (α)}; {right arrow over (b)}) holds and α_iis the ith component of {right arrow over (α)}, then X(x; {right arrow over (y)}) holds and thus β_Ξ(α_i;{right arrow over (b)})holds. This shows that φ is equivalent to β_Ξ(x_i;{right arrow over (y)}) . . . β_Ξ(x_n;{right arrow over (y)}) φ({right arrow over (x)};{right arrow over (y)}) thus completing the proof.

[0088] Corollary 3.1

[0089] If M is an o-minimal structure based on a dense order, and φ({right arrow over (x)};{right arrow over (y)}) is algebraic over M, then φ is algebraic over any M′ elementary equivalent to M.

[0090] This is proven in the following manner. There exists a collection of formulae Ξ such that M ∀{right arrow over (x)}∀{right arrow over (y)}·φ({right arrow over (x)};{right arrow over (y)}) (φ({right arrow over (x)};{right arrow over (y)}) iβ_Ξ(x_i; {right arrow over (y)}) . Hence the same sentence is true in M′. Since M′ is also o-minimal and based on a dense order, we get from the proposition that φ is algebraic in M′,too.

[0091] (b) Main Pre-processing Construction

[0092] We start with a few definitions. For a L(Ω)-formulae γ({right arrow over (x)}; {right arrow over (y)}) and database D, let:

[0093] γ(D)={{right arrow over (α)}|∃{right arrow over (b)}∈adom (D)^m′ such that D γ({right arrow over (α)}; {right arrow over (b)})}

[0094] If Γ is a collection of formulae in {right arrow over (x)}; y, define: $\Gamma \left(D\right)=\bigcup _{\gamma \in \Gamma }\gamma \left(D\right).$

[0095] Note that if Γ is algebraic and finite, then Γ (D) is finite.

[0096] Definition 3.1 (Range-restriction)

[0097] Let M be an interpreted structure. A range-restricted query over M and a database schema SC is a pair Q=(Γ, φ({right arrow over (x)})), where Γ is a finite collection {γ₁({right arrow over (x)}; {right arrow over (y)}), . . . , γ_m({right arrow over (x)};{right arrow over (y)})} of algebraic L(Ω) formulae, and φ({right arrow over (x)}) is a L(SC, Ω) query.

[0098] The semantics of Q is as follows:

[0099] Q[D]={{right arrow over (α)}∈Γ(D)|Dφ({right arrow over (α)})}

[0100] That is, Γ provides an upper bound on the output of a query; within this bound, a usual first-order query is evaluated. For example, let φ(x) be the FO+POLY query S (x) (x>5). Clearly, it is not safe. Let now γ(x; y)≡(x*x=y) and Q=({γ}, φ) . Then, for any database S (which a finite set of the reals), Q [S] is the set of those elements α such that α²∈ S and either α ∈ S or α>5. Clearly, this is a finite set.

[0101] It is to therefore be observed that every range-restricted query is safe.

[0102] We call a range-restricted query (Γ,φ) active-semantics if φ is an active-semantics formula. Note that Γ does not mention the database. As will be shown, range-restricted active queries characterize all the safe active-semantics queries in the following sense.

[0103] Preprocessing Construction 3.1

[0104] Let M be any o-minimal structure based on a dense linear order. Then, there is a function Make_Safe that takes as input an active-domain formula φ({right arrow over (x)}), and outputs a range-restricted active query Q=(Γ, ψ) with the property that Make_Safe (φ) is equivalent to φ on all databases D for which φ is safe. Furthermore, if M has effective quantifier-elimination, then Make_Safe is recursive.

[0105] This may be achieved in the following manner. We deal with the one-variable case first. Let:

[0106] φ(z)≡Q₁w₁∈adom . . . Q₁w_k∈adom.α(z, {right arrow over (w)})

[0107] where each Q_iis ∃ or ∀ and α (z, {right arrow over (w)}) is quantifier-free, and all atomic subformulae R (. . .) contain only variables, excluding z. Any formula can be transformed into such by adding existential quantifiers. Let Ξ={ξ_i(z, {right arrow over (w)}) | i=1, . . . , k} be the collection of all Ω-atomic subformulae of α. We may assume without loss of generality that the length of {right arrow over (w)} is nonzero, and that Ξ is nonempty (if this is not true for φ, take φ∀ w ∈adom (w=w) and transform it to the above form).

[0108] Define same_Ξ(α, b; {right arrow over (w)}), as before, to be ^k(ξ_i(α, {right arrow over (w)})ξ_i(b, {right arrow over (w)})), and define γ(x; {right arrow over (w)}) to be:

[0109] β_Ξ(x; {right arrow over (w)}); that is, γ(x; {right arrow over (w)})≡∀x′, x″·x′<x<x″→∃y·[x′≦y≦x″ same_Ξ(x, z; {right arrow over (w)})]

[0110] Now Γ consists just of γ, with {right arrow over (w)} being distinguished parameters. We let Make_Safe (φ) output ({γ}, φ).

[0111] Since γ is algebraic by proposition 3.1, we must show that {α |DB φ(α)}={α ∈ Γ (DB) | DB φ(α)} for every nonempty database for which φ is safe.

[0112] Assume otherwise; that is, for some nonempty D for which φ is safe, we have DB φ(α) but α ∉ Γ (D). Let {right arrow over (c)}₁, . . . , {right arrow over (c)}_Mbe an enumeration of all vectors of the length of {right arrow over (w)} of elements of the active domain. Note that M>0. Since α ∉ Γ (D), we have that for each i=1, . . . M, there exist α_i, α′_isuch that α_i<α<α′_iand M same_Ξ(α,c;{right arrow over (c)};) for all c∈[α_i,α′_i].

[0113] Let b=max{α_i}, b′=max{α_i}. We have b<α<b′, and for each {right arrow over (c)} (of length of {right arrow over (w)}) over the active domain, we have ξ_i(α, {right arrow over (c)})ξ_i(c,{right arrow over (c)}) for every c ∈ [b, b′]. From this, by a simple induction on the structure of the formula (using the fact that z does not appear in any atomic formula R (. . .)), we obtain that D α(α, {right arrow over (c)})α(c, {right arrow over (c)}) for every {right arrow over (c)} over adom (D) and every c ∈ [b, b′], and thus D φ(α)φ(c), which implies that φ is not safe for D. This contradiction proves correctness of Make_Safe for the one-variable case. This completes the proof for the one-variable case. We handle the multivariable case by reducing to the one-variable case.

[0114] Let M′=U, Ω′ be a definable extension of M that has quantifier-elimination. Note that M′ is o-minimal. Let φ(z₁, . . . , z_n) be given, and define:

[0115] φ_i(z_i)≡∃z₁. . . ∃z_i−1∃z_i+1. . . ∃z_n·φ(z₁, . . . , z_i−1, z_i+1, . . . , z_n).

[0116] There is a L (SC, Ω′) active formula ψ₁(z_i) such that D ∀z·ψ_i(z)φ_i(z) for all D. Let ({γ_i(z_i, {right arrow over (w)}_i)}, ψ_i(z_i)) be the output of Make_Safe on ψ_i. Since M″ is a definable extension, we can assume without loss that γ_iis a Ω-formula.

[0117] We now define:

[0118] γ({right arrow over (z)}; {right arrow over (w)}₁, . . . , {right arrow over (w)}_n)≡γ₁(z₁; {right arrow over (w)}₁)γ_n(z_n; {right arrow over (w)}_n),

[0119] where each {right arrow over (w)}_iis of the same length as the vector of distinguished parameters in the formulae γ_i. Finally, Make_Safe (φ) outputs ({γ},φ). To see that it works, first notice that algebraicity of all γ_is implies algebraicity of γ. Now assume that D φ({right arrow over (α)}) where {right arrow over (α)}=(α₁, . . . , α_n). Then D φ_i(α_i), and thus for some vector {right arrow over (c)} of elements of the active domain, we have that γ_i(α_i, _i) holds. Thus, if {right arrow over (c)} is the concatenation of all {right arrow over (c)}_is, then γ({right arrow over (α)},{right arrow over (c)}) holds, showing that {right arrow over (α)}∈Γ(D), where Γ={γ}. This completes the proof of the multivariable case.

[0120] We finally notice that Make_Safe for one-variable formulae is recursive, no matter what M is. For the multivariable case, to make it recursive, we need a procedure for converting natural-quantification formulae into active-quantification formulae. Such a procedure exists by Fact 1.2 above.

[0121] Corollary 3.2 (Range-restricted=Safe)

[0122] For any o-minimal structure based on a dense order, the class of safe active-semantics queries is the same as the class of range-restricted queries.

[0123] Corollary 3.3

[0124] For any o-minimal structure based on a dense order (decidable or not), the collection of safe queries is recursively enumerable.

[0125] We finish this section with a proposition that follows from the special form of formulae in Γ, as established in the proof of construction 3.1.

[0126] It can be observed that by a modification of construction 3.1, the following is true.

[0127] Construction 3.2

[0128] Let M be o-minimal and based on a dense order. Let φ({right arrow over (x)}) be a first-order query. Then one can find a set Γ of algebraic formulae γ(x; {right arrow over (y)}) such that, for any database D, if φ [D] is finite, then adom (φ[D]) ⊂ Γ [D].

[0129] (c) Example applying technique to polynomial constraints

[0130] We now consider the real field, that is, with respect to the constraint language FO+POLY. One task is to find a more concrete representation of range-restricted queries over the real field. Intuitively, it should be sufficient to look for roots of polynomials p (x; {right arrow over (α)}) where {right arrow over (α)} ranges over tuples of elements of the active domain, as suggested by the example in the beginning of this section. However, even quantifier-free algebraic formulae do not give us directly this representation. Nevertheless, in accordance with the present invention, the following can be shown.

[0131] Let p (x; {right arrow over (y)}) be a multivariate polynomial over the real field. Define Root (p, {right arrow over (α)}) as 0 if p (x;{right arrow over (α)}) is identically zero, and the set of roots of p (x; {right arrow over (α)}) otherwise. Given a collection P of olynomials {p₁(x, {right arrow over (y)}), . . . , p_m(x, {right arrow over (y)})} and a database D, let: $P\left(D\right)=\bigcup _{i=1}^m\bigcup _{\overrightarrow{a}\subseteq \mathrm{adom}\left(D\right)}\mathrm{Root}\left(p_i,\overrightarrow{a}\right)$

[0132] Definition 3.2

[0133] A query in polynomial range-restricted form is a pair (P, φ), where P is a finite collection of multivariate polynomials, and φ(x₁, . . . , x_n) is a FO+POLY query. The semantics is defined as (P, φ) [D]=φ[D]∩P (D)ⁿ.

[0134] Advantageously, the following proposition states one of the key aspects of the invention that enables the query pre-processor 16 (FIG. 1) to perform the analysis and translation operations explained herein.

[0135] Construction 3.3

[0136] For every FO+POLY query φ, a collection of polynomials P can be effectively found such that φ and (P, φ) are equivalent on all databases on which φ is safe.

[0137] This may be achieved in the following manner. Given a query φ({right arrow over (x)}), effectively find a collection of algebraic formulae Γ={γ_j(x;{right arrow over (y)})}_jsuch that for any D for which φ is safe, adom (φ[D])⊂Γ(D). For each {right arrow over (α)} and each γ∈Γ, the set γ[{right arrow over (α)}]={c| γ(c; {right arrow over (α)})} is finite, and by o-minimality there is a uniform bound M such that card (γ[{right arrow over (α)}])<M for all {right arrow over (a)} and γ∈Γ.

[0138] Now let γⁱ_j(x;{right arrow over (y)}), i<M , be defined as follows: M γⁱ_j(c;{right arrow over (α)}) if either: (i) γ_j[{right arrow over (α)}] has at least i elements, and c is the ith element in the order <; or (ii) γ_j[{right arrow over (a)}] is nonempty, has fewer than i elements, and c is the largest element of γ_j[{right arrow over (α)}]; or (iii) γ_j[{right arrow over (α)}] is empty, and c=0. Note that γⁱ_j(x; {right arrow over (y)}) s are indeed L (+, *, 0,1, <) formulae. It is easy to see that each γⁱ_j(x; {right arrow over (y)}) defines a function 𝑓_ij;″^m→ where m is the length of {right arrow over (y)}, by 𝑓_ij({right arrow over (α)})=c if and only if c is the unique element such that γⁱ_j(c; {right arrow over (α)}) holds. Furthermore, this function is semi-algebraic and the following property holds: if φ is safe for D, then adom (φ[D]) is contained in _{i,j{right arrow over (α)}}𝑓_ij({right arrow over (α)}), where {right arrow over (α)} ranges over adom (D).

[0139] It is known that each 𝑓_ij({right arrow over (y)}) is algebraic, that is, there exists a polynomial p_ij(x, {right arrow over (y)}) such that p_ij(x,{right arrow over (y)})=0 if and only if x=𝑓_ij({right arrow over (y)}). It is easy to see that for P={p_ij|i<M, γ_j∈Γ}, Γ(D) ⊂P (D) and P (D) is always finite. To complete the proof, we must show effectiveness. We can effectively construct Γ, and thus find M (by writing formulae saying that each γ(x; {right arrow over (y)}) has fewer than M satisfiers for each {right arrow over (y)}, and checking if it is true by applying QE; since it is true for some M, the process terminates). Hence, we can effectively construct {right arrow over (y)}ⁱ_js, and the procedure for finding p_ijs is effective.

[0140] (d) Extensions

[0141] Suppose we are given two elementary equivalent structures M and M′, for example, ,+,< and Q, +, <. Assuming M is o-minimal based on a dense order, so is M′, and thus the characterization of a safe queries applies to M′ as well. Thus, it may be proven that if M is an o-minimal structure based on a dense order, and φ is a safe active-semantics query, then φ is safe in any structure elementary equivalent to M, i.e., M′.

[0142] Given the above-described teachings of the invention, an illustrative scenario is presented below in the context of FIG. 2 whereby a query pre-processor of the invention performs safe translation through range-restriction. It is to be appreciated that the above sections presented the invention in terms of first-order logic, or relational calculus, which is the standard theoretical database query language. Practical languages, and most notable, SQL, are based on relational calculus. The basic form of SQL statements is:

[0143] SELECT<attribute list>

[0144] FROM<relations list>

[0145] WHERE<conditions>

[0146] SQL statements roughly correspond to conjunctive queries. For example, the following SQL statement:

[0147] SELECT F1·Source, F2·Destination

[0148] FROM Flights F1, Flights F2

[0149] WHERE F1·Destination=F2·Source

[0150] selects pairs of cities from the flight database that can be reachable with at most one stopover. An equivalent conjunctive query is:

[0151] φ(x, y): ∃u (Flights(x, u)&Flights(u, y))

[0152] To achieve the power of safe first-order logic queries (without constraints), SQL statements are closed under set union, intersection and difference, and results of the queries can be saved for future use.

[0153] The present invention shows how SQL design can be extended to deal with constraints. We now illustrate this below using the example shown in FIG. 2

[0154] Referring to FIG. 2, a flow diagram is shown of a method of automatic safe query translation in the context of geometric point data according to an illustrative embodiment of the present invention. In step 210, the user 12 enters a query “Unsafe1” at the user interface 14. It is assumed that the spatial database includes a table (relation) “POINTS” which has one non-key attribute “Value,” and the relation stores real numbers. To have access to arbitrary real numbers, we assume a hypothetical relation called R with one attribute called X; its elements are all real numbers. Of course it is not stored in a database, but queries are allowed to use this relation. Thus, for example, the query entered by the user may be:

[0155] SELECT X1=R·X

[0156] X2=POINTS1·Value

[0157] X3=POINTS2·Value

[0158] FROM R, POINTS POINTS1, POINTS POINTS2

[0159] WHERE Xl*(X2-1)=X3

[0160] It is to be appreciated that query “Unsafe1” is unsafe since if POINTS has values 0 and 1 stored in it, then any real number X1 from R will satisfy the constraint X1*(X2-1)=X3, when X2=1 and X3=0. Thus, the query will have to return all triples (x, 1, 0) where x is an arbitrary real number. Hence, the query is unsafe.

[0161] Then, in step 220, the user interface 14 sends the query to the query pre-processor 16 which translates the original query and produces a query “Safe2” by adding a restriction to ensure that a finite result will be sent to engine 18. Thus, query “Safe2” is returned to the user 12 at the user interface 14 as:

[0162] SELECT X1=R·X

[0163] X2=POINTS1·Value

[0164] X3=POINTS2·Value

[0165] FROM R, POINTS POINTS1, POINTS POINTS2

[0166] WHERE X1*(X2-1)=X3

[0167] AND NOT EXISTS

[0168] (SELECT Value1=P1·Value, Value2=P2·Value

[0169] FROM POINTS P1, POINTS P2

[0170] WHERE Value1=1 AND Value2=0)

[0171] Then, in step 230 the user queries database engine 18 with “Safe2” via the user interface. The engine returns the appropriate response to the query whereby the response is a finite result.

[0172] Advantageously, the query pre-processor effectively forces the original query entered by the user to be safe. This is accomplished by the pre-processor implementing the range-restriction operation, as explained above. The operation effectively finds a set of polynomials that restrict the search range base associated with the engine 18. In other words, the query is modified to direct the engine to search for data in a certain range base. In effect, the polynomials are telling the engine how to increase the range to include the desired result.

[0173] To do this, the pre-processor adds one or more restrictions that directs the engine 18 to look only for answers where the polynomials have roots equal to zero. Advantageously, this makes the query result finite since there are only a finite amount of locations where roots of a polynomial are zero.

[0174] It is to be appreciated that the pre-processor may add filters even if the query as originally entered is safe. In such case, the filters are merely redundant to the restrictions originally included by the user. In such case, the pre-processor does not affect the result by adding one or more redundant restrictions since the original query would have returned a finite result anyway.

[0175] IV. Safe Query Analysis and User-Input Query Restriction

[0176] In a second embodiment, the invention provides for taking an input query entered by a user and analyzing it with regard to safety. That is, according to the invention, the user-entered query is analyzed to determine if it has been restricted by a relation. If this is not the case, and therefore the original query is unsafe, then the user is prompted to enter one or more appropriate restrictions. Such analysis is accomplished in accordance with the query pre-processor 16 (FIG. 1). As will be explained and illustrated in the context of FIGS. 3A and 3B, the query pre-processor analyzes a user input query and, if the query is determined to be unsafe, prompts the user to add restrictions or filters to the original query to ensure that the query is of a form that will return only finite results when provided to the spatial database engine 18.

[0177] It is to be appreciated that the following is a mathematical explanation of such analysis according to the invention in the context of the notation described in the previous sections. An illustrative scenario will follow this explanation. It is to be further appreciated that, given such detailed explanation of the invention, one of ordinary skill in the art may generate software code for implementing such principles for execution by a query pre-processor.

[0178] Safety of arbitrary calculus queries is undecidable even in the pure case, and of course it remains undecidable when interpreted functions are present. As will be explained below, the present invention provides that safety is decidable for Boolean combinations of conjunctive queries in the presence of an interpreted structure such as ,+, 0,1, <. In particular, safety of FO+POLY and FO+LIN conjunctive queries is decidable.

[0179] Recall that we are using CQ, UCQ and BCCQ for conjunctive, unions of conjunctive, and Boolean combinations of conjunctive queries (see Section I for their definition in the presence of an interpreted structure). Our proof will be by reduction to the containment problem, which is decidable for UCQs over certain structures. Note that CQs and UCQs are monotone (that is, D ⊂ D′ implies φ[D] ⊂ φ[D′]). Since there are non-monotone BCCQs, the class of UCQs is strictly contained in the class of BCCQs.

[0180] The main result here is expressed as follows.

[0181] Construction 4.1

[0182] Let M be o-minimal, based on a dense order, decidable, and admit effective QE. Then it is decidable if a given BCCQ φ({right arrow over (x)}) over M is safe.

[0183] The proof is contained in the following sub-constructions. Recall that by containment φ⊂ψ we mean φ[D] ⊂ψ[D] for any D.

[0184] Sub-construction 4.1

[0185] Let M be o-minimal and based on a dense order, and φ({right arrow over (x)}) be a first-order query. Then there exists an active-semantics CQ ψ({right arrow over (x)}) such that φ is safe if and only if φ⊂ψ.

[0186] Sub-construction 4.2

[0187] Let M be as in construction 4.1. Then containment of a BCCQ in a UCQ is decidable; that is, for a BCCQ φ({right arrow over (x)}) and a UCQ ψ({right arrow over (x)}) it is decidable if φ⊂ψ. This continues to hold if both φ and ψ are active-semantics queries.

[0188] The above two sub-constructions may be achieved as follows. Sub-construction 4.1 follows from construction 3.2: take Γ={γ₁(x; {right arrow over (y)}), . . . , γ_k(x; {right arrow over (y)})} given by the proposition; let γ=_iγ_iand let ψ(x_i, . . . , x_n) be:

[0189] ∃{right arrow over (y)}₁∈ adom . . . ∃{right arrow over (y)}_n∈ adom γ(x₁; {right arrow over (y)}₁) . . . (x_n; {right arrow over (y)}_n)

[0190] If φ⊂ψ, then φ is safe since all γ_is are algebraic. If φ is safe, then adom (φ[D]) ⊂Γ(D) for every D, which implies φ⊂ψ.

[0191] Sub-construction 4.2 is as follows: Given φ and ψ, one can effectively find a number k such that φ⊂ψ if and only if for every database D with at most k tuples, φ[D]⊂ψ[D].

[0192] This clearly implies the result, as the latter condition can be expressed as a L(Ω) sentence. For example, if the schema contains one relational symbol S, this sentence is ∀{right arrow over (x)}₁. . . {right arrow over (x)}_k∀{right arrow over (x)}.φ({right arrow over (x)})[{{right arrow over (x)}_i}/D]→φ({right arrow over (x)})[{{right arrow over (x)}_i})/D] where φ({right arrow over (x)})[{{right arrow over (x)}_i}/D] is obtained from φ({right arrow over (x)}) by replacing each occurrence of S ({right arrow over (z)}) by _i({right arrow over (z)}={right arrow over (x)}_i), and similarly for an arbitrary schema. One can now easily complete the sub-construction using the decidability of M.

[0193] Note that every BCCQ a can be represented as ⁿ(X_i({right arrow over (x)})ξ_i({right arrow over (x)})) where each X_iis CQ and each ξ_iis UCQ; this follows if one writes α as a DNF. We take k to be the maximum length of X_i(measured as the sum of the number of atomic formulae and the number of quantified variables).

[0194] Assume that φ[D] is not a subset of ψ[D] for some D; that is, we have a {right arrow over (α)} ∈ ψ[D] is not a subset of ψ[D]. Assume D X_i({right arrow over (α)})ξ_i({right arrow over (α)}) and let X_i({right arrow over (x)})=∃{right arrow over (y)}∃{right arrow over (z)} ∈ adom ^lα_j({right arrow over (x)}, {right arrow over (y)}, {right arrow over (z)}). Then, for some {right arrow over (b)} over U and {right arrow over (c)} over adom (D) we get D _j=1^lα_j({right arrow over (α)}, {right arrow over (b)}, {right arrow over (c)}). Consider those α_js which are SC-formulae. For each such α_j, which is of the form R(. . .) where R ∈ SC, there is a tuple in D that satisfies it. Select one such tuple for each SC-atomic α_j, and let D′ be D restricted to those tuples. Choose a set of at most length {right arrow over (c)} tuples in D contain all the components of {right arrow over (c)}, and add it to D′. Let the resulting database be D″. Clearly, it has at most k tuples.

[0195] Note that D″ _j=1^lα_j({right arrow over (α)}, {right arrow over (b)}, {right arrow over (c)}) and thus D″ X_i({right arrow over (α)}) since {right arrow over (c)} ⊂adom (D″). On the other hand, D″ ξ_i({right arrow over (α)}) by monotonicity of ξ_i. Thus, we get that {right arrow over (α)} ∈φ[D″]-ψ[D″] where D″ has at most k tuples. This implies that each counterexample to containment is witnessed by a ≦ k-element database, and finishes the proof of correctness of sub-construction 4.2.

[0196] To complete construction 4.1, note that under the assumption on M, the CQ ψ such that φ⊂ψ is equivalent to safety of φ can be effectively constructed—this follows from the procedure for constructing Γ given in construction 3.2. The construction can now easily be completed using sub-construction 4.2

[0197] Corollary 4.1

[0198] It is decidable whether any Boolean combination of FO+LIN or FO+POLY conjunctive queries is safe. Note, however, that safety of CQs is not decidable over every structure. For example, for N, +, *, 0,1, <, decidability of CQ safety would imply decidability of checking whether a Diophantine equation has finitely many solutions, which is known to be undecidable.

[0199] Given the above-described teachings of the invention, an illustrative scenario is presented below in the context of FIGS. 3A and 3B whereby a query pre-processor of the invention performs query analysis and then informs the user whether the original query requires any restrictions or filters to be added in order to make the query safe. We now switch to the SQL syntax again. Recall that the basic SELECT-FROM-WHERE statement corresponds to conjunctive queries, and this remains true in the presence of constraints. Thus, safety of SELECT-FROM-WHERE SQL queries is decidable, even if one uses polynomial constraints, and has access to the hypothetical relation R that refers to all real numbers.

[0200] Referring to FIGS. 3A and 3B, a flow diagram is shown of a method of safe query analysis in the context of geometric point data according to an illustrative embodiment of the present invention. In step 310, the user 12 enters a query “Unsafe1” at the user interface 14. For example, the query entered by the user may be:

[0201] SELECT X1=R·X

[0202] Y=POINTS·Value

[0203] FROM R, POINTS

[0204] WHERE (X1>Y2+2)

[0205] Then, in step 320, the user interface 14 sends the query to the query pre-processor 16 which analyzes the query. According to the invention, the pre-processor determines that the original query is unsafe since it is not restricted by a relation. The pre-processor then instructs the user interface to prompt the user for a restriction on X1.

[0206] In step 330, the user inputs “X1²-POINTS·Value=0. In this way, the user specifies that the engine should only consider values x such that x={square root over (y)} for some y in POINTS·Value. Thus, in step 340, the pre-processor generates query “Safe1” by adding the user-input restriction to the original query. In this way, the pre-processor is effectively restricting the output of the original query to values satisfying the restriction. “Safe1” is as follows:

[0207] SELECT X1=R·X

[0208] Y=POINTS·Value

[0209] FROM R, POINTS

[0210] WHERE (X1>Y+2)

[0211] AND X1²-POINTS·Value=0

[0212] Then, in step 350 the user queries database engine 18 with “Safe1” via the user interface. The engine returns the appropriate response to the query whereby the response is a finite result. An example of a response that may be returned by the engine to the user by at the user interface is shown in block 350.

[0213] Advantageously, in this scenario, the query pre-processor analyzes a query entered by the user and tells the user whether or not the query is safe, as explained above. If the query is determined to be unsafe, the user is then prompted to enter one or more restrictions. The pre-processor then generates a new query with the user-input restrictions, assuming the added restriction now makes the query safe. It is to be appreciated that the pre-processor analyzes the query with the restrictions added before declaring it safe.

[0214] To do this, the pre-processor determines whether the one or more restrictions will direct the engine 18 to look only for answers where the polynomials have roots equal to zero. Advantageously, this makes the query result finite since there are only a finite amount of locations where roots of a polynomial are zero.

[0215] V. Effective Syntax Query Translation Via Preservation of Geometric Properties

[0216] In a third embodiment, the invention implements safe query translation where safety has a different meaning then in the previous scenarios and where the data considered is region data rather than point data. Here, finiteness of an output is not at issue, but rather the invention provides a technique for creating a restricted query such that whenever a user-input query includes certain geometric object types, e.g., triangles, the output from the spatial database engine will have the same object types. This is referred to herein as the operation of preserving geometric properties. Such translation is accomplished in accordance with the query pre-processor 16 (FIG. 1). As will be explained and illustrated in the context of FIGS. 4A and 4B, the query pre-processor translates the query to ensure preservation of the same geometric properties in the results returned by the engine.

[0217] It is to be appreciated that the following is a mathematical explanation of such translation according to the invention in the context of the notation described in the previous sections. An illustrative scenario will follow this explanation. It is to be further appreciated that, given such detailed explanation of the invention, one of ordinary skill in the art may generate software code for implementing such principles for execution by a query pre-processor.

[0218] Accordingly, in this section, we deal with constraint databases that represent potentially infinite objects. The notion of safety over constraint databases is different: we are interested in identifying languages that guarantee preservation of certain geometric properties.

[0219] To give a very simple example, assume that spatial objects stored in a database are convex polytopes in ⁿ. A simple query “return the convex hull of all the vertices x with∥x∥<1” does always return a convex polytope. This query must be written in a rather expressive language: it can be expressed in FO+POLY but not FO+LIN. Now, our question is: can we ensure in some way that a class of FO+POLY programs preserves a given property, like being a convex polytope ? That is, can we find an effective syntax for the class of queries that preserve certain geometric properties ? In accordance with the invention, the answer to these questions is yes.

[0220] First, we present a general scheme for enumerating such queries in FO(M). Here M is some structure on the reals, not necessarily , +, *, 0,1, <. The approach is based on reduction to the finite case, and using our results about finite query safety.

[0221] We explain the invention for three geometric properties: (i) a convex polytope; (ii) a convex polyhedron; and (iii) a compact semi-linear set in ²(the latter are perhaps the most often encountered class of constraint databases).

[0222] We then demonstrate that for unions of conjunctive FO+POLY queries, it is decidable whether they preserve convex polytopes or compact semi-linear sets in ².

[0223] To define a general framework for explaining queries that preserve geometric properties, we recall some basic definitions on constraint (or finitely representable) databases. As before, we have a language of some underlying structure M and a schema SC, but now m-relations in SC are given by quantifier-free formulae α(x₁, . . . x_mm)in L (Ω). It is to be appreciated that we do not assume relational attributes for the sake of ease of notation. If M is , +, 0,1, <, then sets so defined are called semi-linear; for ,+, *,0,1, < they are called semi-algebraic. The query languages for constraint databases are the same as those we considered for finite ones: FO (SC, Ω).

[0224] If M=U, Ω is an infinite structure, let Obj(Ω) be the class of finitely representable databases over M, that is, Obj(Ω)=_n<wObj_n(Ω) and Obj_n(Ω) is the collection of subsets of Uⁿof the form {(x₁, . . . , x_n)|M α(x₁, . . . ,x_n)} where α is quantifier-free first-order formula in L (Ω). We use SAlg_nfor semi-algebraic sets.

[0225] Let S be an m-ary relational symbol, and let ψ(y₁, . . . , y_n) be a first-order formula in the language of S and Ω. Then this query defines a map from Obj_m(Ω) to Obj_n(Ω) as follows: for any X ∈ Obj_m(Ω), ψ[X]={{right arrow over (y)} | (M, X) ψ({right arrow over (y)})}. Clearly ψ[X] ∈ Obj(Ω), if M has quantifier-elimination.

[0226] Let C be a class of objects in Obj(Ω). We say that a first-order query ψ preserves C if for any X ∈C, ψ[X] ∈ C. For example, C can be the class of convex polytopes in SAlg.

[0227] Thus, the safety question for constraint databases is the following. Is there an effective syntax for the class of C-preserving queries? Below, we show a solution.

[0228] Definition 5.1

[0229] The class C has a canonical representation in Obj(Ω) if there is a recursive infective function g: N→N with computable inverse, and for each n, two functions code_n: 2^U→2^Uand decode_n: 2^U→2^U, where m=g(n), such that:

[0230] (1) decode_n° code_n(x)=x if x ∈ Obj_n(Ω);

[0231] (2) code_n(x) is finite if x ∈ C; decode_n(x) ∈ C if x is finite;

[0232] (3) code_nis FO(Ω)-definable on Obj_n(Ω);

[0233] (4) decode_nis FO(Ω)-definable on finite sets.

[0234] Intuitively, the canonical representation is a finite representation of C within Obj(Ω) that can be defined in first-order logic over M. For example, an approach to obtaining a canonical representation of convex polytopes would be to compute their vertices. This suffices to reconstruct the polytope, and the vertices can be defined by a first-order formula. The actual representation proposition 5.1 below) is indeed based on computing the vertices.

[0235] Next we show that canonical representations solve the safety problem. We always assume that the set Ω is recursive.

[0236] Construction 5.1

[0237] Let M=U, Ω be o-minimal, based on a dense order, decidable, and have effective QE. Suppose C is a class that has a canonical representation in Obj(Ω). Then there is an effective syntax for C-preserving FO(Ω) queries; that is, there exists a recursively enumerable set of FO(Ω) queries that express exactly all C-preserving FO(Ω) queries.

[0238] This may be achieved in the following manner. Consider an enumeration of all safe FO(Ω) queries φ_i (from Corollary 3.2 we know that it exists). Let φ use the extra relation symbol of arity m, and assume that n is such that g(n)=m; given the assumptions, we can compute that. Let φ have l parameters, and again let k be such that g(k)=l. If n and k are found for a given φ_i, we let ψbe:

[0239] decode_k° φ_i° code_n

[0240] This produces the required enumeration. So we have to check that every query above preserves C, and for every C-preserving ψ we can get φ such that decode ° φ° code coincides with ψ. The first one is clear: if we have X ∈ C, then code_n(X) is finite, hence φ_i[code_n(X)] is finite too, and applying decode_kwe get an object in C.

[0241] For the converse, suppose we have a C-preserving query ψ: Obj_n(Ω)→Obj_k(Ω). Define α as follows: α=code_k° ψ° decode_n. That is, α is a query Obj_m(Ω)→Obj_l(Ω). Given this, notice that:

[0242] decode_k° α° code_n=decode_k° code_k° ψ° decode_n° code_n=ψ

[0243] on Obj_n(Ω). Thus, it remains to show that α is safe, i.e., preserves finiteness. Let X be a finite set in U^m. Then decode_n(X) ∈ C, decode_n(X) ⊂ C. Since ψ is C-preserving, we get that Y=ψ[decode_n(X)] ∈ Obj_k(Ω) is in C, too, and thus code_k(Y) is finite. This proves finiteness of α, and concludes the proof of correctness of the construction.

[0244] We now turn to examples in the case when Ω=+, *, 0,1, <; that is, we are looking for canonical representations in SAlg. Let CPH be the class of convex polyhedra (i.e., intersections of a finite number of closed halfspaces) and CPT be the class of convex polytopes (i.e., bounded polyhedra). The basic facts on convex sets that will be used in the proofs of the propositions below are known in the art, e.g., R. T. Rockafellar, “Convex Analysis,” Princeton Univ. Press, 1970.

[0245] Proposition 5.1

[0246] The class CPT has canonical representation in SAlg. This may be proven as follows. Given a convex polytope X in ⁿ, its vertices can be found as V(X)={{right arrow over (x)}∈ⁿ| {right arrow over (x)}∈X·{right arrow over (x)}∉conv(X−{right arrow over (x)})}. Thus, vertices of convex polytopes are definable in FO (+, *,0, 1, <), because the convex hull of a finite set of points is definable, and, in view of Caratheodory's theorem, we have:

[0247] V(X)={{right arrow over (x)}∈ⁿ| {right arrow over (x)}∈X, ∀{right arrow over (x)}_i, . . . , {right arrow over (x)}_n+1∈X−{right arrow over (x)}·{right arrow over (x)}∉conv ({{right arrow over (x)}₁, . . . , {right arrow over (x)}_n+1})}

[0248] We now define code_n. To simplify the notation, we let it produce a pair of n-ary relations, but it can be coded in a straightforward manner by one relation. If X=conv(V(X)), then code_n(X)=(V(A),O); otherwise, code_n(X)=(ⁿ, X). The function decode_n: 2R ⁿ×2R ⁿ→2Rⁿis defined as follows: ${\mathrm{decode}}_n\left(Y,Z\right)=\{\begin{array}{cc}\bigcup _{\left({\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_{n+1}\right)\in Y}\mathrm{conv}\left(\left\{{\overrightarrow{y}}_1,\dots ,{\overrightarrow{y}}_{n+1}\right\}\right)& \mathrm{if}Y\ne {\Re }^n\\ Z& \mathrm{otherwise},\end{array}$

[0249] Clearly, decode_n° code_nis the identity function for any (semi-algebraic) set; these functions are also first order definable. If X is a polytope, V(X) is finite, and by Caratheodory's theorem each point of X is contained in the convex hull of most n+1 vertices of X. Hence, card (code_n(X))≦card (V(X))ⁿ⁺¹, which is finite. If (Y, Z) is finite, then decode_n(Y) is conv(Y), and thus a convex polytope. This proves the proposition.

[0250] Proposition 5.2

[0251] The class CPH has canonical representation in SAlg. This may be proven as follows. Let X be a convex polyhedron in ⁿ. Then X=L+(X ∩L^⊥), where L is its lineality space, defined as {{right arrow over (y)} | ∀{right arrow over (x)}∈S·{right arrow over (y)}+{right arrow over (x)}∈X} (it is a subspace of ⁿ) and L^⊥is the orthogonal subspace {{right arrow over (y)} | ∀{right arrow over (x)}∈L·({right arrow over (x)}, {right arrow over (y)})=0}. We shall use X₀for X ∩L¹⁹⁵in this proof. It is known that X₀is a convex polyhedron of lineality zero, that is, it contains no line. By A+B we mean {{right arrow over (a)}+{right arrow over (b)} | {right arrow over (α)}∈A,{right arrow over (b)}∈B}. Note the difference between the translate X−{right arrow over (x)}={{right arrow over (y)}−{right arrow over (x)} | {right arrow over (y)}∈X} and the set-theoretic difference X−x; we use {right arrow over (x)} to distinguish between them.

[0252] For X₀, define its vertices as x ∈X₀such that x ∉ conv(X₀−x). A direction is given by a vector {right arrow over (y)} and corresponds to the equivalence class of rays which are translate of each other. Note that each direction can be canonically represented by {right arrow over (y)} such that ∥{right arrow over (y)}∥=1. A direction {right arrow over (y)} is an extreme direction of X₀if for some vertex {right arrow over (x)}, the ray through {right arrow over (x)} in the direction of {right arrow over (y)}, l({right arrow over (x)}, {right arrow over (y)})={{right arrow over (x)}+λ•{right arrow over (y)}|λ≧0}, is a face of X₀. Since X₀is polyhedral of lineality zero, the set of vertices and extreme directions is finite. By (generalized) Caratheodory's theorem, every point {right arrow over (z)} of X₀is a combination of at most n+1 vertices and extreme directions,

[0253] λ₁{right arrow over (x)}₁+ . . . +λ_k{right arrow over (x)}_k+μ₁{right arrow over (y)}₁+ . . . +μ_m{right arrow over (y)}_m, where λ_i, μ_j≧0, λ₁+ . . . +λ_k=1, k+m≦n+1.

[0254] This suggests the following coding scheme. As before, for simplicity of exposition, we assume several coding relations, but they can be combined into one easily. It is to be understood that, in accordance with the mathematical definitions, all the concepts we use are first-order definable over the real field. We use relations LINEAL_k; each such relation contains a canonical representation (roughly, an orthogonal basis) of the lineality space of X, provided its dimension is k. That is, at most one of these relations actually contains some information. We then have the relations Vert and ExtDir for storing vertices and extreme directions of X₀. Finally, we have a relation Points that contains points that do not belong to L+X₀(recall that the coding scheme applies to any semi-algebraic set, so there could be such points, and we need to record them for the decode function).

[0255] Thus, to code (an arbitrary semi-algebraic) set X, we first note that its lineality space L(X)={{right arrow over (y)} | ∀{right arrow over (x)}∈X·{right arrow over (x)}+{right arrow over (y)}∈X} and its orthogonal L(X)¹⁹⁵={{right arrow over (y)} | ∀{right arrow over (x)}∈L(X)·({right arrow over (x)}, {right arrow over (y)})=0} are definable in FO+POLY (note that one can define the inner product in FO+POLY). Furthermore, for each k≦n, there exists a FO+POLY sentence dim_kexpressing the fact that L(A) is a subspace of ⁿand its dimension is k. This is true because in FO+POLY we can test linear independence; thus, we can check if there exists a system of k linearly independent vectors in L such that every vector in L is a linear combination of them.

[0256] Next, we show how to compute LINEAL_kand VertDir. We first sketch the coding scheme for LINEAL_k. The set L(X) is FO+POLY-definable. Assume that it is a k-dimensional linear space (which is tested by dim_k). Let Δ_nbe some canonically chosen n-dimensional simplex of diameter 1 such that the origin has barycentric coordinates $\left(\frac{1}{n},\dots ,\frac{1}{n}\right).$

[0257] Consider intersection of L(X) with 1-dimensional faces of Δ_n(unless L(X) is a line, in which case we consider its intersection with 2-dimensional faces of Δ_n). If the intersection is a point, we record that point; if it contains the whole face, we record both endpoints of the face. From the selected points, find a linearly independent subsystem (note that it can be done canonically, for example, by listing the vertices and 1-dimensional faces of Δ_nin some order). It then serves as a basis of L(X), which we use to code L(X). Note that L(X) can be reconstructed in FO+POLY from its basis.

[0258] Now that we have a representation for the lineal space of X, and a first-order formula defining L^⊥, we have a FO+POLY-formula defining X₀. Using it, we can compute vertices:

[0259] V(X₀)={x ∈ X₀| ∃x_i, . . . , x_n+1∈ X₀−x·x ∈conv({x₁, . . . , x_n+1})}.

[0260] Clearly, this is a first-order definition. Next, we find the set:

[0261] E(X₀)={{right arrow over (y)}|{right arrow over (y)}, {right arrow over (y)} =1 and ∃{right arrow over (x)}∈V (X₀)·l({right arrow over (x)}, {right arrow over (y)}) is a face }.

[0262] A subset Y of X₀is a face if every closed line segment in X₀with a relative interior point in Y has both endpoints in Y. Clearly, this is first-order definable, and thus E(X₀), the set of extreme directions of X₀, is first-order definable.

[0263] Given two sets V and E in ⁿ, by conv (V, E) we denote their convex hull, that is, the set of elements of ⁿdefinable as $\sum _{i=1}^k{\lambda }_i·{\overrightarrow{x}}_i+\sum _{j=1}^m{\mu }_j·{\overrightarrow{y}}_j,\mathrm{where}$ ${\overrightarrow{x}}_i\in V,{\overrightarrow{y}}_j\in E,\sum _{i=1}^k{\lambda }_i=1,{\lambda }_i,{\mu }_j\ge 0\mathrm{and}k+m\le n+1.$

[0264] Again, this can be done in FO+POLY.

[0265] We now describe code_n. For a semi-algebraic set X, it produces a tuple of relations:

[0266] (LINEAL₀, . . . , LINEAL_n, Vert, ExtDir, Point)

[0267] as follows. It first determines, by computing L(X), L(X)^⊥, V(X₀) and E(X₀) if it is the case that L(X) is a linear subspace of ⁿand:

[0268] X=L(X)+conv(V(X₀), E(X₀)).

[0269] If this is the case, then LINEAL_k, Vert, and ExtDir are produced as before, and Point is empty. Otherwise, Point coincides with X, and all other sets in the coding are taken to be ⁿ. From the description above it follows that code_nis FO+POLY-definable.

[0270] To compute decode_n, we first check if the first n+2 relations in the code coincide with ⁿ, and, if this is the case, output the last relation in the code. Otherwise, we use the nonempty LINEAL_kwith least k to compute a linear subspace L of ⁿgenerated by the vectors in LINEAL_k(if all LINEAL_kare empty, we let this subspace be {{right arrow over (0)}})). Next, compute Y=conv(Vert, ExtDir). Note that both are FO+POLY-definable. Finally, return L+Y ∩L^⊥; this is FO+POLY-definable also. This completes the proof

[0271] Let SLincomp be the class of compact (i.e., closed and bounded) semi-linear sets. We resolve this case for dimension 2, that is, for non-convex two dimensional polygons.

[0272] Proposition 5.3

[0273] The class SLinComp₂has canonical representation in SAlg₂. This may be proven as follows. An object in SLinComp₂is a finite union of convex polytopes in ²—this easily follows from cell decomposition. Any such object X admits a triangulation that does not introduce new vertices. Thus, the idea of the coding is to find the set V(X) of vertices and use as the code triples of vertices (not necessarily distinct) ({right arrow over (x)},{right arrow over (y)}, {right arrow over (z)}) with conv({{right arrow over (x)},{right arrow over (y)}, {right arrow over (z)}}) ⊂X. More precisely, a triple ({right arrow over (x)},{right arrow over (y)}, {right arrow over (z)}) belongs to code(X) if either {right arrow over (x)},{right arrow over (y)}, {right arrow over (z)} ∈ V(X) and conv({right arrow over (x)}, {right arrow over (y)}, {right arrow over (z)}) ⊂ X, or {right arrow over (x)}={right arrow over (y)}={right arrow over (z)} and there is no triple of elements of V(X) whose convex hull is contained in X and contains {right arrow over (x)}. Thus code(X) ⊂ ⁶. For decode, we use: $\mathrm{decode}\left(Y\right)=\bigcup _{\left(\overrightarrow{x},\overrightarrow{y},\overrightarrow{z}\right)\in Y}\mathrm{conv}\left(\left\{\overrightarrow{x},\overrightarrow{y},\overrightarrow{z}\right\}\right).$

[0274] Clearly, decode ° code is the identity, decode is first-order definable, and decode(Y) is compact and semi-linear when Y is finite. Thus, it remains to show that Y(X) is finite and FO+POLY-definable. The former is well-known. For the first-order definition of V(X) we use the following result. Let X be a finite union of polyhedra (in ⁿ) and let B_∈({right arrow over (x)}) be the ball of radius ∈ around z. Then for each {right arrow over (x)}, there exists δ>0 such that for any 0<∈₁, ∈₂<δ, we have: $\overrightarrow{x}+\bigcup _{\lambda >0}\lambda ·\left[\left(X\bigcap B_{{\in }_1}\left(\overrightarrow{x}\right)\right)-\overrightarrow{x}\right]=\overrightarrow{x}+\bigcup _{\lambda >0}\lambda ·\left[\left(X\bigcap B_{{\in }_2}\left(\overrightarrow{x}\right)\right)-\overrightarrow{x}\right]$

[0275] We denote this set by X({right arrow over (x)}). Define the equivalence relation ≡_xby {right arrow over (y)}≡_x{right arrow over (z)} if X({right arrow over (y)})=X({right arrow over (z)}). Then the vertices of X are precisely the one element equivalence classes of ≡_x. It is routine to verify that the above can be translated into a FO+POLY definition of vertices. This completes the proof.

[0276] Summing up, we have:

[0277] Theorem 5.1

[0278] There exists a recursively enumerable class of FO+POLY queries that captures the class of CPT (CPH and SLinComp₂, respectively) preserving queries.

[0279] Given the above-described teachings of the invention, an illustrative scenario is presented below in the context of FIGS. 4A and 4B whereby a query pre-processor of the invention performs query translation by providing an effective syntax query in response to a user-input query including certain geometric objects. The effective syntax query ensures that the same geometric properties associated with the objects in the original query are preserved in the results returned by the engine. In the following example, we show, using SQL syntax, how a user forms a query that preserves the property of being a union of triangles. Such a query would first compute vertices of its input, thereby creating a finite relation with six attributes (each vertex of a triangle is a point on the real plane and is thus described by two real numbers). The user then applies a query that was shown to be safe b the pre-processor and obtains another relation with six attributes. This relation is treated as coding of the output: each tuple describes a triangle in the output. Since there are finitely many six-tuples, the result of the query is a finite union of triangle. Below, we describe a safe query on finite relations with six attributes first, and then apply it to a geometric relation.

[0280] Referring to FIGS. 4A and 4B, a flow diagram is shown of a method of effective syntax query translation in the context of geometric region data according to an illustrative embodiment of the present invention. In step 410, the user 12 enters a query “SafeRelational” at the user interface 14. The query applies to a database schema with input table VERT, which is a finite relational table with 6 attributes: v1xval, v1yval, v2xval, v2yval, v3xval and v3yval. It is to be appreciated that “SafeRelational” outputs a table with six columns as well. In this example, the query “SafeRelational” entered by the user may be:

[0281] SELECT U1=R·X,

[0282] U2=R·X,

[0283] V2=R4·X,

[0284] W1=R5·X,

[0285] W2=R6·X,

[0286] FROM R R1, R R2, R R3, R R4, R R5, R R6, VERT

[0287] WHERE U1=VERT·v1xval+5 AND

[0288] U2=VERT·vlyval*2 AND

[0289] V1=VERT·v2xval+5 AND

[0290] V2=VERT·v2yval*2 AND

[0291] W1=VERT·v3xval+5 AND

[0292] W2=VERT·v3yval*2

[0293] In step 420, the user interface 14 sends the query to the query pre-processor 16 which accepts the query since it requires no modification to be made safe. In step 430, the user creates a schema Figure of type region (e.g., stores triangular regions in the a plane) and inputs some sample data. The user then, in step 440, forms query “SafeGeometric: Apply SafeRelational to Vertices(Regions)”.

[0294] In response, the query pre-processor generates a spatial query “SafeGeometric2,” which takes any region and returns the region obtained by taking all triangles making up the region, moving them 5 places to the right, and doubling their size. The user then, in step 450, applies “Safegeometric” to the schema Figure by sending “SafeGeometric2” to the database engine via the user interface.

[0295] Advantageously, in this scenario, the query pre-processor generates an effective syntax query (SafeGeometric2) that ensures that the geometric properties associated with the user's original query are preserved in the output returned by the spatial database engine.

[0296] Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention.