\documentclass[a4paper]{article}
\usepackage{epsfig}
\psfigdriver{dvips}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{vmargin}            % redéfinir les marges
\setmarginsrb{2cm}{2cm}{2cm}{2cm}{0cm}{0cm}{0cm}{1cm}
% Marge gauche, haute, droite, basse; espace entre la marge et le texte à
% gauche, en  haut, à droite, en bas

\usepackage{amsmath,amssymb,verbatim}

\usepackage{supertabular}

\usepackage{listings}

\usepackage{url}

\newcommand\sautligne{
\par\vspace{12pt}
}
\title{Bases de données \\ Forum}
\author{Sam \textsc{Zoghaib} \\ Tahina \textsc{Ramananandro}}
\date\today

\begin{document}
\maketitle
\section{Principe}
\subsection{Définition}
Un \emph{forum} est un système de communication informatique où des utilisateurs lisent et \emph{postent} des \emph{messages}, lisibles par tous.
\sautligne
Les messages sont regroupés par thème, dans des \emph{groupes de discussion}, ou en anglais \emph{newsgroups}, ou, dans le jargon normalien, \emph{contis}\footnote{abrév. de \emph{continuum}, c'est-à-dire ensemble de messages formant \emph{continuité} de thème}. Un message peut appartenir à plusieurs contis, mais doit appartenir à au moins l'un d'eux.
\sautligne
Mais les messages sont aussi organisés en arbres, grâce à une notion de \emph{père-fils}, qui définit \emph{une thread}\footnote{ou, selon certains, \emph{un thread}}, ou \emph{fil de discussion}. Une thread peut s'étendre arbitrairement sur plusieurs contis.
\sautligne
En plus de la notion de père-fils, il existe une notion plus générale de \emph{référence} d'un message à un autre (comme une bibliographie), assez rarement utilisée dans un autre usage que la relation père-fils. (Le père d'un message est le dernier message référencé par celui-ci).
\subsection{Structure d'un message}
Un message est constitué d'\emph{une en-tête}\footnote{Ou, selon certains, \emph{un en-tête}}, suivie du \emph{corps}. L'en-tête définit le message par des \emph{attributs}, ou \emph{champs}, de la forme \verb+ATTRIBUT: valeur1, valeur2, ...+, tandis que le contenu du corps est libre.
Il existe un certain nombre d'attributs obligatoires, sachant que tous ceux commençant par \verb+X+ sont toujours facultatifs. Les principaux champs obligatoires sont :
\begin{itemize}
\item \verb+DATE+ : la date du message
\item \verb+NEWSGROUPS+ : l'ensemble des contis auxquels appartient le message.
\item \verb+FROM+ : le pseudonyme du posteur
\item \verb+SENDER+ : l'identité <<physique>> du posteur
\item \verb+SUBJECT+ : le sujet\footnote{A ne pas confondre avec un \emph{thème}.} du message
\item \verb+REFERENCES+ : l'ensemble des messages auxquels ce message fait référence ; la dernière référence est le père du message.
\end{itemize}
Le message est toujours identifié par un identifiant unique, le \emph{message-ID}.
\subsection{Exemples}
Exemples d'en-têtes de messages (l'attribut \verb+DATE+ est omis), ainsi que l'organisation correspondante en termes de contis et threads :

\clearpage

\begin{tabular}{lc}
  \begin{minipage}{6cm}

\begin{verbatim}
Message-Id: 18
NEWSGROUPS: foo, bar
FROM: zoghaib
SUBJECT: essai
REFERENCES:
 
Message-Id: 19
NEWSGROUPS: foo
FROM: ramanana
SUBJECT: truc
REFERENCES: 18
 
Message-Id: 20
NEWSGROUPS: foo
FROM: zoghaib
SUBJECT: machin
REFERENCES: 18, 19
 
Message-ID: 21
NEWSGROUPS: bar
FROM: ramanana
SUBJECT: test
REFERENCES: 18
 
Message-ID: 22
NEWSGROUPS: foo
FROM: zoghaib
SUBJECT: tu t'es trompé
REFERENCES: 19, 21
\end{verbatim}
  \end{minipage}
& La figure n'est pas prête.\\
\end{tabular}
\sautligne
Attention, les contis préexistent aux messages (c'est-à-dire que le fait de poster un message contenant un nom de conti inconnu ne va pas automatiquement créer ledit conti).
\subsection{Modération : déplacement, ou blast}
Entre le post, tâche commune, et la création de contis, tâche d'administration, il existe une tâche intermédiaire, dite de \emph{modération}, visant à contrôler l'appartenance de messages à des contis en fonction de leur contenu. Cette tâche est accomplie par des \emph{modérateurs}. Elle se manifeste par le \emph{déplacement} de certains messages d'un conti à un autre, déplacement que l'on appelle aussi \emph{blast} car les messages incriminés disparaissent de leur conti d'origine.

On peut blaster :
\begin{itemize}
\item un message isolé, depuis un conti vers un autre
\item un fil entier, mais connexe dans un même conti (c'est-à-dire que le fil est <<coupé>> dès que l'on trouve un message fils hors du conti considéré), vers un autre conti
\end{itemize}

Mais le blast requiert des permissions spéciales (tout le monde ne peut pas blaster).
\begin{itemize}
\item Le modérateur qui blaste doit avoir la permission de déplacer des messages depuis le conti source considéré.
\item Il existe des contis qui sont en \emph{lecture seule}, c'est-à-dire que l'on ne peut pas y poster. Un modérateur de ce conti peut toujours déplacer des messages depuis ce conti, mais n'a pas toujours le droit d'en faire un conti cible de blasts.
\end{itemize}
\sautligne
Prenons un exemple. Plaçons-nous dans la situation précédente, et supposons que l'on ait un troisième conti, \verb+schmilblick+. Supposons que \verb+foo+ soit en lecture seule. Soient les deux modérateurs suivants :

\begin{center}
\begin{tabular}{llll}
Modérateur & \verb+foo+ & \verb+bar+ & \verb+schmilblick+ \\ \hline
Alice & Oui, en lecture seule & Oui & Non \\
Bob & Oui, en lecture et écriture & Non & Non \\
\end{tabular}
\end{center}

Dans ces conditions, Alice peut déplacer le message \verb+22+ de \verb+bar+ vers \verb+schmilblick+, mais pas vers \verb+foo+ car il est en lecture seule. Ce que peut faire Bob, en revanche.

Toutefois, Alice, modératrice de \verb+foo+, peut, comme Bob, déplacer le message \verb+18+ de \verb+foo+ vers \verb+bar+, même si Alice n'a pas le droit d'écriture sur \verb+foo+ car ce droit ne s'applique que si le conti est la destination d'un blast. 

Alice et Bob, modérateurs de \verb+foo+, peuvent choisir de déplacer tout le fil de \verb+foo+ issu de \verb+18+, qui comprendra donc les messages \verb+18+, \verb+19+ et \verb+20+, mais pas \verb+22+ car son père, \verb+21+, n'est pas dans \verb+foo+.

\begin{center}\begin{tabular}{|p{15cm}|}
\hline\begin{flushleft}\textbf{Important} \\ \end{flushleft}
\emph{Lorsqu'un message est déplacé d'un conti vers un autre, son Message-ID change.} \\
\\
C'est une convention utilisée dans certains forums, comme celui des élèves de l'ENS, considérant qu'un message, déplacé, n'est plus le même message (en particulier si le Message-ID est un \emph{hash} du contenu du message, en-tête et corps compris).  \\
\\
\hline\end{tabular}\end{center}
\section{Modélisation en termes de bases de données}
\subsection{Schéma entité-association}

\begin{center}
La figure n'est pas prête.
\end{center}

\subsection{Tables}\label{sql-tables}

Nous avons choisi de stocker le corps des messages dans des fichiers, et non dans la base de données. C'est ce que l'on appelle le \emph{spool}.

Le code SQL de création des tables est donné ci-dessous :

\lstset{language={sql}, keywordstyle=\bfseries, basicstyle=\ttfamily}
\lstinputlisting{base_tables.sql}

La table \verb+contis+ définit les contis. L'attribut \verb+prochain_numero+ définit le numéro du prochain message qui appartiendra à ce conti (car outre par son Message-ID, on peut aussi accéder à un message par un conti auquel il appartient, et le numéro au sein de ce conti, défini dans l'attribut \verb+numero+ de la table \verb+messages_contis+).
\sautligne
La table \verb+droits+ définit les modérateurs.
\sautligne
La table \verb+messages+ définit les messages. L'attribut \verb+pere+ contient le Message-ID du père, ou \verb+NULL+ si le message n'a pas de père.

L'attribut \verb+fils+ contient les Message-ID des fils du message, séparés par des virgules, mais n'est pas utilisé en pratique (un \lstinline+select id from messages where pere = 'id_du_pere'+ fait l'affaire).

L'attribut \verb+numero_fichier+ permet d'accéder au fichier spool correspondant au message (c'est le fichier qui contient le corps du message), dont le nom est \verb+id.numero_fichier+.
\sautligne
La table \verb+messages_contis+ définit les appartenances de messages à des contis (on rappelle qu'un message peut appartenir à plusieurs contis). Comme un Message-ID peut changer, il n'est pas question d'intégrer ici pour l'attribut \verb+message+ une clé étrangère référençant \verb+messages.id+, tout comme pour les attributs \verb+de+ et \verb+a+ de la table \verb+refs+.
C'est dans cette table qu'est défini le numéro d'un message au sein d'un conti (attribut \verb+numero+). Cependant dans tous les contis auxquels il appartient, le message conserve son unique Message-ID.
\sautligne
Les tables sont utilisées :
\begin{itemize}
\item par le programme, pour le post et la modération
\item directement, pour l'administration (création de contis et déclaration de modérateurs).
\end{itemize}

\subsection{Instructions SQL pour l'administration}
La création d'un conti se fait directement via l'instruction SQL suivante :

\begin{itemize}
\item si le conti est en lecture seule :
  \begin{lstlisting}
    insert into contis(nom, lecture_seule) values( 'nom_du_conti', 't' );
  \end{lstlisting}
\item sinon, au choix :
  \begin{lstlisting}
    insert into contis(nom) values( 'nom_du_conti' );
    insert into contis(nom, lecture_seule) values( 'nom_du_conti', 'f' );
  \end{lstlisting}
\end{itemize}

Un modérateur est ajouté également directement, par insertion de valeurs, sur le modèle de la création de conti.

\begin{itemize}
\item si le conti n'est pas en lecture seule
\begin{lstlisting}
insert into droits(moderateur, conti)
       values( 'nom_du_moderateur', 'nom_du_conti' )
\end{lstlisting}
\item si le conti est en lecture seule mais que l'on souhaite cependant que le modérateur ait le droit de déplacer des messages \emph{depuis et vers} ce conti, on utilise au choix :
\begin{lstlisting}
insert into droits(moderateur, conti)
       values( 'nom_du_moderateur', 'nom_du_conti' )
insert into droits(moderateur, conti, ecrire)
       values( 'nom_du_moderateur', 'nom_du_conti', 't' )
\end{lstlisting}
\item  si le conti est en lecture seule mais que l'on souhaite cependant que le modérateur ait le droit de déplacer des messages \emph{uniquement depuis} ce conti :
\begin{lstlisting}
insert into droits(moderateur, conti, ecrire)
       values( 'nom_du_moderateur', 'nom_du_conti', 'f' )
\end{lstlisting}
\end{itemize}

\section{Le programme}

Le programme a été écrit en C, avec la librairie \verb+libpq+ pour l'accès à la base de données PostgreSQL. C'est le module \verb+base.c+ qui concerne les bases de données et le fonctionnement du forum, tandis que \verb+server.c+ contient les fonctionnalités réseau, permettant une utilisation plus ou moins <<pratique>> du programme.

\subsection{Post}
Le programme commence par générer des fragments de requêtes :
\begin{enumerate}
\item génère le Message-ID du message
\item vérifie, pour chaque message référencé, s'il existe, en exécutant\footnote{La vérification consiste à compter le nombre de lignes renvoyées par l'exécution d'une telle requête. Si aucune ligne n'est renvoyée, la vérification échoue.} :
  \begin{lstlisting}
    select * from messages where id = '...'
  \end{lstlisting}
  et génère la requête d'insertion correspondante dans la table des références :
  \begin{lstlisting}
    insert into refs(de,a)
      values('nouveau_message','message_reference')
  \end{lstlisting}
\item vérifie, pour chaque conti, s'il existe et s'il n'est pas en lecture seule, en exécutant :
  \begin{lstlisting}
    select * from contis where id = '...' and lecture_seule = 'f'
  \end{lstlisting}
  et génère la requête d'insertion correspondante, avec l'incrément du numéro du prochain message :
  \begin{lstlisting}
    insert into messages_contis (message,conti,numero) values (
      '...', '...',
      (select prochain_numero from contis where nom = '...' )
    );
    update contis set prochain_numero = 1 + prochain_numero
      where nom = '...';
  \end{lstlisting}
  Si aucun conti ne convient, la création du message est annulée.
  \item Sinon, le programme crée le fichier spool (contenant le corps du message), et génère la requête de création du message (\lstinline+insert into messages...+).
\end{enumerate}
\sautligne
Enfin, les différents fragments de requêtes générés sont remis dans l'ordre :
\begin{enumerate}
  \item insertion du message
  \item insertion des références
  \item insertion dans les contis
\end{enumerate}
puis exécutés au sein d'une même transaction, avec un verrou :
\begin{lstlisting}
  lock contis in row exclusive mode
\end{lstlisting}
au préalable pour éviter les conflits au niveau de l'incrémentation du compteur \verb+prochain_numero+.

\subsection{Déplacement d'un message}
Lorsqu'un modérateur souhaite déplacer un message, le programme commence par vérifier si ce modérateur :
\begin{itemize}
\item est modérateur du conti source :
\begin{lstlisting}
select * from droits where moderateur = '...' and conti = '...';
\end{lstlisting}
\item a les droits d'écriture sur le conti cible s'il est en lecture seule :
\begin{lstlisting}
select * from contis,droits
  where conti.nom = '...' and (
    conti.lecture_seule = 'f'
    or (
      droits.conti = conti.nom
      and droits.moderateur = '...'
      and droits.ecrire = 't'
    )
  )
\end{lstlisting}
(Si le conti n'est pas en lecture seule, cette requête, exécutée, renvoie toute la table \verb+droits+ jointe à la ligne de \verb+contis+ définissant le conti cible)
\end{itemize}

Si le modérateur passe ces vérifications avec succès, alors le message peut être déplacé. Le programme :
\begin{enumerate}
\item copie le fichier spool pour y mettre à jour l'en-tête \verb+NEWSGROUPS+
\item supprime la ligne de \verb+messages_contis+ liant le message au conti source :
\begin{lstlisting}
  delete from messages_contis
    where message = 'id' and conti = 'conti_source'
\end{lstlisting}
\item vérifie si le message est déjà présent dans le conti cible :
\begin{lstlisting}
  select * from messages_contis
    where message = 'id' and conti = 'conti_cible'
\end{lstlisting}
Si c'est le cas, le programme se contente d'incrémenter le compteur \verb+numero_fichier+ pour prendre en compte la copie du fichier spool, sans modifier le Message-ID, et la procédure est terminée :
\begin{lstlisting}
  update messages set numero_fichier = 1 + numero_fichier
    where message = 'id'
\end{lstlisting}
\item Si le message est absent du conti cible, alors il faut changer son Message-ID. Le programme génère alors un nouvel ID et renomme alors la copie du fichier spool dans ce sens,
\item sélectionne tous les messages faisant référence au message à déplacer :
\begin{lstlisting}
  select de from refs where a = 'ancien_id'
\end{lstlisting}
 puis pour chacun d'eux, crée une copie du fichier spool pour y mettre à jour l'en-tête \verb+REFERENCES:+, et incrémente alors, comme ci-avant, le compteur \verb+numero_fichier+ (dans la table \verb+messages+)
\item détecte l'éventuelle présence d'un père (en deux temps, vérifie d'abord si \verb+pere+ contient un Message-ID valide, puis teste l'existence du message), pour mettre à jour l'attribut \verb+fils+ correspondant dans \verb+messages+ (attribut qui n'est pourtant pas utilisé outre mesure : cette étape pourrait donc très bien être ignorée et l'attribut \verb+fils+ supprimé dans les définitions des tables)
\item remplace alors par le nouvel ID toutes les occurrences de l'ancien parmi les fils (dans l'attribut \verb+pere+ de \verb+messages+), ainsi que dans les attributs \verb+de+ et \verb+a+ de \verb+refs+ :
\begin{lstlisting}
  update messages set pere = 'nouvel_id' where pere = 'ancien_id';
  update refs set de = 'nouvel_id' where de = 'ancien_id';
  update refs set a = 'nouvel_id' where a = 'ancien_id';
\end{lstlisting}
\item modifie la ligne de définition du message dans \verb+messages+, pour prendre en compte le nouvel ID :
\begin{lstlisting}
  update messages set id = 'nouvel_id', numero_fichier = 0
    where id = 'ancien_id'
\end{lstlisting}
\item et enfin, signale l'appartenance du message au conti cible :
\begin{lstlisting}
  insert into messages_contis(message, conti, numero) values(
    'nouvel_id', 'cible', (
      select prochain_numero from contis where nom = 'cible'
    )
  );
  update contis set prochain_numero = 1 + prochain_numero
    where nom = 'cible'
\end{lstlisting}
\end{enumerate}

Notons que toutes ces requêtes sont exécutées dans une même transaction, avec au préalable des verrous amplement suffisants comme :
\begin{lstlisting}
  lock refs,messages,messages_contis in exclusive mode;
  lock contis in row exclusive mode;
\end{lstlisting}
Ceci empêche le post de messages pendant l'opération de blast. En particulier, la réponse (par référence) à un message en train d'être déplacé (problème très désagréable en pratique : fils de discussion interrompus).

\subsection{Déplacement d'un fil}

On rappelle que, dans un fil, ne sont déplacés que :
\begin{itemize}
\item la racine, si elle appartient au conti source
\item les messages appartenant au conti source et dont le père appartient au conti source
\end{itemize}
\sautligne
Avant toute chose, les vérifications des droits du modérateur sont effectuées une fois pour toutes.

Puis, une transaction unique est créée pour le déplacement de tout le fil. Le programme s'exécute alors récursivement, avec pour cas de base la racine du fil à déplacer :
\begin{enumerate}
\item Le programme déplace d'abord le message considéré du conti source vers le conti cible.
\item Puis, le programme cherche tous ses fils qui sont dans le conti source :
\begin{lstlisting}
  select messages.id from messages,messages_contis
    where messages.id = messages_contis.message
    and messages.pere = 'nouvel_id_du_pere'
    and messages_contis.contis = 'conti_source'
\end{lstlisting}
\item Puis, le programme déplace (récursivement, donc) le fil de discussion issu de chacun de ces messages, mais toujours depuis le même conti source, vers le même conti cible.
\end{enumerate}
\subsection{Utilisation du programme}
Le programme est un serveur TCP qui écoute sur le port n°12755. On interagit donc avec lui grâce à un programme de communication réseau, typiquement \verb+telnet+\footnote{Ne pas utiliser \texttt{netcat} dont les conventions de fin de ligne ($\mathtt{\backslash n}$) ne respectent pas les standards de communication TCP ($\mathtt{\backslash r\backslash n}$).}. Nous préconisons de travailler dans un environnement FreeBSD.
\sautligne
Avant de compiler le programme, il faut modifier les lignes de \verb+serv.h+ :
\lstset{language=C}
\begin{lstlisting}
#define SPOOLPATH "chemin_de_spool"
#define PGCONN "host=hote_postgre dbname=base_de_donnees"
\end{lstlisting}
afin de spécifier le répertoire (à créer au préalable) où les fichiers spool seront créés, ainsi que les coordonnées de la base de données PostgreSQL contenant les tables (que l'on aura créées au préalable grâce aux instructions SQL du \ref{sql-tables}).

Les sources \verb+base.c+, \verb+server.c+, \verb+serv.h+  se compilent alors sous FreeBSD avec la librairie \verb+libpq+ :
\lstset{language=ksh}
\begin{lstlisting}
gcc -o base -I`pg_config --includedir` -L`pg_config --libdir` -lpq
   base.c server.c
\end{lstlisting}
Une fois compilé, le programme \verb+base+ peut être lancé. Il n'admet pas d'entrée utilisateur, mais il écoute sur le port n°12755 et il peut afficher des messages décrivant son activité (en particulier les principales requêtes exécutées).
Pour interagir avec \verb+base+, il est donc nécessaire d'ouvrir \verb+telnet+ dans un autre terminal (ou carrément sur une autre machine, qui elle, peut vivre sous n'importe quel système d'exploitation pourvu de \verb+telnet+) :
\begin{lstlisting}
telnet machine_ou_on_a_lance_base 12755
\end{lstlisting}

Le serveur répond alors :
\begin{verbatim}
Hey, how's it going ?
\end{verbatim}
où l'on doit alors entrer \lstinline+helo utilisateur+, sur quoi l'on reçoit le message :
\begin{verbatim}
Nice to meet you.
\end{verbatim}

Là, on peut exécuter les commandes suivantes : \clearpage

\begin{center}
\begin{tabular}{lp{9cm}}
\verb+BLST messageid, source, cible+ & Déplace un message isolé. Attention à l'espace après chaque virgule. \\ \\
\verb+BLTHR messageid, source, cible+ & Déplace le fil de discussion de \verb+source+ dont la racine est \verb+messageid+. Attention à l'espace après chaque virgule. \\ \\
\verb+GET message_id+ & Affiche le contenu du fichier spool du message dont l'ID est indiqué. \\ \\
\verb+GETID conti, numero+ & Affiche le Message-ID correspondant au message indiqué par son conti et son numéro au sein du conti. Attention, bien respecter l'espace après la virgule. \\ \\
\verb+LIST conti+ & Affiche la liste des messages (numéro et message-ID) dans le conti spécifié. \\ \\
\verb+LSTNGS+ & Affiche la liste des contis. \\ \\
\verb+POST+ & Poste un message. Sur les lignes suivantes, il faudra indiquer successivement et \textbf{dans l'ordre}, les champs \verb+NEWSGROUPS+, \verb+FROM+, \verb+SUBJECT+ et \verb+REFERENCES+, sous la forme \verb+ATTRIBUT:<espace><contenu>+ (en plaçant aussi une espace après chaque virgule, si l'on indique plusieurs newsgroups ou plusieurs références). Ensuite, on pourra spécifier le corps du message, sur une ou plusieurs lignes, en terminant par une ligne blanche puis par une ligne ne contenant qu'un point.\\ \\
\verb+QUIT+ & Coupe la connexion au serveur. \\
\end{tabular}
\end{center}
\sautligne
Notre choix d'avoir écrit un serveur permet en fait l'exécution de requêtes en parallèle depuis plusieurs machines, dans les conditions réelles d'utilisation d'un forum. On peut imaginer ce qui peut se passer si le répertoire de spool est situé sur une disquette (ou tout autre périphérique de stockage lent), par exemple.
\sautligne
Pour fermer le serveur, on revient là où on l'a lancé et on fait la combinaison de touches Ctrl+C.
\end{document}