Logique du premier ordre

Algèbre relationnelle

• Relations : R(x₁,…,x_n) ⊆ D^X finies sur des attributs X et un domaine D.
• Représentés par des tables

On manipule les relartions via des opérateurs :

• Union ∪
• Différence \
• Produit Cartésien ×
• Projection Π
• Sélection σ
• Renommage ρ

Union

R ∪ S : les lignes qui sont à la fois dans R et S.

(SELECT * FROM Personnes1) UNION (SELECT * FROM Personnes2)

Différences

R \ S : les lignes qui ne sont que dans R.

(SELECT * FROM Personnes1) MINUS (SELECT * FROM Personnes2)

Produit Cartésien

R × S : on a les colonnes de R et de S et toutes les paires de tuples possibles.

(SELECT * FROM Personnes, Langages)

Sélection

σ_F(R) : on ne sélectionne que les tuples de R qui satisfont une formule F.

SELECT * FROM Personnes WHERE age>30

Join

R⋈_x = x′S souvent utilisé est un raccourci à σ_x = x′(R(x,y)×S(x′,y′))

Projection

Π_C(R) : on ne garde que les attributs (colonnes) c ∈ C dans R

SELECT nom,prénom FROM Personnes

Renommage

ρ_A → B(R) : on renomme l’attribut (colonne) A de R en B.

SELECT idPersonnes, 
       nom AS lname, 
       prénom AS fname, 
       âge AS age 
FROM Personnes

Correspondance

SELECT id, nom, prénom 
FROM ((SELECT id,nom,prénom,âge as x FROM Personnes1) UNION (SELECT id,nom,prénom,âge as x FROM Personne2)) 
WHERE x>30

Π_{id, nom, prénom}(σ_x > 30(ρ_{âge → x}(Personnes1∪Personnes2)))

pareil que

R(id,nom,prénom) ≡ ∃x.((P1(id,nom,prénom,x)∨P2(id,nom,prénom,x))∧x>30)

dans une interprétation où le prédicat P1 correspond à la table Personnes1 et P2 correspond à la table Personnes2.

Table de correspondance

Quelques différences

1. Dynamique différente
   • L’algèbre relationnelle décrit une procédure : comment transformer des relations en d’autres relations
   • La LPO : décrit des relations entre les différentes variables libres.
2. Modèles finis
   • Les bases de données n’utilisent que des tables **finies
   • Les interprétations des prédicats peuvent être infinies.
3. Symbole de fonctions
   • L’algèbre relationnelle n’utilise pas de fonction (sauf parfois dans σ(⋅))
4. Domaine d’interprétation
   • une interprétation en LPO fixe un domaine : ∀x(R(x,y)) n’a de sens que si le domaine de x est fixé !
   • l’algèbre relationnelle utilise le domaine actif, celui présent dans les tables.

Contraintes et théories

Contraintes de base de données :

• Unicité : UNIQUE(R,x) ≡ ∀xyz.R(x,y,z) ⇒ (∀uv.R(x,u,v)⇒(u=y∧v=z))
• Clé étrangère: FKEY(x,R,S) ≡ ∀xyz.R(x,y,z) ⇒ ∃u(S(x,u)).
• …

Une base de données respectant des contraintes peut être vue comme un modèle fini d’une théorie encodant ces contraintes !

Traduire vers LPO

1. σ_x = 4(Π_x, y(R(x,z)×S(y,t)))
2. σ_{x = ′Bob′}(R(x,z)∪S(x,z)) × T(a,b)
3. Π_y((T(x)×S(y))\R(x,y))
4. σ_{sqrt(x) > 5}(R(x,y,z) ∪ ρ_u → z(T(x,y,u))
5. Π_x(σ_{x = 3 ∧ y < 3}(R(x,y)×S(y,z)))