doc/canonisation.txt
author Julien Cristau <julien.cristau@logilab.fr>
Wed, 15 Jul 2015 10:55:38 +0200
changeset 766 050cceb6e78b
parent 384 3d869f4b93f6
child 875 9aa93973fb42
permissions -rw-r--r--
[pkg] Update debian packaging

Idées sur la canonisation
=========================

from ginco.rql.node_lib import Variable

def sort(canon_dict):
    canon_dict['all_variables'].sort()
    for l in canon_dict['restriction'].values():
        l.sort()

Exemple 1
---------

Formules équivalentes
`````````````````````

  Any N, N2 where N is Note, N2 is Note, N ecrit_par P1, P1 nom 'jphc', N2 ecrit_par P2, P2 nom 'ocy' ;
  Any Y, X  where X is Note, Y is Note,  X ecrit_par P1, P1 nom 'ocy',  Y ecrit_par P2,  P2 nom 'jphc' ;

Forme canonique
```````````````

N = Variable('N')
N2 = Variable('N2')
P1 = Variable('P1')
P2 = Variable('P2')

canon1 = {
 'all_variables': [N, N2, P1, P2],
 'selected' : [N, N2],
 'restriction' : {'is' :        [(N, 'Note'), (N2, 'Note')],
                  'ecrit_par' : [(N, P1), (N2, P2)],
                  'nom' :       [(P1, 'jphc'), (P2, 'ocy')]
                 }
}

N.name  = 'is_Note:ecrit_par:1' # 1 car c'est la première variable séléctionnée
N2.name = 'is_Note:ecrit_par:2' # deviner pourquoi 2 ...
P1.name = 'ecrit_par_jphc'
P2.name = 'ecrit_par_ocy'
sort(canon1)

Y = Variable('Y')
X = Variable('X')
P1 = Variable('P1')
P2 = Variable('P2')

canon2 = {
 'all_variables': [X, Y, P1, P2],
 'selected' : [Y, X],
 'restriction' : {'is' :        [(X, 'Note'), (Y, 'Note')],
                  'ecrit_par' : [(X, P1), (Y, P2)],
                  'nom' :       [(P1, 'ocy'), (P2, 'jphc')]
                 }
}

Y.name  = 'is_Note:ecrit_par:1'
X.name = 'is_Note:ecrit_par:2'
P1.name = 'ecrit_par_ocy'
P2.name = 'ecrit_par_jphc'
sort(canon2)


canon2 == canon1

Exemple 2
---------

Formules équivalentes
`````````````````````

  Note N WHERE N ecrit_le D, N ecrit_par P, P nom 'jphc', D day > (today-10);
  Note K WHERE K ecrit_le D, K ecrit_par Y, D day > (today-10), Y nom 'jphc';

Forme canonique
```````````````

N = Variable('N')
D = Variable('D')
P = Variable('P')
canon1 = {
 'all_variables': [N, D, P],
 'selected' : [N],
 'restriction' : {'is' :        [(N, 'Note')],
                  'day':        [(D, '> (today-10)')],
                  'ecrit_le' :  [(N, D)],
                  'ecrit_par' : [(N, P)],
                  'nom' :       [(P, 'jphc')]
                 }
}
N.name = 'is_Note:ecrit_le:ecrit_par:1'
D.name = 'ecrit_le:day_> (today-10)'
P.name = 'ecrit_par:nom_jphc'
sort(canon1)


K = Variable('K')
D = Variable('D')
Y = Variable('Y')
canon2 = {
 'all_variables': [K, D, Y],
 'selected' : [K],
 'restriction' : {'is' :        [(K, 'Note')],
                  'day':        [(D, '> (today-10)')],
                  'ecrit_le' :  [(K, D)],
                  'ecrit_par' : [(K, Y)],
                  'nom' :       [(Y, 'jphc')]
                 }
}
K.name = 'is_Note:ecrit_le:ecrit_par:1'
D.name = 'ecrit_le:day_> (today-10)'
Y.name = 'ecrit_par:nom_jphc'
sort(canon2)

canon1 == canon2


Exemple 3
---------

Formules équivalentes
`````````````````````

  Note N WHERE N ecrit_le D, D day > (today -10), N ecrit_par P, P nom 'jphc' or P nom 'ludal';
  Note K WHERE K ecrit_le D, K ecrit_par Y, D day > (today -10), Y nom in ('jphc', 'ludal');

Forme canonique
```````````````

N = Variable('N')
D = Variable('D')
P = Variable('P')
canon1 = {
 'all_variables': [N, D, P],
 'selected' : [N],
 'restriction' : {'is' :        [(N, 'Note')],
                  'day':        [(D, '> (today-10)')],
                  'ecrit_le' :  [(N, D)],
                  'ecrit_par' : [(N, P)],
                  'nom' :       [(P, 'jphc'), (P, 'ludal')]
                 }
}
N.name = 'is_Note:ecrit_le:ecrit_par:1'
D.name = 'ecrit_le:day_> (today-10)'
P.name = 'ecrit_par:nom_jphc'
sort(canon1)


K = Variable('K')
D = Variable('D')
Y = Variable('Y')
canon2 = {
 'all_variables': [K, D, Y],
 'selected' : [K],
 'restriction' : {'is' :        [(K, 'Note')],
                  'day':        [(D, '> (today-10)')],
                  'ecrit_le' :  [(K, D)],
                  'ecrit_par' : [(K, Y)],
                  'nom' :       [(Y, 'jphc'), (Y, 'ludal')]
                 }
}
K.name = 'is_Note:ecrit_le:ecrit_par:1'
D.name = 'ecrit_le:day_> (today-10)'
Y.name = 'ecrit_par:nom_jphc'
sort(canon2)

canon1 == canon2



Problèmes
---------

.1 Les paires de formules suivantes sont considérées comme identiques par
   l'algorithme ci-dessus alors qu'elles ne le sont pas:

Note N WHERE N ecrit_le D, D day > (today -10), N ecrit_par P, P nom 'jphc' or P nom 'ludal';
Note N WHERE N ecrit_le D, D day > (today -10), N ecrit_par P, P nom 'jphc', P nom 'ludal';

Note N WHERE N ecrit_le D, D day > (today -10), N ecrit_par P, P nom 'jphc' or P prenom 'ludal';
Note N WHERE N ecrit_le D, D day > (today -10), N ecrit_par P, P nom 'jphc', P prenom 'ludal';

donne comme restriction:

 'restriction' : {'is' :        [(K, 'Note')],
                  'day':        [(D, '> (today-10)')],
                  'ecrit_le' :  [(K, D)],
                  'ecrit_par' : [(K, Y)],
                  'nom_nom' :   [(Y, 'jphc', Y, 'ludal')]
                 }

.2 risque de collision dans les noms de variables non sélectionnées (un exemple ?).