Optimization
[ Back ] [ Home ] [ Next ]

Constraints as Data
Potential Apps
Query by Example
Query by Example
Query by Example
More Examples
Model and Language
Main Features
Hosting Iterative Lang.
Constraint Calculus
Constraint Calculus
Polynomial Complexity
Query Evaluation
Functionality
Optimization
Optimization
Optimization
Optimization
Implemented Apps
Implemented Apps

Optimization by Approximation-based Filtering and Indexing (cont.)

Consider All_trajectories, which is a variable of type SET<DC_LIN*>, i.e., a set of references to trajectories. The Fairfax county is assumed to be represented as a polygon, i.e., as a C_LIN CST object Fairfax_area in variables x and y. The above query can be directly expressed in CCUBE as

   SELECT traj         
   INTO {Set<DC_LIN*>} result
   FROM All_Trajectories AS {DC_LIN*} traj
   WHERE  MUT_SAT(*traj, Fairfax_area )             // Note: MUT_SAT 
                                                    //   on DC_LIN

or, if MUT_SAT is expressed, in turn, as an iterative query:

   SELECT traj          
   INTO {Set<DEC_LIN*>} result
   FROM All_Trajectories AS {DC_LIN*} traj
   WHERE SELECT MUT_SAT(*segment,Fairfax_area)  // Note: MUT_SAT 
         INTO {Some}                            //   on C_LIN
         FROM *traj AS {C_LIN*} segment         // SELECT returns
                                                //  True of False       

which is an expensive query if evaluated directly, because it iterates over all trajectories, and for each trajectory it iterates over its linear pieces, performing a SAT test for each.

To exemplify the use of the CCUBE built-in index structures called inverse grouping and indexed approximation grouping, we show an example of how the given query can be re-written to run much more efficiently.

presentation created by Victor E. Segal