Langages de requêtes `a la SQL pour la découverte de r`egles dans

Langages de requetes a la SQL pour la decouverte de regles dans les bases de donnees

Langages de requetes a la SQL pour la decouvertede regles dans les bases de donnees

B. Chardin, E. Coquery, B. Gouriou, M. Pailloux, J.-M. Petit

3 juin 2013


Introduction

Objectifs

Decouvrir des regles dela forme X → Y

X ,Y ensembles d’attributs

A partir de donnees situees dans un SGBD relationnel

Specifiees de maniere declarative


Introduction

Comment

Langage RQL permettant de specifier:

l’acces et le formatage des donnees de la base via SQL

la forme des regles exprimee via une formule δ du langage RLX → Y si:

pour tous les tuples issus de la requete SQLtels que tous les attributs A ∈ X satisfont δ,tous les A ∈ Y satisfont egalement δ

Dans le prolongement de [AFPRW-LID’2011]


Introduction

Requete RQL

FINDRULES

OVER A1, ..., AkSCOPE t1 (SQL1), ..., tn (SQLn)

WHERE condition(t1, , ..., tn)

CONDITION ON A IS delta cond(A, t1, ..., tn);


Introduction

Exemple: Dependances fonctionnelles

{X → Y | ∀t1, t2 ∈ Emp(∀A ∈ X t1.A = t2.A)⇒ (∀A ∈ Y t1.A = t2.A)}

FINDRULES

OVER Empno,Lastname,Workdept,Job,Sex,Bonus

SCOPE t1,t2 Emp

CONDITION ON A IS t1.A = t2.A;


Introduction

Exemple: maximums locaux

FINDRULES

OVER <list of attributes >

SCOPE t1,t2,t3 sensors

WHERE t2.time = t1.time+interval ’1’ minute

AND t3.time = t2.time+interval ’1’ minute

CONDITION ON A IS t1.A < t2.A AND t2.A > t3.A;


Introduction

Plan

1 Introduction

2 (Safe)RL

3 Systemes de fermeture

4 Calcul d’une base en TRC / SQL

5 Experimentations

6 Conclusion


(Safe)RL

Formules TRC

Definition (Syntaxe)

ψ ::= R(t) | t1.A�t2.B | t.A�c | ¬ψ | ψ1 ∧ ψ2 | ∃t : X (ψ)

Definition (Semantique)

〈d , σ〉 |= R(t) if σ(t) ∈ d(R), R ∈ R

〈d , σ〉 |= t1.A�t2.B if σ(t1)(A)�σ(t2)(B)

〈d , σ〉 |= t.A�c if σ(t)(A)�c

〈d , σ〉 |= ¬ψ if 〈d , σ〉 6|= ψ

〈d , σ〉 |= ψ1 ∧ ψ2 if 〈d , σ〉 |= ψ1 and 〈d , σ〉 |= ψ2

〈d , σ〉 |= ∃t : X (ψ) if there exists a tuple t over Xsuch that 〈d , σt 7→t〉 |= ψ


(Safe)RL

Formules RL


δ ::= t1.A � t2.B | t.A � c | ¬δ | δ1 ∧ δ2


〈σ, ρ〉 |= t1.A�t2.B iff σ(t1)(ρ(A))�σ(t2)(ρ(B))

〈σ, ρ〉 |= t.A�c iff σ(t)(ρ(A))�c

〈σ, ρ〉 |= ¬δ iff 〈σ, ρ〉 6|= δ

〈σ, ρ〉 |= δ1 ∧ δ2 iff 〈σ, ρ〉 |= δ1 and 〈σ, ρ〉 |= δ2


(Safe)RL

Requetes SafeRL


Q = {X → Y | 〈ψ(t1, . . . , tn), δ(A, t1, . . . , tn)〉}

ψ est une formule du safe TRC (⊂ SQL)

A seule variable d’attribut libre dans δ

sch(Q) =⋂n

i=1 sch(ti )


〈d ,Σ〉 |= 〈ψ, δ〉 si pour tout σ t.q. 〈d , σ〉 |= ψ :

si ∀A ∈ Σ(X ) 〈σ, ρA7→A〉 |= δalors ∀A ∈ Σ(Y )〈σ, ρA 7→A〉 |= δ

ans(Q, d) = {Σ(X )→ Σ(Y ) | 〈d ,Σ〉 |= 〈ψ, δ〉}


(Safe)RL

Exemple: Dependances fonctionnelles

{X → Y | ∀t1, t2 ∈ Emp(∀A ∈ X t1.A = t2.A)⇒ (∀A ∈ Y t1.A = t2.A)}

En SafeRL:

{X → Y | 〈Emp(t1) ∧ Emp(t2) , t1.A = t2.A〉}


(Safe)RL

Exemple: Maximums locaux

En SafeRL:

{X → Y | 〈 Sensors(t1) ∧ Sensors(t2) ∧ Sensors(t3)∧t2.time = t1.time + 1 ∧ t3.time = t2.time + 1,t1.A < t2.A ∧ t2.A > t3.A 〉}


Systemes de fermeture

1 Introduction

2 (Safe)RL



5 Experimentations

6 Conclusion



Regles et fermeture

Ensemble de regles F = {X1 → Y1, . . . ,Xn → Yn}

Systeme de fermeture associe:

X+F = {A ∈ U | X →F A}

CL(F ) = {X ⊆ U|X = X+F }

Inf-irreductibles de F :IRR(F ) = {X ∈ CL(F ) |

∀Y1,Y2 ∈ CL(F ), X = Y1 ∩ Y2 ⇒ X = Y1 ∨ X = Y2}



Base du systeme de fermeture

Une base B de CL(F ) est telle que IRR(F ) ⊆ B ⊆ CL(F )

Base = contexte en FCA

Dependances fonctionnelles: base = agree set

Algorithmes existants pour calculer des couvertures du systeme deregles


Calcul d’une base en TRC / SQL

1 Introduction

2 (Safe)RL



5 Experimentations

6 Conclusion



Systeme de fermeture pour Q = 〈ψ, δ〉

Z satisfait F si pour tout X→ Y ∈ F , soit X 6⊆ Z, soit Y ⊆ Z,i.e. Z = Z+

F

Definition

CLQ(d) = {Z ⊆ sch(Q) | Z satisfait ans(Q, d)}

.



Base BQ(d)

Definition

BQ(d) =⋃σ t.q.

〈d ,σ〉|=ψ

{{A ∈ sch(Q) | 〈σ, ρA7→A〉 |= δ}

}

Proposition

BQ(d) est une base du systeme de fermeture CLQ(d).



Transformation d’attributs

Calcul de BQ(d) en une requete SQL:

renommage d’attributs

nouveau schema:⋃

i∈1..n{〈A, i〉 | A ∈ sch(ti )}nouvelles variables d’attribut Ai et une variable de tuple t

transformations:

rw(δ): ti .A t.Ai

rw(σ)(t) = t avec t(〈A, i〉) = σ(ti )(A).rw(ρ)(Ai ) = 〈ρ(A), i〉rw(ψ) = ∃t1 : sch(t1), . . . ,∃tn : sch(tn)

(ψ ∧∧

A∈sch(Q)

n∧i=1

t.Ai = ti .A)



Calcul de BQ(d) via le TRC

Proposition

BQ(d) =⋃

rw(σ) s.t.〈d ,rw(σ)〉|=rw(ψ)

{{A ∈ sch(Q) | 〈rw(σ), rw(ρA 7→A)〉 |= rw(δ)}

}

BQ(d) =⋃

t∈ans({t|rw(ψ)},d)

{{A ∈ sch(Q) | 〈σt 7→t, rw(ρA 7→A)〉 |= rw(δ)}

}


Experimentations

1 Introduction

2 (Safe)RL



5 Experimentations

6 Conclusion


Experimentations

Prototype: architecture


Experimentations

Performances / #attributs (DF)

0

1000

2000

3000

4000

5000

6000

10 20 30 40 50 60

Cu

mu

lati

veex

ecu

tion

tim

e(i

ns)

Number of attributes

Rules generationSQL query

(a) Rule generation

0

2

4

6

8

10

12

14

10 20 30 40 50 60

Cu

mu

lati

veex

ecu

tion

tim

e(i

ns)


(b) Zoom on SQL queries durations

Figure : Execution time for functional dependencies


Experimentations

Performances / #attributs (max. loc.)

0200400600800

10001200140016001800

20 40 60 80 100

Cu

mu

lati

veex

ecu

tion

tim

e(i

ns)


Rules generationSQL query

(a) Rule generation

0

0.2

0.4

0.6

0.8

1

1.2

1.4

20 40 60 80 100

Cu

mu

lati

veex

ecu

tion

tim

e(i

ns)


(b) Zoom on SQL queries durations

Figure : Execution time for local maximums rules


Conclusion

1 Introduction

2 (Safe)RL



5 Experimentations

6 Conclusion


Conclusion

Conclusion

Langage declaratif pour la decouverte de regles

Possibilite en pratique d’utiliser la syntaxe SQL pour

Acceder / formater les donneesSpecifier la forme des regles

Requete les donnees directement dans le SGBD

Calcul d’une base via une requete SQL

Utilisation d’algorithmes existants pour le calcul d’unecouverture de l’ensemble des regles.

Documents

Langages de requêtes `a la SQL pour la découverte de r`egles dans