Catégories / Syllodonnées
Romuald THION
La théorie des catégories
- maths contemporaines (post Bourbaki)
- cadre assez peu connu, voire ésotérique
- intellectuellement séduisant
Intérêt pour les informaticiens
- cadre fortement typé
- démarche constructive
- spécification versus implémentation
Un outil majeur de l'informatique théorique ... Qui aurait sa place en bases de données ?
Sommaire
Présentation informelle[modifier]
Une catégorie comme :
- une structure algébrique
- un cadre où faire des mathématiques
- une alternative aux ensembles
Dana S. Scott - Relating theories of the \-calculus (1980)
What we are probably seeking is a "purer" view of functions : a theory of functions in themselves, not a theory of functions derived from sets.
What, then, is a pure theory of functions ?
Answer : category theory.
Introduction[modifier]
Une catégorie C
- d'une collection d 'objets : A,B,C ...
- d'une collection de morphismes (ou flèches) : f,g,h ...
- pour chaque morphisme, un domaine (dom) et un codomaine (cod) \ f : A —> B (fortement typé)
- d'une opération de composition associant à chaque paire de morphismes / et g telles que cod(f) = dom(g) un morphisme go f : dom(f) cod(g)
Satisfaisant les deux conditions suivantes
- la composition est associative : (h o g) o f = h o (g o f)
- pour chaque objet A, un morphisme identité id A : A ^ A t.q. pour tout / : A -s- B on ait ids ° f = f et / o idA — f
Et rien d'autre . . .
Exemples
Bestiaire Catégorie Set Pfn Rel Mon Grp Q-Alg Pos CPO
Objets ensembles ensembles ensembles monoïdes groupes O-algèbres posets posets complets
Morphismes fonctions totales fonctions partielles relations binaires homomorphismes de monoïdes homomorphismes de groupes O-homomorphismes fonctions de monotones fonctions continues
Des implémentations de la définition de catégorie
Toutes ces catégories sont concrètes : les objets sont des ensembles munis de structures.
Pour ou contre ?[modifier]
En défaveur :
- trop abstrait (abstract nonsense)
- poids notationnel accablant
- rien de plus que dans Set (fondamentalement)
En faveur
- se débarasser des « détails » de Set
- « penser transformations »
- généraliser et réutiliser des constructions
Pratique des catégories[modifier]
Particularités de la pratique
- définition et raisonnement sur les morphismes
- rôle de l'unicité (l'universalité, la canonicité, l'optimalité . . . )
- utilisation de diagrammes pour décrire les propriétés
- abstraction de constructions ou propriétés sur des objets connus
Processus de catégorisation
Passer de = (en algèbre) à = (via morphismes)
La construction est « réussie » si on retrouve les mêmes lois
1. Raisonner sur les morphismes[modifier]
Démarche constructive On ne considère jamais l'égalité entre objets, seulement entre les morphismes.
Objet terminal
Un C-objet 1 est terminal si, pour tout C-objet A il existe un unique morphisme noté ! : A 1
On caractérise un objet via ses morphismes.
Isomorphisme
/ : A -> B est un isomorphisme si il existe g : B -» A tel que fog = ids et 50 / = idA-
Intuitivement, une transformation réversible qui préserve la structure.
2. Rôle de l'unicité[modifier]
Proposition : Les objets terminaux d'une catégorie sont isomorphes.
(Preuve) Soient A et B terminaux, et U : A -> B et \b • B ->•A les uniques morphismes entre ces objets.
U et \B sont composables : l ^ o ! ^ : A -> A. Or id a • A -> A existe (axiome) et est l'unique morphisme A -> A, car A est terminal. Donc, •B°-A = idA-
Similairement pour •.. •.. = ids'- A sont B' isomorphes.
Il n'y a (catégoriquement) aucun intérêt à distinguer les terminaux entre eux.
3. Diagrammes commutatifs[modifier]
FA VA GA F(f) G(f) FB V B GB Le carré commute G(f) °riA=riB° F(f) 4. Intuition dans Set Produit cartésien : A x B = {(a, b) | a E A A b e B} Comment définir le produit sans faire intervenir G, en considérant uniquement des transformations (fonctions) entre objets (ensembles)?
- première projection m : A x B ->• A 9 seconde projection 7r 2 : A x B ->• B
- la structure (A x B, m, m) est optimale
- quelques soient / : C A et g : C ->• B on peut construire
(f,g) :C ->• A x B définie par {f,g)(x) = (f(x),g(x)) 7T1 . 7T 2 A ^ i x B ^ B A I / I </>0> I C ^ La pratique Q Conclusion A categorical manifesto (Joseph Goguen) "This paper tries to explain why and how category theory is useful in
computing science, by guiving guidelines for applying seven basic categorical concepts : category, functor, natural transformation, limit, adjoint, colimit and comma category. Somes examples, intuition, and references are given for each concept, but completeness is not attempted." Utilisations
- théorie des graphes (catégorie « algèbre des chemins)
- théorie des automates (systèmes et comportement, bisimulation) o théorie des types (polymorphisme)
- programmation fonctionnelle (modèles du A - c a l c u l , effets) 9 substitutions de variables et unification 9 systèmes de réécriture
Une application « grand public » Catégories et programmation fonctionnelle a objet = type e.g., Bool, Int, Unit a morphismes = fonctions e.g., not : Bool —> Bool
- morphismes 1 A = constantes de type A
e.g., true, false : Unit —>• Bool a équations = même fonctions d'après la sémantique du language e.g., false = not o true
- endo-foncteurs = constructeurs de types
e.g., List ! C — y C
- transformations naturelles = fonctions polymorphiques
e.g., rev a • List(À)—ïList(À) Notions of computation and monads (Eugenio Moggi)
- monade : une construction catégorique
F ; C —' C , Tj : 1 c~^F, fx F o F—^F >
- utilisé dans le langage Haskell
- un sucre spécifique, commun à toutes les instances
Effets en programmation fonctionnelle
- partialité : F (A) = A + 1
- exceptions : F E (A) = A + E 9 non-déterminisme : F (A) = A*
- gestion d'états : F S (A) = {S x A ) s 9 lecteur : F E (A) = A E
Quid des bases de données ? Data Base Mappings and Monads : (Co)lnduction (Zoran Majkic)
Thus DB category, as a base category for the semantics of databases and mappings between them, is different from the Set category used dominantly for such issues, and needs the full investigation of its properties. Simplicial Databases (David I. Spivak) "The theory of relational databases is generally formulated within mathematical logic. V\/e provide a more modern and more flexible approach using methods from category theory and algebraic topology [...] Using an inefficient language can hamper ones ability to implement, work with, and reason about a subject."
Un goût de catégorification . . . gratuite
A calculus for collections and aggregates (Lellahi, Tannen) " This paper proposes a calculus for programming with collection data types and aggregate operations on such collections. From a philosophical perspective, such a calculus should play for database query languages the role that the lambda calculus plays for functional programming languages. From a practical perspective, such a calculus can form the foundation of an intermediate language : the surface syntax of queries can gets translated into terms of the calculus and the equational theory of the calculus derives program equivalences used in optimization.'"
Constructions catégoriques
- proposition d'un calcul sur les collections (cf. Nested Relational Calculus), dont la sémantique est donnée à l'aide de catégories,
- notion générale de collection : monades,
- notion générale d'aggrégats : algèbres sur un endo-foncteur, 9 théorèmes vérifiés dans les structures : pour l ' o p t i m i s a t i o n .
» un vocabulaire de concepts et de constructions, 9 une façon de penser morphismes,
- généraliser et transférer entre domaines.
Intérêt des catégories en BD ?
- Abstraire les constructions/transformations classiques des bases de données relationnelles e.g., contraintes d'intégrité, chase, réécriture ...
- Pour les appliquer/instancier sur de nouvelles structures e.g., graphes RDF, arbres XML, BD objets, NRC ...
Références
- Deutsch, A. ; Nash, A. & Remmel, J. B. The chase revisited. 2008. PODS sur l'universalité du chase
- Pierce, B. C. Basic Category Theory for Computer Scientists. 1991. Livre d'introduction de référence
- Lellahi, S. K. & Tannen, V. A Calculus for Collections and Aggregates. 1997. Un équivalent du X-calcul pour les BD
- Rydeheard, D. E. & Burstall, R. M. A Categorical Unification Algorithm. 1986. Algo de Martelli & Montanari décrit catégoriquement
- Rutten, J. J. M. M. Universal coalgebra : a theory of systems. 2000. Transpositions de concepts algébriques aux automates
- Moggi, E. Notions of computation and monads. 1991. Formalisation de la notion d'effet
- Liang, S. & Hudak, R Modular Monadic Semantics. 1998. Combiner modulairement les effets
- Goguen, J. A. A Categorical Manifesto. 1991.
Introduction Applications informatiques
Conclusion
L A T H É O R I E DES C A T É G O R I E S
Q U ' E S T - C E QUE C ' E S T ? Q U E L INTÉRÊT EN INFORMATIQUE ?
R o m u a l d THION
Liris - Équipe BD
Vendredi 22 avril 2011
a a
e
n S
a *
nnees
R. Thion Théorie des catégories 1
Page 1-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
Plan
O Introduction
Q Les catégories
Q La pratique
Q Applications informatiques
§ Conclusion
R. Thion Théorie des catégories
Page 2-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
O Introduction
Q Les catégories
^ La pratique
Applications informatiques
§ Conclusion
R. Thion Théorie des catégories
Page 3-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
Disclaimer
R. Thion Théorie des catégories
Page 4-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
Pourquoi cet exposé ?
La théorie des catégories
o maths contemporaines (post Bourbaki) o cadre assez peu connu, voire ésotérique » intellectuellement séduisant
R. Thion Théorie des catégories
Page 5-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
Pourquoi cet exposé ?
La théorie des catégories
o maths contemporaines (post Bourbaki) o cadre assez peu connu, voire ésotérique » intellectuellement séduisant
Intérêt pour les informaticiens
o cadre fortement typé ® démarche constructive
o spécification versus implémentation
R. Thion Théorie des catégories
Page 6-----------------------------------------------------
� Introduction Les catégories La pratique
Applications informatiques
Conclusion
Pourquoi cet exposé ?
La théorie des catégories
o maths contemporaines (post Bourbaki) o cadre assez peu connu, voire ésotérique » intellectuellement séduisant
Intérêt pour les informaticiens
o cadre fortement typé ® démarche constructive
o spécification versus implémentation
Un outil majeur de l'informatique t h é o r i q u e . . . ... Qui aurait sa place en bases de données ?
R. Thion Théorie des catégories
Page 7-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
Présentation informelle
Une catégorie c o m m e . . . 9 une structure algébrique
® un cadre où faire des mathématiques ® une alternative aux ensembles
R. Thion Théorie des catégories
Page 8-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
Présentation informelle
Une catégorie c o m m e . . . 9 une structure algébrique
® un cadre où faire des mathématiques ® une alternative aux ensembles
Dana S. Scott - Relating theories of the \-calculus (1980) What we are probably seeking is a "purer" view of functions : a theory of functions in themselves, not a theory of functions derived from sets.
What, then, is a pure theory of functions ?
Answer : category theory.
R. Thion Théorie des catégories
Page 9-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
^ Introduction
Q Les catégories
^ La pratique
Applications informatiques
§ Conclusion
R. Thion Théorie des catégories
Page 10-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Une catégorie C
® d'une collection d 'objets : A,B,C ...
9 d'une collection de morphismes (ou flèches) : f,g,h ...
9 pour chaque morphisme, un domaine ( dom ) et un codomaine
(cod) \ f : A —? B (fortement typé)
9 d'une opération de composition associant à chaque paire de morphismes / et g telles que cod(f) = dom(g) un morphisme
go f : dom(f) cod(g)
Satisfaisant les deux conditions suivantes
9 la composition est associative : (h o g) o f = h o (g o f)
O pour chaque objet A, un morphisme identité id A : A ^ A t.q.
pour tout / : A -s- B on ait ids ° f = f et / o idA — f
R. Thion Théorie des catégories
Page 11-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Une catégorie C
® d'une collection d 'objets : A,B,C ...
9 d'une collection de morphismes (ou flèches) : f,g,h ...
o pour chaque morphisme, un domaine ( dom ) et un codomaine
(cod) \ f : A —? B (fortement typé)
9 d'une opération de composition associant à chaque paire de morphismes / et g telles que cod(f) = dom(g) un morphisme
go f : dom(f) cod(g)
Satisfaisant les deux conditions suivantes
O la composition est associative : (h o g) o f = h o (g o f)
O pour chaque objet A, un morphisme identité id A : A ^ A t.q.
pour tout / : A -s- B on ait ids ° f = f et / o idA — f
Et rien d'autre . . .
R. Thion Théorie des catégories
Page 12-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Exemples
Bestiaire
Catégorie Objets Morphismes
Set
Pfn Rel
Mon Grp
Q-Alg Pos
CPO
ensembles ensembles ensembles monoïdes groupes
O-algèbres posets
posets complets
fonctions totales
fonctions partielles relations binaires
homomorphismes de monoïdes homomorphismes de groupes O-homomorphismes
fonctions de monotones fonctions continues
R. Thion Théorie des catégories
Page 13-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Exemples
Bestiaire
Catégorie Objets Morphismes
Set
Pfn Rel
Mon Grp
ensembles ensembles ensembles monoïdes groupes
fonctions totales
fonctions partielles relations binaires
homomorphismes de monoïdes homomorphismes de groupes
Q-Alg O-algèbres
O-homomorphismes
Pos
posets
fonctions de monotones
CPO posets complets
fonctions continues
Des implémentations de la définition de catégorie
Toutes ces catégories sont concrètes :
les objets sont des ensembles munis de structures.
R. Thion Théorie des catégories
Page 14-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Pour ou contre ?
En défaveur
» trop abstrait ( abstract nonsense) 9 poids notationnel accablant
9 rien de plus que dans S e t (fondamentalement)
R. Thion Théorie des catégories
Page 15-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Pour ou contre ?
En défaveur
» trop abstrait ( abstract nonsense) 9 poids notationnel accablant
9 rien de plus que dans S e t (fondamentalement)
En faveur
9 se débarasser des « détails » de S e t 9 « penser transformations »
9 généraliser et réutiliser des constructions
R. Thion Théorie des catégories
J
Page 16-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
(J Introduction
Q Les catégories
Q La pratique
Applications informatiques
§ Conclusion
R. Thion Théorie des catégories
Page 17-----------------------------------------------------
� Introduction La pratique
Applications informatiques Conclusion
Pratique des catégories
Particularités de la pratique
O définition et raisonnement sur les morphismes
Q rô le de l'unicité (l'universalité, la canonicité, l'optimalité . . . ) O utilisation de diagrammes pour décrire les propriétés
O abstraction de constructions ou propriétés sur des objets connus
Processus de catégorisation
Passer de = (en algèbre) à = (via morphismes)
La construction est « réussie » si on retrouve les mêmes lois
R. Thion Théorie des catégories
Page 18-----------------------------------------------------
� Introduction La pratique
Applications informatiques Conclusion
1. Raisonner sur les morphismes
Démarche constructive
On ne considère jamais l'égalité entre objets,
seulement entre les morphismes.
R. Thion Théorie des catégories
Page 19-----------------------------------------------------
� Introduction La pratique
Applications informatiques Conclusion
1. Raisonner sur les morphismes
Démarche constructive
On ne considère jamais l'égalité entre objets,
seulement entre les morphismes.
Objet terminal
Un C-objet 1 est terminal si, pour tout C-objet A il existe un unique morphisme noté ! : A 1
On caractérise un objet via ses morphismes.
Isomorphisme
/ : A -> B est un isomorphisme si il existe g : B -» A tel que fog = ids et 5 0 / = id A -
Intuitivement, une transformation réversible qui préserve la structure.
R. Thion Théorie des catégories
Page 20-----------------------------------------------------
� Introduction Applications informatiques
2. Rôle de l'unicité
Conclusion
Proposition
Les objets terminaux d'une catégorie sont isomorphes.
(Preuve ) Soient A et B terminaux, et U : A -> B et \ b • B ->• A les uniques morphismes entre ces objets.
U et \ B sont composables : l ^ o ! ^ : A -> A. Or id a • A -> A existe (axiome) et est l'unique morphisme A -> A, car A est terminal. Donc, •B°-A = idA-
Similairement pour = ids'- A sont B isomorphes.
Il n'y a (catégoriquement) aucun intérêt à distinguer les terminaux
entre eux.
R. Thion Théorie des catégories
]
Page 21-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
3. Diagrammes commutatifs
FA
VA GA
F(f) G(f)
FB
V B
GB
R. Thion Théorie des catégories
Page 22-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
3. Diagrammes commutatifs
FA
VA GA
F(f) G(f)
FB
V B
GB
Le carré commute
G(f) °riA=riB° F(f)
]
R. Thion Théorie des catégories
Page 23-----------------------------------------------------
� Introduction Applications informatiques
Conclusion
4. Intuition dans Set
Produit cartésien : A x B = {(a, b) | a E A A b e B}
Comment définir le produit sans faire intervenir G, en considérant uniquement des transformations (fonctions) entre objets (ensembles)?
o première projection m : A x B ->• A 9 seconde projection 7r 2 : A x B ->• B
9 la structure (A x B, m, m) est optimale
9 quelques soient / : C A et g : C ->• B on peut construire
(f,g) :C ->• A x B définie par {f,g)(x) = (f(x),g(x))
7T1 . 7T 2
A ^ i x B ^ B
A
I
/ I
</>0>
I C
R. Thion Théorie des catégories
Page 24-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
(J Introduction
Q Les catégories
^ La pratique
Q Applications informatiques
Q Conclusion
R. Thion Théorie des catégories
Page 25-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Applications informatiques
A categorical manifesto (Joseph Goguen)
"This paper tries to explain why and how category theory is useful in
computing science, by guiving guidelines for applying seven basic categorical concepts : category, functor, natural transformation, limit, adjoint, colimit and comma category. Somes examples, intuition, and references are given for each concept, but completeness is not attempted."
R. Thion Théorie des catégories
Page 26-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Applications informatiques
A categorical manifesto (Joseph Goguen)
"This paper tries to explain why and how category theory is useful in
computing science, by guiving guidelines for applying seven basic categorical concepts : category, functor, natural transformation, limit, adjoint, colimit and comma category. Somes examples, intuition, and references are given for each concept, but completeness is not attempted."
Utilisations
o théorie des graphes (catégorie « algèbre des chemins)
® théorie des automates (systèmes et comportement, bisimulation) o théorie des types (polymorphisme)
o programmation fonctionnelle (modèles du A - c a l c u l , effets) 9 substitutions de variables et unification 9 systèmes de réécriture
R. Thion Théorie des catégories
J
Page 27-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Une application « grand public »
Catégories et programmation fonctionnelle
a objet = type
e.g., Bool, Int, Unit
a morphismes = fonctions
e.g., not : Bool —> Bool
9 morphismes 1 A = constantes de type A
e.g., true, false : Unit —>• Bool
a équations = même fonctions d'après la sémantique du language
e.g., false = not o true
9 endo-foncteurs = constructeurs de types
e.g., List ! C — y C
9 transformations naturelles = fonctions polymorphiques
e.g., rev a • List(À)—ïList(À)
R. Thion Théorie des catégories
Page 28-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Une application « grand public »
Notions of computation and monads (Eugenio Moggi)
® monade : une construction catégorique
F ; C —' C , Tj : 1 c~^F, fx F o F—^F >
® utilisé dans le langage Haskell
9 un sucre spécifique, commun à toutes les instances
R. Thion Théorie des catégories
Page 29-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Une application « grand public »
Notions of computation and monads (Eugenio Moggi)
® monade : une construction catégorique
F ; C —' C , Tj : 1 c~^F, fx F o F—^F >
® utilisé dans le langage Haskell
9 un sucre spécifique, commun à toutes les instances
Effets en programmation fonctionnelle
9 partialité : F (A) = A + 1
9 exceptions : F E (A) = A + E 9 non-déterminisme : F (A) = A*
9 gestion d'états : F S (A) = {S x A ) s 9 lecteur : F E (A) = A E
R. Thion Théorie des catégories
Page 30-----------------------------------------------------
� Introduction Les catégories La pratique Applications informatiques Conclusion
(J Introduction
Q Les catégories
^ La pratique
Applications informatiques
§ Conclusion
R. Thion Théorie des catégories
Page 31-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Quid des bases de données ?
Data Base Mappings and Monads : (Co)lnduction (Zoran Majkic)
" Thus DB category, as a base category for the semantics of databases and mappings between them, is different from the Set category used dominantly for such issues, and needs the full investigation of its properties."
Simplicial Databases (David I. Spivak)
"The theory of relational databases is generally formulated within
mathematical logic. V\/e provide a more modern and more flexible approach using methods from category theory and algebraic topology [...] Using an inefficient language can hamper ones ability to implement, work with, and reason about a subject."
R. Thion Théorie des catégories
Page 32-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
Quid des bases de données ?
Data Base Mappings and Monads : (Co)lnduction (Zoran Majkic)
" Thus DB category, as a base category for the semantics of databases and mappings between them, is different from the Set category used dominantly for such issues, and needs the full investigation of its properties."
Simplicial Databases (David I. Spivak)
"The theory of relational databases is generally formulated within
mathematical logic. V\/e provide a more modern and more flexible approach using methods from category theory and algebraic topology [...] Using an inefficient language can hamper ones ability to implement, work with, and reason about a subject."
Un goût de catégorification . . . gratuite
R. Thion Théorie des catégories
Page 33-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
A calculus for collections and aggregates (Lellahi, Tannen)
" This paper proposes a calculus for programming with collection data types and aggregate operations on such collections. From a philosophical
perspective, such a calculus should play for database query languages the role that the lambda calculus plays for functional programming languages. From a practical perspective, such a calculus can form the foundation of an intermediate language : the surface syntax of queries can gets translated into terms of the calculus and the equational theory of the calculus derives program equivalences used in optimization.'"
R. Thion Théorie des catégories
Page 34-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
A calculus for collections and aggregates (Lellahi, Tannen)
" This paper proposes a calculus for programming with collection data types and aggregate operations on such collections. From a philosophical
perspective, such a calculus should play for database query languages the role that the lambda calculus plays for functional programming languages. From a practical perspective, such a calculus can form the foundation of an intermediate language : the surface syntax of queries can gets translated into terms of the calculus and the equational theory of the calculus derives program equivalences used in optimization.'"
Constructions catégoriques
® proposition d'un calcul sur les collections (cf. Nested Relational Calculus), dont la sémantique est donnée à l'aide de catégories,
9 notion générale de collection : monades,
9 notion générale d'aggrégats : algèbres sur un endo-foncteur, 9 théorèmes vérifiés dans les structures : pour l ' o p t i m i s a t i o n .
R. Thion Théorie des catégories
Page 35-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
La théorie des catégories
» un vocabulaire de concepts et de constructions, 9 une façon de penser morphismes,
9 généraliser et transférer entre domaines.
R. Thion Théorie des catégories
Page 36-----------------------------------------------------
� Introduction
Les catégories La pratique Applications informatiques Conclusion
La théorie des catégories
» un vocabulaire de concepts et de constructions, 9 une façon de penser morphismes,
9 généraliser et transférer entre domaines.
Intérêt des catégories en BD ?
9 Abstraire les constructions/transformations classiques des bases
de données relationnelles
e.g., contraintes d'intégrité, chase, réécriture ...
9 Pour les appliquer/instancier sur de nouvelles structures
e.g., graphes RDF, arbres XML, BD objets, NRC ...
R. Thion Théorie des catégories
Page 37-----------------------------------------------------
� Introduction Applications informatiques
Conclusion
o
o
o< •o
o o
• • / \
o o o
0
O O'
//
o
O
O •
o
O
Cec/' n'est pas une catégorie (R. Magritte)
R. Thion Théorie des catégories
Page 38-----------------------------------------------------
� Introduction Applications informatiques
Conclusion
Références
9 Deutsch, A. ; Nash, A. & Remmel, J. B. The chase revisited. 2008.
PODS sur l'universalité du chase
9 Pierce, B. C. Basic Category Theory for Computer Scientists. 1991.
Livre d'introduction de référence
9 Lellahi, S. K. & Tannen, V. A Calculus for Collections and Aggregates.
1997. Un équivalent du X-calcul pour les BD
9 Rydeheard, D. E. & Burstall, R. M. A Categorical Unification Algorithm.
1986. Algo de Martelli & Montanari décrit catégoriquement
9 Rutten, J. J. M. M. Universal coalgebra : a theory of systems. 2000.
Transpositions de concepts algébriques aux automates
9 Moggi, E. Notions of computation and monads. 1991. Formalisation de
la notion d'effet
9 Liang, S. & Hudak, R Modular Monadic Semantics. 1998. Combiner
modulairement les effets
9 Goguen, J. A. A Categorical Manifesto. 1991.
R. Thion Théorie des catégories
Page 39-----------------------------------------------------
