ognjen.savkovic@wikispace

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
{{:magik-demo:magik_logo.png?nolink&500|}}

====== 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 will remove 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 continue.

** __2nd iteration__ **

Now we know that A4 is incomplete. From this we can inferred that also A3 is not complete because A3 in complete iff also A4 is complete (TC3), but this is not the case. So 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 continue.

** __3rd iteration__ **

Now we know that A4 and A3 are incomplete. From this we can inferred that also A2 is not complete because A2 is complete iff also A3 is complete (TC2), but this is not the case. For this reason A2 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__ **

Now we have only A1. This atom is complete because there is no other atoms involved in its completeness (TC1). So A1 survived.\\
New query is 
<code>
Q4 = A1
</code>
Now 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>
ognjen.savkovic@wikispace

User Tools

Site Tools

Page Tools
