Using Constraint Programming in Selection Operators for Constraint Databases

Using Constraint Programming in Selection Operators for Constraint Databases María Teresa Gómez-López ⇑ , Rafael M. Gasca Department of Languages and Computer Systems, University of Seville, Spain Keywords: Complex data Optimal query evaluation Selection Operator Constraint Databases Constraint Programming abstract Constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficient retrieval of classic data, but for complex data a made-to-measure solution combined with expert systems for each type of problem are necessary. Therefore, in the same way as commercial solutions of relational databases permit storing and querying classic data, we propose an extension of the Selection Operator for complex data stored, and an extension of SQL language for the case where both classic and constraint data need to be managed. This extension shields the user from unnecessary details on how the information is stored and how the queries are evaluated, thereby enlarging the capacity of expressiveness for any commercial database management system. In order to minimize the selection time, a set of strategies have been proposed, which combine the advantages of relational algebra and con-straint data representation. 1. Introduction Databases are used for the management of information in software applications. However there are certain types of data that cannot be represented as classic data and treated with commercial solutions, such as software mining, web analytics, medicine, biology and chemistry data (Poelmans, Ignatov, Kuznetsov, & Dedene, 2013a; Poelmans, Kuznetsov, Ignatov, & Dedene, 2013b). Constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). The problem remains that no commercial database exists that permits constraints to be handled in the same terms as classic data, and which shields the user from how the information is stored and how the queries are evaluated. It implies that, for each type of problem, a made-to-measure solution combined with expert systems are necessary. The use of the constraint data type to represent these different types of problems permits the abstraction to use the data in the same sense as in the relational databases, where the same type of data can be used for different semantics. The main contributions of this paper can be summarized as follows: (1) An extension of SQL language to evaluate the Selection Operator for complex data; (2) The proposal for a set of strategies to minimize the evaluation time; (3) A library to extend commercial databases for constraint data and Selection Operator; (4) It is applied to a project for the Human Accident Risk Management in Construction. The industrial development of the proposal has been elaborated in a real project called Victor R&D Project. The Victor Project (Visual Interface ConTrol Object Rules) (Victor-Project, 2013)isa case study where classic and complex data are managed at the same time in an application, and the efficiency of the data selection is essential for security reasons. This project focuses on the Human Accident Risk Management in Construction, where it is possible to model static objects at design time (video cameras, ditches, cranes, machinery zones, ...), dynamic objects whose position is sent from the sensors at runtime (persons, machinery, ...), and rules that describe the safe or dangerous relation between the objects. The various objects have locations that can be described by means of points, lines, polygons, or irregular zones, and for different floors, in general by means of constraints (Fig. 1). The data retrieval over this data implies the evaluation of queries such as: Which machines are in a zone of security on floor three? or Is there anybody with a level of risk higher than 8 from a ditch? In order to describe the data model of the project, the level of floor can be represented by means of an integer, and the type of zone or the type of ⇑ Corresponding author. Tel.: +34 954553871; fax: +34 954557139. E-mail addresses: [email protected] (M.T. Gómez-López), [email protected] (R.M. Gasca). URLs: http://www.lsi.us.es/~mayte (M.T. Gómez-López), http://www.lsi.us.es/ ~gasca (R.M. Gasca). static element can be stored by means of an enumerate type, but the problem remains of how to represent and to ascertain whether a piece of machinery is inside or outside of a zone, or how to represent the risk between two objects using only operations over the database. The development of this type of query implies a made-to-measure implementation depending on the problem. However, would it be possible to extend the Selection Operator to query complex types of data represented by means of constraint, in the same sense as classic data is treated in relational databases? Optimal data selection is essential since there are many objects, and a delay in identifying potential accidents can be very negative for the safety of the personnel. For this reason, the main objective of this paper is to improve the constraint data retrieval, by combining the advantages of the commercial relational databases in order to delegate the evaluation of the classic data to the database management. This paper is organized as follows: Section 2presents how complex data represented by constraints can be stored using Constraint Databases. Section 3extends the syntax and the semantics of the Selection Operator of relational algebra for constraint data. Sections 4 and 5 explain how the queries can be evaluated by describing the implementation details based on Constraint Satisfaction Problems, and the strategies to improve the evaluation time. Section 6presents several examples of queries and their average evaluation times, and shows how the use of our solution improves the computation time for various selections over constraints. Section 7reviews the most relevant proposals in this area. Finally, conclusions are drawn and future work is proposed. 2. Constraint Databases background Constraints have already been related to databases by means of the so-called Constraint Databases (CDBs) (Revesz, 2001). Constraint Databases were introduced in 1990 in a paper by Kanellakis and Revesz (1990), creating a new line of research (Revesz, 1995Revesz, 1998). Although there are several proposals related to CDBs, the definitions of CDBs and how to store the constraints used in this paper is the proposal called LORCDB (Gómez-López, Ceballos, Gasca, & Valle, 2009), which is based on Chapter 2 of Revesz (2001) with certain variants. In Section 7the different solutions found in the literature are analysed and why the LORCDB solution is used to extend the Selection Operator in this paper. The necessary definitions are included in this work to facilitate the understanding of the paper. AConstraintcan be expressed by means of a Boolean combination of equations and inequations that follows the metamodel presented in Gómez-López, Gasca, and Reina-Quintero (2011). Aconstraint is a Boolean combination (not, and, or) of comparison (<; 6;P;...) among equations (þ;;;=). For example: {a>b AND NOT c + 1 = b} When constraint data need to be stored in a database, classic attributes and constraint attributes can be combined in the same relation, where the tuples of the relation are called constraint k-tuples: Aconstraint k-tuple with the variables x 1 ;...;x k is a finite conjunction u 1 ^...^ u N where each u i , for 1 6i6N, is either a constraint, such that {x j ¼Constant}, where x j 2{x 1 ;...;x k }, called aClassic Attribute,oran X -constraint over the variables x 1 ;...;x k which do not correspond to a classic attribute, and is called a constraint Attribute. When a set of constraint k-tuples are joined in a relation, it is called a constraint relation: Aconstraint relation is defined as a finite set of Classic Attributes and constraint Attributes.Aconstraint relation of arity k, is a finite set r¼fw 1 ;...;w M g, where each w j for 1 6j6Mis a constraint k-tuple over {x 1 ;...;x k }. The corresponding formula is the disjunction w 1 _..._w M , such that w j ¼ u 1 ^...^ u N for each u i is a constraint k-tuple, where 1 6i6N. If in each w j 2rthere is a u i such that {x=Constant}, where xis the same variable in all u i belonging to different w j , and xdoes not appear in the rest of the u i of the same w j , then the xvariable is a classic attribute, while the rest of the variables belong to constraint attributes. A relation has classic attributes if and only if: u ij is a u i 2 u 1 ^...^ u N and w j 2w 1 _..._w M , such that w j ¼ u 1j ^...^ u Nj , and therefore a constraint relation will have a classic attribute (x) if: 9 u ij  8 j21::Mji21::N;f u ij x¼c j g^ 8 t21::N^t–i^ u tj ðx 1 ;...;x k Þ^xRfx 1 ;...;x k g where c j is a constant, Mthe number of tuples, and Nthe number of attributes (columns). This implies that if an equality relation exists between a variable and a constant (the same variable in all tuples) in all constraint ktuples, and that if this variable does not appear in another constraint attribute, then this variable is a classic attribute, since it follows relational algebra. An example is presented in Fig. 2, where the constraint relation is composed of one constraint attribute and two classic attributes. In the example, there are two variables (xand y) that appear in all the tuples which have an equality relation with a constant, and these variables cannot appear in the rest of the attributes. Therefore, a Constraint Database is a finite collection of constraint relations composed of Classic and constraint attributes. From the previous definitions, it is clearly necessary to extend the types of attributes for CDBs. The definitions of three different types of attributes are used: Fig. 1. Example of objects of risk management. Classic attribute (at i ): at i belongs to the n-tuples of a relation (1 6i6n), where at i is of a type permitted by standard SQL, for example Integer,String,Date,... This type of attribute can be represented as a constraint, such as {at i = constant}, since relational databases only permit attributes with atomic values. These attributes can be used as a primary or foreign key. Constraint attribute (at c i ): at c i belongs to the n-tuples of a relation where at c i is of Constraint type defined as a constraint k-tuple with the variables v 1 ... v k . A constraint attribute represents a relation between the set of variables v 1 ... v k . Therefore, for our proposal, a constraint relation is formed by classic and constraint attributes. Constraint-variable attribute (at c i .v j ): v j is a variable which belongs to a constraint attribute at c i . This attribute is represented by: <Constraint  column  name>.<Variable  name> where <Variable  name>is not a classic attribute, but it is a variable of a constraint stored as a value inside a column. A column of the database (constraint attribute) can have several constraints, and these constraints can be defined over different variables. Derived form theses definitions, The storage proposal in Gómez-López et al. (2009) presents a framework called LORCDB (Labelled Object–Relational Constraint Database). LORCDB is focused on storing the constraints as objects indexed by the variables contained within, the minimum and maximum value of each variable for every constraint, what is the box consistency for each variable (the minimum-bounding hyper-rectangle) (Granvilliers, Goualard, & Benhamou, 1999). By storing the maximum and minimum values, the query evaluation becomes more efficient, as explained in the following sections. 3. Extending the syntax and semantics of the Selection Operator for constraint data One of the main objectives of this paper is to define a language to describe the constraint data for the selection of data in a database, independent of the semantics of the problem. Since SQL is the standard language for relational databases, we propose an extension to the meaning of selection for constraint data. For the extension, it is necessary to propose: a new syntax; the semantics of the possible comparators; and a way of evaluating the queries in order to optimize the data selection. Examples where a Selection Operator can be used to select data include: Is any security zone being crossed by any machine? What degree of risk does the ditch ðx5Þ 2 þðy12Þ 2 6 36 ^2<¼x^x<¼8 pose for a particular person? What objects are to the north of the person located at the point (6;8)? In general, the Selection Operator has to return the tuples that satisfy a condition, which can relate an attribute either with a constant or with attributes of different relations. An example of a selection in SQL is: Select R. ⁄ from R, R’ where R.At 3 hR’.At 2 The main difference in the syntax, when constraint data is added, is that the attributes can be constraints, and hence the comparison (h) must allow the comparison between constraints. One of the goals of this paper is to define what ’’to compare constraints’’ means, what types of comparison can be defined between constraints, how we can evaluate the queries, and how the efficiency of query evaluation can be improved. In this paper we propose various strategies to improve the evaluation, such as the box consistency of constraints, relational algebra, and Constraint Satisfaction Problems. 3.1. Syntax of the Selection Operator The syntax of the query with a selection of tuples in standard SQL is: SELECT <list  of  attributes (t 1 ) [,list  of  attributes (t 2 ), ...]> FROM <list  of  tables (t 1 ,t 2 ;...)>WHERE predicate The predicate is a condition where the attributes of tables involved can participate, where a Boolean expression is composed of logic operators v ¼{^;_} and comparison operators h¼{<; 6;>;P;¼;<>} with the form: a 1 hc 1 v a 2 hc 2 v  v a n hc n where a i represents an attribute (one of the three proposed for CDBs) and where c i is another attribute or a constant of the same domain as that of a i . The differences added for the extension of SQL for constraints are: the type of attributes involved, which can be constraint attributes; and the predicate to define the condition. The parameter <list  of  attributes (t i )>represents various types of projections over the attributes of table t i . These attributes can be classic attributes, constraint attributes, or constraint-variable attributes. The predicate that we propose extends the standard, adding to the classic attributes the comparison among constraint attributes, constraint-variable attributes, and constraint attributes for a set of variables (at, at c ,at c .variable). The operators to compare classic attributes (<; 6;>;P;¼;<>) are also used to compare constraint-variable attributes, but the operators to compare constraint attributes are extended to compare the constraints (<; 6;>;P;¼; <>; &;;#;;). When only a number of the variables of the constraints are to be taken into account in the selection process, the syntax permits either the specification of these variables with the token FOR, or a combination of this comparison with the equality of other variables. A detailed clarification of the following syntax is given in the subsection below: Fig. 2. Example of constraint k-tuples and constraint relations. predicate :¼condition jcondition [’AND’ j’OR’] predicate; condition :¼at COMPARATOR [at jconstant] jat c CONSTRAINTCOMP [at c jconstraint] jat c CONSTRAINTCOMP ’(’[at c jconstraint] ’FOR’ ’{’listOfVariables’}’ [’AND’ listAtVarEqual]’)’ jat c ’.’variable COMPARATOR [at c ’.’variable j constant]; COMPARATOR :¼’<’j’6’j’>’j’P’j’¼’j’<>’; CONSTRAINTCOMP :¼’<’j’6’j’>’j’P’j’¼’j’<>’j ’&’j’’j’#’ j’’j’’; listOfVariables :¼Variable jVariable ’,’ listOfVariables; listAtVarEqual :¼at c ’.’Variable ’=’ at c ’.’Variable jat c ’.’Variable ’=’ at c ’.’Variable ’AND’ listAtVarEqual; 3.2. Semantics of the Selection Operator for constraint attributes In the same way as the comparison operators have been modified, the semantics has to be adapted. In this work, the comparison defined between constraints is related to the comparison between the extensional values that the constraints involved represent in an intensional way. As stated earlier, the constraint data is an intensional way to represent a set of extensional data, therefore their comparison operators must compare all the extensional data that they represent. Some of the operators used are those defined in Chapter 2 of Marriott and Stuckey (1998) that describe the relation between the extensional values of the variables represented by means of constraints in a similar way to operations between sets. Other papers, such as Lee, Unger, Zheng, and Lee (2011), also use the comparison operators for the containment scope of mobiles in covered zones. We propose the comparison which ascertains whether the values that represent a constraint are included in the values of another constraint (,#;;), or that both sets of values of the variables have at least one solution in common (&). Moreover, the semantics of the classic operator for the comparison in relational algebra have also been added (h¼(<; 6;>;P;¼;<>)). The semantics defined in this paper for these operators describes whether the values that represent a constraint are greater than, smaller than, equal to or different from the values of another constraint. The typical topological relations (disjoint, meet, overlap, ...) can be performed with the comparison operators that we propose. The advantage of incorporating these operators, however, is that they can be used in any type of problem or selection, by permitting the use of the same operators in a general purpose database, and not only for spatio-temporal data. We also find it interesting to compare a set of the variables involved only in the constraints, for this reason we have included a special syntax: ’(’[at c jconstraint] ’FOR’ ’{’listOf- Variables’}’’)’. This sentence allows the definition of the set of variables that we want to include in the comparison. Before explaining how the evaluation of the comparison is performed, it is necessary to clarify that if the involved constraints in the comparison are not defined over the same variables, then the comparison has no sense. For this reason, we define a new operation over the variables that describes the syntactic equality between variables of different constraints: Definition 3.1. Syntactic Equality between variables of constraints: Let C a and C b be two constraints where A¼ {a 1 ;a 2 ;...;a n } represents the variables of C a , and B¼{b 1 ;b 2 ,...;b m } represents the variables of C b .Ifa i 2A, and b j 2B, then a i  S b j is true if both variables are syntactically equal, which means that they have the same name. If two variables of different constraints are syntactically equal, it does not imply that they are the same variable and represent the same extensional values in both constraints. For example, if two separate objects are defined in a zone of the space, both objects are described by the same variables (x,y). However there is no solution for both objects for the same values of xand y, although it is possible to define a comparison between them, for example if one object is higher than the other. This means that although the variables of two constraints of different tuples are syntactically equal, they are not semantically equal because they represent symbolically different extensive values. 4. Evaluation of Selection Operator for data selection In order to compare the values represented by means of constraints, and to evaluate the queries over the possible constraint attributes, we propose the use of Constraint Satisfaction Problems because their resolution is more efficient and general (for any number of variables) than the computation geometry algorithm used in other proposals. Depending on the related constraints in the evaluation, and the comparator of the Selection Operator, various models are created to evaluate the query. Moreover, classical mathematics models should not be applied to solve geographical problems, then new ways to represent and solve them are necessary (Malpica, Alonso, & Sanz, 2007). In order to understand the models, it is necessary to clarify what a Constraint Satisfaction Problem is, to determine whether a comparison between two constraints is true or false, and to determine whether the tuple with the constraint will form part of the output constraint relation. Constraint Satisfaction Problems (CSPs) represent a reasoning framework consisting of variables, domains and constraints. Formally, it is defined as a triple hX,D,Ciwhere X¼{x 1 ;x 2 ;...;x n }is a finite set of variables, D¼{dðx 1 Þ;dðx 2 Þ,...;dðx n Þ} is a set of domains of the values of the variables, and C¼{C 1 ;C 2 ,...;C m }is a set of constraints. Each constraint C i is defined as a relation R on a subset of variables V¼{x i ;x j ;...;x k }, called the constraint scope. The relation Rmay be represented as a subset of the Cartesian product dðx i Þdðx j Þ... dðx k Þ. A constraint C i ¼ðV i ;R i Þ specifies the possible values of the variables in Vsimultaneously in order to satisfy R. Let V k ¼{x k 1 ,x k 2 ;...;x k l } be a subset of X, and an l-tuple ðx k 1 ;x k 2 ;...;x k l Þfrom dðx k 1 Þ;dðx k 2 Þ;...;dðx k l Þcan therefore be called an instantiation of the variables in V k . An instantiation is a solution only if it satisfies the constraints C. In order to solve a CSP, a combination of search and consistency techniques is commonly used (Dechter, 2003). The consistency techniques remove inconsistent values from the domains of the variables during or before the search. Several local consistency and optimization techniques have been proposed as ways of improving the efficiency of search algorithms. The technique for comparison of the constraints proposed in this paper uses model-driven evaluation of CSPs. This implies building a CSP to ascertain whether each constraint stored in the relation satisfies the condition defined in the query, which determines whether each tuple of the input constraint relation will form part of the output constraint relation, and hence a CSP is modelled and solved. The inclusion of each tuple within the group of those that satisfy the condition, and therefore its inclusion in the output relation, depends on the condition and on the existence of a solution for the CSP. The comparison between two constraints is defined if there is a syntactic equality between the variables of the constraints (Definition 3.1) and if the variables are defined over the same domain. Otherwise, the result of the evaluation will be false. Given that a 1 ...a n represent the variables of constraint C a , and b 1 ...b m represent the variables of C b , then the created models for the comparison operators are: C a <C b is true if, for all a i ja i  S b j , the maximum value of the solutions of a i always remains smaller than the minimum value of b j , and if for all the variables of C a , there is a syntactic equality in C b and vice versa. This definition can be extended to C a >C b . In order to determine whether C a <C b , a CSP is built where all the variables a i of C a , that also participate in C b (which means that a i  S b j ), are renamed as a i 0, thereby building a new constraint C a 0. This creation is necessary since these two constraints have to be able to assume different solutions in order to compare the values of the solutions. If a CSP is built with the variables both syntactically and semantically equal, then the solutions obtained are the values of a i where both constraints are satisfiable. In order to ascertain whether all the solutions of C a for the variables a i  S b j are smaller than the solutions of C b , a created CSP will determine whether there is a solution where this does not happen. If a solution is found, then the output of the evaluation for the predicate C a <C b is false, and true otherwise. This means that the formula: 8 a i 2A; 8 b j 2Bja i  S b j )(a i <b j ) is transformed into: :ð9 a i 2A;9b j 2Bja i  S b j )a i >b j _a i ¼b j Þ. This transformation obviates the study of the entire search space of the solutions, since it is only necessary to find a value where a i Pb j is true. A CSP is built as follows: A 0 ¼{a 0 1 ;a 0 2 ,...;a 0 n } B¼{b 1 ;b 2 ;...;b n } C 0 a ^C b 8 a i 2A 8 b j 2Bja i  S b j )add {(a i 0>b j _a i 0¼b j )} If there exists a solution for the CSP, then C a <C b for these tuples returns false, since it means that not all the values of the variables of C a are smaller than those in constraint C b , since there exists a value that satisfies the opposite condition. If no solution is found for the CSP, then the comparison C a <C b returns true. An example is shown in Fig. 3, where C a <C b is true. This type of selection can be used to query spatial objects, for example to ascertain what objects are to the southwest of another object. C a 6C b is true if, for all the variables a i  S b j , the maximum value of a i is always smaller than or equal to the minimum values of b j . This definition can be extended to C a PC b . The construction of this CSP is as follows: A 0 ¼{a 0 1 ;a 0 2 ,...;a 0 n } B¼{b 1 ;b 2 ;...;b n } C 0 a ^C b 8 a i 2A 8 b j 2Bja i  S b j )add {(a i 0>b j )} If there is a solution for this CSP, then C a 6C b returns false, and true otherwise. C a ¼C b is true if all the solutions of C a are also solutions of C b and vice versa. In this case, it is possible that two syntactically different constraints can be semantically equal. For this comparison, the variables are not renamed for the CSP, since it is necessary to know whether the solutions of C a are also solutions of C b . The CSP built in this case is: A¼{a 1 ;a 2 ;...;a n } B¼{b 1 ;b 2 ;...;b n } (:C a ^C b )_(C a ^:C b ) If there is a solution for the CSP, then C a =C b returns false, and true otherwise. The operation <>, which describes the inequality of two constraints, can be evaluated with the same construction of the CSP used for the ¼operator. The main difference when using this operator is that if there is a solution for the CSP, the comparison returns true, and false otherwise. C a &C b is true if there is a solution that satisfied both constraints, where all the variables are syntactically equal. In this case, the model of the CSP is: A¼{a 1 ;a 2 ;...;a n } C a ^C b If a solution is found for this CSP, the operation C a &C b returns true, and false if no solution is found. C a #C b is true whether all the solutions of C a are also solutions of C b . In order to analyse the inclusion operator in constraints, both constraints have to be defined over the same variables. Therefore, since C a and C b are two constraints where A¼ {a 1 ;a 2 ;...;a n } are the variables of C a and C b , then C a #C b is equal to the implication (C a !C b )(Marriott & Stuckey, 1998). This comparison determines if all the solutions of C a are also solutions of C b , although it is possible that C b has solutions that do not belong to C a . In order to avoid having to analyse all the solutions of C a by checking whether they are solutions of C b , the CSP is modelled to search for solutions where the constraint is not satisfiable. The evaluation of the conditional predicate C a #C b therefore corresponds to the formula: :ð9 a i 2A ðC a ^:C b ÞÞ and the model of the CSP is: A¼{a 1 ;a 2 ;...;a n } C a ^:C b If any solution is found for the CSP, the evaluation returns false, and true if no solution is found. There is an example shown in Fig. 4 where the constraint C a is included in the constraint C b (all the solutions of C a are solutions of C b ). This definition can be extensible for C a C b . C a C b returns true if all the solutions of C a are also solutions of C b , and C b has at least one solution which does not belong to Fig. 3. Example where C a <C b . y x Fig. 4. Example of C a #C b . C a . As for the previous operator, both constraints have to be defined over the same variables. In this case, one CSP is modelled in order to determine whether C a #C b , and another CSP is modelled to determine whether there is a solution for C b that does not belong to C a : A¼{a 1 ;a 2 ;...;a n } C b ^:C a If there is a solution for the CSP, then C a C b returns true, and false otherwise. This definition can be extended to C a C b . The operators above can be modified to compare only one set of the variables, defined syntactically with the word FOR, and to establish equality relations between certain variables: C a <(C b FOR {b d ;...;b h }) is a variant of the comparison ’<’ which returns true if for all the variables a i  S b j such that b j 2 {b d ,...;b h }, the maximum value of a i is smaller than the minimum value of b j . This comparison carries out a projection over those variables that belong to the predicate {b d ;...,b h }. This assumes that the variables of C a that do not belong to {b d ;...;b h } hold no significance for this operation. In this case, the constraints C a and C b do not require all the variables to be syntactically equal, and the comparisons between the variables of the predicate are included in the CSP. The model of the CSP has the form: A 0 ¼{a 0 1 ;a 2 ’, ...;a 0 n } B¼{b 1 ;b 2 ;...;b n } C 0 a ^C b 8 a i 2A 8 b j 2fb d ;...;b h gja i  S b j )add {(a 0 i >b j _a 0 i ¼b j )} If there is any solution for the CSP, the comparison returns false, and true otherwise. An example is presented in Fig. 5a where the selection is over the variable y, and the predicate is C a <(C b FOR fyg). This predicate queries whether all the values of the variable y in C a are smaller than the solutions for this variable in C b , where the values of the variables {x;z} are not important. However, for the predicate C a <(C b FOR fxg) and the same example, the evaluation output is false. This definition can be extended to the operations 6;>;&and P. An easy way to illustrate this type of selection is in an application which refers to objects in space, for example, in the determination of whether there is any object physically located above another. A further variant of this type of comparison for variables is illustrated in ascertaining whether the solutions of a constraint are smaller than the solutions of another constraint for a fixed group of variables. In Fig. 5b an example is shown, in which, for the values of xwhere C a and C b are satisfiable, the value of yto satisfy C a is smaller than the value of yto make C b satisfiable. The conditional predicate for this example is: C a <(C b FOR {y}AND C a .x¼C b .x). It assumes that the general syntax to fix the semantic equality is: C a <(C b FOR {b d ;...;b h }AND C a .v 1 =C b .v 1 AND ... AND C a .v i ¼C b .v i AND ...AND C a .v k ¼C b .v k). where v i R{b d ;...;b h } and means that the model of the CSP is: A 0 ¼{a 0 1 ;a 2 ’, ...;a n 0} B¼{b 1 ;b 2 ;...;b n } C 0 a ^C b 8 a i 2A 8 b j 2fb d ;...;b h gja i  S b j )add {(a 0 i >b j _a i 0¼b j )} 8 v 2f v 1 ;...; v k gj v  S a i 0^ v  S b j )add {a i 0¼b j } If the CSP finds a solution, then the comparison will be false, and true if no solution is found. The remaining operators can be extended for the use of FOR in a similar way, although ;#;;;&;¼and <> cannot be extended to an equality relation between variables since these operators define a relation where the variables of these two constraints are equal, and hence stating that the variables are equal would be redundant. 5. Strategies for improving the selection of constraint data In order to define a methodology to obtain an efficient evaluation of the Selection Operator for the data retrieval, a strategy inspired by spatial databases has been designed to handle each part (conditions) of the predicate in a specified order. The evaluation for the selection consists of obtaining a horizontal subset of tuples for an input relation. In order to obtain the output relation, a sequence of steps are executed, within each of which the tuples that do not satisfy a part of the predicate are eliminated. When a constraint is stored, the box consistency of each variable (minimum-bounding hyper-rectangle) in each constraint is also stored in one of the three tables presented in Section 2. This information leads to a more efficient evaluation of the queries. We address the problem of an efficient query evaluation of the Selection Operator that follows a set of steps which is the result of an exhaustive analysis of the problem. These steps are determined by the type of attributes involved, which include: 1. Classic attribute: For an input relation R, the predicate over the classic attributes has to be analysed according to relational algebra, and a new constraint relation must be obtained. This is possible since the constraints and relational data can be differentiated. (a) (b) a b b a Fig. 5. Example of selection over certain variables. 2. Constraint-variable attribute: The second step is related to constraint-variable attributes, where these attributes represent numeric variables whose maximum and minimum values are stored. The implementation of this type of attribute is analysed in Subsection 5.1. 3. Constraint attribute: For the constraint attributes, two types of treatments are used, box consistency and the solving of CSPs. The implementation of this type of attribute is analysed in SubSection 5.2. Classically, the object retrieval for spatio-temporal objects is formed of two steps: The filter step to quickly prune the indexed objects, and the refinement step where the exact representations of candidates using computational geometry algorithms are inspected. In our proposal, the filter step is executed by means of the box consistency analysis. There are a significant number of papers that study the benefits of the use of the box consistency and how to improve the evaluation time based on interval-based solvers (Chabert & Jaulin, 2009; Araya, Trombettoni, & Neveu, 2010; Trombettoni, Papegay, Chabert, & Pourtallier, 2010; Chabert, Trombettoni, & Neveu, 2005). There exist other proposals, such as the use of internal rectangles (Lin & Tan, 2003), but they cannot be used directly in our problem because a constraint can represent more than one object, and hence the internal rectangle indexation would need adapting. Reduction of the space of analysis for two dimensions has been proposed in papers such as Brisaboa, Luaces, Navarro, and Seco (2010), Brisaboa, Luaces, Navarro, and Seco (2013). Our proposal of a refinement step is based on the use of Constraint Programming to support any type of problem or number of variables, thereby obviating the made-to measure algorithm, which depends on the type of problem to solve and the number of variables. 5.1. Evaluation of a constraint-variable attribute in a selection The predicates related to these attributes can define a comparison between two constraint-variable attributes, a constraint-vari- able attribute and a classic attribute, or a constraint-variable and a constant attribute. These three types of comparison can be considered as only two types, since the comparison between a constraintvariable and a classic attribute, or a variable and a constant are equivalent. The comparison between a constraint-variable and a classic attribute can be studied as a comparison between a constraint-variable attribute and a constant where the value of the constant is different for each tuple. The various cases are handled by means of the analysis of the box consistency. For example, if the tuples of an output relation have to satisfy a condition where the variable ais smaller than the value 5, and the domain of this variable for a constraint is 10..15, then the tuple with this variable does not belong to the output relation. In certain cases, this elimination of tuples can be performed without creating a CSP, simply by carrying out a classic query for classic attributes, since the maximum and minimum value of the variables are stored. However, in order to be sure that the value can be instantiated, a CSP has to be created. An example of predicate for constraint-variable attributes can be. r Relation:c>Relation:d (R), where Ris the relation shown in Fig. 6.As the output of the selection, the first tuple of the relation is obtained {x¼5^y¼2^aþb>c^dþa<8}, and since the second and fourth tuples have the variable d, this implies that the relation between variables cannot be defined. With respect to the third tuple, the constraint d>ccþ1 appears, hence the condition r Relation:c>Relation:d (R) cannot be satisfied. 5.2. Evaluation of constraint attributes for data selection For the constraint attributes, we first propose an analysis of the box consistency in order to determine whether the predicate involved satisfies the condition over the constraint attributes. If this analysis is insufficient, a CSP has to be created and solved. Box consistency analysis: If the minimum and maximum values that a variable can take are analysed, it is possible to infer whether two constraints satisfy a condition, for example, for the comparison between the constraints C a and C b , both defined over the variables v 1 and v 2 , where the ranges are C a ( v 1 :½5..15, v 2 :½20..30) and C b ( v 1 :½20..25, v 2 :½40..55). If the predicate is C a <C b , then it is possible to ensure that the evaluation of the comparison is true. However if the predicate is C a #C b , then the evaluation of the comparison is false. All the combinations are studied in depth in this section. Building CSP: Although there are cases where it is possible to determine whether a tuple belongs to an output relation using only the analysis of the box consistency, other cases do exist where a CSP has to be built and solved. Returning to the previous example, if the domain of the variables is C a ( v 1 :½5..15; v 2 :½20..30) and C b ( v 1 :½2..25; v 2 :½10..55), and the predicate is C a #C b , although the possible solutions of the variables of C a are included in the possible solution of the variables of C b , it is not possible to ensure that the predicate is satisfiable. An example where the ranges of sets of variables are included in another constraint, but not the solutions, is shown in Fig. 7. In these cases, it is necessary to create and solve CSPs with both constraints as explained in SubSection 3.2. In the work of Veltri (2001), the idea of approaching the constraints using box consistency is introduced in order to improve the evaluation time in the query evaluation for CDBs. Despite the limitations of that study, it defines the operations and types of relation between linear constraints to represent polygons with only two dimensions. Our approach is based on this proposal but is defined for all types of polynomial constraints, not only polygons, and for any number of dimensions. Moreover, the aforementioned paper by Veltri adds the description of each minimumbounding rectangle in each constraint with the ^Boolean operator, while our proposal stores the minimum and maximum values of the minimum-bounding rectangle as classic numeric data with the characteristics of relational algebra. This way of storing the box consistency obviates the building and solving of CSPs for the Fig. 6. Example of the Selection Operator with constraint-variable attributes in the predicate. tuples when the box consistency can infer the evaluation of the query. The various types of relations between two constraints related to the ranges of their variables (shown in Fig. 8) include: (a) All the possible values of a variable v for the constraints C a are always smaller than the values of the variable v of the constraint C b . (b) The greatest value of a variable v for the constraint C a is equal to the smallest value of this variable in the constraint C b . (c) A variable v can take a set of values that satisfy both constraints C a and C b , and the values of v satisfying C a are smaller than the values satisfying C b . (d) For the variable v , all the values for the constraint C a are also solutions of C b , although C b can have more solutions than can C a . (e) All the possible values of v to satisfy C a are also values that satisfy C b , and vice versa. These relations between domains can help towards determining the relations between constraints as described in Section 3.2, since modelling and solving CSPs is rendered unnecessary in some cases. With a generalization for nvariables, Min  Value C j ð v i Þrepresents the minimum value of the variable v i that satisfies constraint C j , which can be 1 or a numeric value, and Max  Value C j ð v i Þ represents the maximum value of the variable v i that satisfies constraint C j , which can be þ1 or a numeric value. Let v 1 ... v n be the variables of the constraints C a and C b , and let Min  Value C a ð v 1 Þ;..., Min  Value C a ð v n Þbe the minimum values of the variables of the constraint C a . Let Max  Value C a ð v 1 Þ;..., Max  Value C a ð v n Þbe the maximum values of each variable for the constraint C a , let Min  Value C a ð v 1 Þ;..., Min  Value C b ð v n Þbe the minimum values of the variables of the constraint C b , and let Max  Value C b ð v 1 Þ;..., Max  Value C b ð v n Þbe the maximum values of the variables for the constraint C b . In the cases where the clause FOR is included in the condition, in order to determine the subset of variables involved in the comparison, only these variables are analysed. If the key words AND and FOR are used, the semantic equality between the variables is established. The various cases depend on the operation between the constraints C a and C b , and the ranges of their variables are shown in Table 1. This table represents the evaluation of the comparison between two constraints (C a and C b ), depending on the relation of their box consistencies. Sometimes it is possible to know if the comparison will be true or false,although sometimes will be necessary to build a CSP, as explained in SubSection 3.2. In Fig. 9, some examples of relations of satisfaction using box consistency are shown, highlighting two constraints with a shaded area. In Fig. 9a, an example is given where C a <C b is satisfiable, which means that all the values of the variables v 1 and v 2 that satisfy C a , are smaller than the values of these same variables that satisfy C b .InFig. 9b, an example is presented where C a <C b FOR { v 2 } is satisfiable, since all the values of v 2 that satisfy C a are smaller than the values of this variable that satisfy C b . Fig. 10apresents an example where the projection obtained from the box consistency of C a is included in the projection of the box consistency of C b , and where all the solutions of C a are also solutions of C b . On the other hand, in Fig. 10b, an example is presented where, although the range of the variables for C a is included in the range of C b , not all the solutions of C a are solutions of C b . The example shown in Fig. 10c is similar, since the range of the variables for C a is equal to the range of C b , but not all the solutions of C b are solutions of C a . For the inclusion and equal operations, by means of using the ranges it is possible to ensure that two constraints do not satisfy a condition. However, to ensure that the constraints satisfy the condition, it is necessary to build and solve a CSP. If there is no FOR clause, then this analysis is performed for all the variables, either until one of them fails to satisfy a condition, or until all the variables had been analysed. If finally the study returns true, then the tuples, where the constraints are, belong to the output relation. 5.3. Scope of applicability of our proposal As a consequence of the model presented and the strategies of evaluation, the scope of application of our proposal is limited by three characteristics: Constraint Programming. We have decided to use Constraint Programming since: it is a very mature area that has been applied to a wide range of problems, and with high level of complexity; it uses propagation techniques to reduce the search space in an efficient way; there are numerous tools and algorithms to model and solve problems, and; it permits an easy Cb x y Ca Fig. 7. Example of C a C b . (a) (c) (b) (d) (e) Fig. 8. Types of relations between the ranges of the variables of two constraints. Table 1 Evaluation of comparison using box consistency prototypes. C a ;C b Fig. 8(a) Fig. 8(b) Fig. 8(c) Fig. 8(d) Fig. 8(e)  <  true false CSP CSP false  6  true true CSP CSP false  {>; P}  false false false CSP false  ¼  false false false false CSP  <>  true true true true CSP  &  false CSP CSP CSP CSP  {;#;;}  false false false CSP CSP definition of the complex data using a wide range of constraints, such as implication constraints, disjunctive constraints, reified constraints, global constraints, and channelling constraints. The range of Constraints. This limitation is centred on the capacity of their expressiveness as allowed by the grammar and type of variables. The grammar of the Constraints constitutes the formal representation of the relations between the data involved. The limitations of use of the proposal appear when the information to be stored cannot be represented by numerical constraints over the defined domains, or the operator is not included in this proposal, such as when a relation among two variables is described by means of a trigonometric function. The limitation of the data domain and the operations that can be employed are established by the solver used for the Constraint Programming Problem, explained in Section 4. Most of the commercial solvers maintain the capacity to include Float, Integer, Sets, and Boolean variables in the model, thereby making it possible to cover a significant number of problems and their business data constraints. Complexity of resolution of the CSP. In the worst case scenario, the evaluation time depends on the complexity of the resolution of the CSP. This has been analysed in great depth over recent decades (Cheeseman, Kanefsky, & Taylor, 1991), and depends on two parameters: the width of the graph and the order parameter. On one hand, the width of the graph represents the relation between the constraints: the tractability in CSPs is due to the structure of the constraint network, where the tree-structured CSPs have polynomial complexity (linear with respect to the number of variables, and quadratic with respect to the cardinal of the domain of the variables). On the other hand, the order parameter, defined as the ratio of the number of forbidden tuples to the total number of possible combinations, determines the partition of the problem space into under-constrained, overconstrained and just-constrained problems. In the first two cases, the problems are scalable, but in just-constrained problems, a significant increase in solving cost could occur and the scalability would not be possible (Krzysztof, 2003). For these reasons, no affirmation about the efficiency or scalability in a generic way can be given by our proposal, since our framework permits any type and number of Constraints defined with numerical variables, and therefore the evaluation time depends on the specific problem. However, in order to reduce the complexity and allow the scalability of the problems, we have proposed a set of strategies shown experimentally in the following section. 6. Example of use and experimental results for the Selection Operator In order to extend SQL and include the explained strategies in the expert system, this proposal has been implemented as a Java Library component, called CDB  Package, which shields the user from unnecessary details on how the information is stored and how the queries are evaluated. With a very similar code to that used for any database connection in Java TM , the user defines the relational database connection, writes the sentence and executes the query. The difference is that this package includes a CDB class that creates, if they have not been created before, the three tables to index the constraints and variables, and establishes the connection with the database and the type of database management system. In the method executeQuery of class CDB, the steps described in Section 5are implemented. The current database management systems permitted are Oracle and MySQL. CDB  Package includes the solver for the CSP used is Rochart and Jussien (xxxx), which is also a Java library for CSPs, although it can be enlarged to other solvers such as JSolver TM (ILOG, xxxx). CDB  Package has been developed and used in the Victor R&D Project (Victor-Project, 2013). Connection con = DriverManager.getConnector ("jdbc...", ...) String cmd = "Select ...."; CDB bd = new CDB (con, "Oracle"); PreparedStatement stmt = db.executeQuery (cmd); Based on the Victor Project, we have tested how the various strategies that we propose reduce the evaluation time. In order to test queries with this Selection Operator, two different tables are used to represent the various zones of construction and the static objects modelled. The Victor Project only contains two-dimen- sional objects, but the same methodology can be used for any (a) (b) Fig. 9. Example of relations between constraints by means of their box consistency. Fig. 10. Example of constraints with included ranges.