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

\usepackage{amsmath,amssymb,verbatim}

\usepackage{supertabular}

\usepackage{listings}

\usepackage{url}

\def«{\og}
\def»{\fg}

\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.
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.
Mais les messages sont aussi organisés en arbres, grâce à une notion de
\emph{père-fils}, qui définit \emph{un thread}, ou \emph{fil de
discussion}.  Un thread peut s'étendre arbitrairement sur plusieurs
contis.
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{Motivation de notre système}
Historiquement, les news ont commencé par le système de
\emph{mailing-list}. Dès 1970, les développeurs de divers composants du
système \emph{ITS}\cite{ITS} (Incompatible Timesharing System) avaient mis
en place de telles \emph{mailing-lists}, pour recevoir les divers rapports
de bugs.\\
Chaque message envoyé à une telle addresse était redirigé vers chaque
personne inscrite.\\
De nombreux problèmes se posent. Notamment, chaque message étant stocké
chez chaque utilisateur, une place importante est perdue ; tout le monde
recevant les mêmes messages, il est plus judicieux de les stocker une seule
fois et de donner aux utilisateurs les moyens de les lire depuis cet
endroit.\\

En 1986 parait la RFC 977\cite{RFC977}, qui décrit \verb+NNTP+,
protocole de news encore utilisé aujourd'hui, notamment sur \emph{\textsc
USENET}.  Ce protocole possède une grande flexibilité en centralisant
les messages et permettant a divers serveurs de se «feeder» certains
groupes (avoir des groupes en commun, chaque message posté dans un groupe
sur un serveur étant copié sur l'autre). Toutefois, la RFC ne spécifie pas
de détails d'implémentation, par exemple la manière dont sont stockés les
messages (base de données SQL, Berkeley DB, etc.). Il lui manque une
fonction utile, celle de pouvoir aisément déplacer des messages
d'un groupe a un autre.\\
C'est pour pallier à ces défauts que nous avons choisi d'implémenter un
serveur de news reposant sur une base de donnée SQL. Nous avons
délibérement choisi de ne pas respecter la RFC 977, ce qui aurait demandé
un travail beaucoup plus long et ne rentrant globalement pas dans le cadre
de ce projet.

\subsection{Structure d'un message}

Un message est constitué d'\emph{un en-tête}, suivi 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 champs obligatoires dans notre système 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  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: lisp, scheme
FROM: zoghaib
SUBJECT: macros
REFERENCES:
 
Message-Id: 19
NEWSGROUPS: lisp
FROM: ramanana
SUBJECT: Re: macros
REFERENCES: 18
 
Message-Id: 20
NEWSGROUPS: lisp
FROM: zoghaib
SUBJECT: evalquote (Was: Re: macros)
REFERENCES: 18, 19
 
Message-ID: 21
NEWSGROUPS: scheme
FROM: ramanana
SUBJECT: Re: macros
REFERENCES: 18
 
Message-ID: 22
NEWSGROUPS: lisp
FROM: zoghaib
SUBJECT: Re: macros
REFERENCES: 19, 21
\end{verbatim}
  \end{minipage}
& \epsfig{file=arbre.eps}
\end{tabular}

Le fait de poster un message contenant un nom de conti inconnu ne crée pas
automatiquement 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}

Prenons un exemple. Plaçons-nous dans la situation précédente, et supposons
que l'on ait un troisième conti, \verb+caml+. Supposons que
\verb+lisp+ soit en lecture seule. Soient les deux modérateurs suivants :

\begin{center}
\begin{tabular}{llll}
Modérateur & \verb+lisp+ & \verb+scheme+ & \verb+caml+ \\ \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+scheme+
vers \verb+caml+, mais pas vers \verb+lisp+ car il est en lecture
seule. Ce que peut faire Bob, en revanche.

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

Alice et Bob, modérateurs de \verb+lisp+, peuvent choisir de déplacer tout
le fil de \verb+lisp+ 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+lisp+.

\emph{Lorsqu'un message est déplacé d'un conti vers un autre, son
  Message-ID change.} \\
C'est une convention utilisée dans la plupart des systèmes de news, dont
{\textsc NNTP}, 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). Les clients news utilisant cette
propriété pour savoir quels sont les messages lus ou non lus, il convient
de ne pas la changer. En effet, ce serveur minimal étant fonctionnel, on
pourrait vouloir l'étendre afin qu'il respecte la RFC 977. Ses
fonctionnalités avancées nécessiteraient un client adapté pour être
utilisé, mais les fonctionnalités de base (commune avec NNTP) doivent
pouvoir être utilisées avec un client news usuel.
\\

\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+).\\
La table \verb+droits+ définit les modérateurs.\\
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.
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+.\\
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.\\

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). Le rajout d'une interface pour la modération (démon ou
  interface web, par exemple) est triviale.
\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 \cite{KR2}, avec la librairie \verb+libpq+
pour l'accès à la base de données PostgreSQL. Le module \verb+base.c+
concerne la base de données et le fonctionnement interne du forum, tandis
que \verb+server.c+ est le code du démon qui permet d'utiliser le forum,
notamment par le réseau. Notons toutefois que \verb+base.c+ utilise des
extensions {\textsc GNU} de la {\textsc libc}. Le code est raisonnablement
portable, et devrait tourner, en ce qui concerne \verb+server.c+, sur
n'importe quel système {\textsc POSIX}, et en ce qui concerne
\verb+base.c+, sur n'importe quel système implémentant \verb+asprintf()+.

\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}

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}
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 \verb+SERV_TCP_PORT+
défini dans {\textsc serv.h} et pouvant être spécifié au lancement du
serveur, à l'aide de l'option \verb+-p+ ou \verb+--port+. On interagit donc
avec lui grâce à un programme de communication réseau, typiquement
\verb+telnet+.

Certains \verb+#define+ devraient être adaptés à la machine où l'on
souhaite faire tourner le serveur avant la compilation.
\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 avec la librairie \verb+libpq+ :
On conseille d'utiliser le \verb+Makefile+ fourni.
\lstset{language=ksh}
\begin{lstlisting}
make
\end{lstlisting}

Une fois compilé, le programme \verb+base+ peut être lancé. Il se détache
du terminal et redirige sa sortie standard et son erreur standard vers
\verb+/dev/null+, sauf si l'option \verb+--debug+ lui a été passée.

\begin{lstlisting}
telnet host TCP_SERV_PORT
\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}
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.\\
Le serveur peut être fermé en lui envoyant  \verb+SIGTERM+.

\addcontentsline{toc}{section}{Bibliographie}
\bibliographystyle{plain}
\bibliography{forumsql}

\end{document}