User Tools
This is an old revision of the document!
====== Generalization ====== After the elaboration MAGIK, will answer if the query given by the user, is complete or not with respect to schema constraints and TC-statements. If it is not complete, MAGIK will try to generate the generalized and specialized query. In this page it is explained how works the generalization algorithm. {{ :magik-demo:user:query_approximation:generalization.png?nolink&650 |}} This schema illustrates all the steps that the generalization algorithm does. In order to be more comprehensive, we will use and example. Suppose that: <code sql> Q = A1, A2, A3, A4 </code> where A1, A2, A3 and A4 are atoms and we have these TC-statements <code sql> TC1 - A1(a) = A1(i) TC2 - A2(a) = A2(i), A3(i) TC3 - A3(a) = A3(i), A4(i) </code> Running MAGIK on this query and given database schema and TC-statements, we get that this query is <fc red>NOT COMPLETE</fc> At this point the generalization algorithm enter in action.\\ The idea is at each iteration remove all the incomplete atoms. The algorithm will stop if there is no other atoms that are incomplete (we said that it reaches a **fixed point**). ** __1st iteration__ ** Looking the 3 tc-statements that we have, we see that there is no information about A4 (you have to look on the left side of the equal) so, the algorithm removes from the query the atom A4. New query is <code> Q1 = A1, A2, A3 </code> Obviously Q1 is not equal to Q, so the algorithm will start another iteration. ** __2nd iteration__ ** Looking TC3 we have that the right part cannot be satisfied because we A4. Because of this, A3 will be removed from the query. New query is <code> Q2 = A1, A2 </code> Obviously Q2 is not equal to Q1, so the algorithm will start another iteration. ** __3rd iteration__ ** Looking TC3 we have that the right part cannot be satisfied because we A4. Because of this, A3 will be removed from the query. New query is <code> Q3 = A1 </code> Obviously Q3 is not equal to Q2, so the algorithm will start another iteration ** __4th iteration__ ** Looking TC3 we have that the right part cannot be satisfied because we A4. Because of this, A3 will be removed from the query. New query is <code> Q4 = A1 </code> Obviously Q4 is equal to Q3, so we reach a fix point and the algorithm stops. So the generalizated query Qgen is: <code> Qgen = A1 </code>
