<figure><img src="image_1.png" /></figure>

HAL
open science

# Λ0: un langage de commande pour une machine spécialisée dans la consultation de données textuelles

Jean-Paul van de Wiele

► To cite this version:

Jean-Paul van de Wiele. Λ0: un langage de commande pour une machine spécialisée dans la consultation de données textuelles. [Rapport de recherche] IRIA-RR-305, IRIA. 1978, pp.31. hal-04716535

HAL Id: hal-04716535

https://inria.hal.science/hal-04716535v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

$\Lambda_0$:
UN LANGAGE DE COMMANDE
POUR UNE MACHINE SPÉCIALISÉE
DANS LA CONSULTATION
DE DONNÉES TEXTUELLES

Jean-Paul Van de WIELE

Rapport de Recherche N° 305

Mai 1978
# $\Lambda_0$: UN LANGAGE DE COMMANDE POUR UNE MACHINE SPÉCIALISÉE DANS LA CONSULTATION DE DONNÉES TEXTUELLES

Jean-Paul Van de Wiele

## Résumé :

$\Lambda_0$ est la première version du langage de commande d'un processeur spécialisé dans la consultation de données textuelles, en cours de réalisation au Laboria. Ce processeur, du type «disque intelligent», comporte un disque magnétique à têtes mobiles, d'une capacité de 300 mégaoctets dont le contrôle est assuré par une logique microprogrammable spécialisée. Les données sont stockées sous forme de relations dont les éléments sont rangés physiquement consécutivement. La structure des relations sur le disque, que nous avons appelée «tridimensionnelle», est d'un type nouveau. Elle tient compte du découpage d'un disque en cylindres, pistes et secteurs. Le contrôleur de disque est capable de lire séquentiellement les éléments consécutifs d'une relation, caractère par caractère et en perdant très peu de rotations. De plus il «filtre au vol» ceux qui répondent à un critère donné. L'ensemble contrôleur-disque fonctionne en parallèle avec un miniordinateur MITRA 125 auquel il est connecté et qui assure la communication avec les utilisateurs. $\Lambda_0$ est un langage uniquement de consultation. Il implémente un ensemble d'opérateurs relationnels non complet. Son originalité tient à ce qu'il offre plus de possibilités pour la consultation de données textuelles que la plupart des langages similaires.

## Abstract :

$\Lambda_0$ is the first version of the query language of a dedicated processor for textual data interrogation. This processor, which is now at the realization stage at Laboria, is an «intelligent disk». A 300 megabytes moving arm disk is controlled by a special microprogrammable logic. Data are stored as relations whose elements are physically clustered. A new data structure called «tridimensional» is used for storing the relations. This structure is based on the decomposition of a magnetic disk in cylinders, tracks and sectors. The controller is able to read sequentially the consecutive elements of a relation, one byte at a time, loosing very few disk-rotations. It also selects on the fly elements which satisfy a given condition. The whole machine excutes in parallel with a minicomputer MITRA 125 which controls it and is responsible for user-communications. $\Lambda_0$ supplies only query functions and implements an incomplete set of relational operators. It offers richer textual data interrogation facilities than most similar languages.
Λ₀ : UN LANGAGE DE COMMANDE POUR UNE MACHINE SPECIALISÉE DANS LA CONSULTATION DE DONNÉES TEXTUELLES

1. Introduction. Présentation générale de la machine.

2. Relations.

3. Forme générale d'une instruction et principales caractéristiques de Λ₀

4. Lettres, mots, phrases, paragraphes.

5. Représentation des constantes de type texte.

6. Forme générale du prédicat de sélection P.

7. Prédicats élémentaires.

8. Représentation d'un ensemble de constantes de type texte par leur structure syntaxique.

9. Identifieurs de structures syntaxiques.

10. La clause ORDONNER PAR.

11. La valeur VIDE.

12. Bibliographie

Annexe. La syntaxe de Λ₀.
# $\Lambda_O$: UN LANGAGE DE COMMANDE POUR UNE MACHINE SPECIALISÉE DANS LA CONSULTATION DE DONNEES TEXTUELLES

## I. INTRODUCTION. PRESENTATION GENERALE DE LA MACHINE.

$\Lambda_O$ est la première version du langage de commande d'une machine conçue pour la gestion d'une base de données, et en particulier d'une base de données constituées par du texte en langage naturel ou proche du langage naturel, comme un annuaire téléphonique, un ensemble de résumés bibliographiques, ou le courrier d'une entreprise. Cette machine est en cours de réalisation au LABORIA dans le cadre du projet "Système de Consultation de Données" et il est utile d'en faire une brève présentation générale.

L'objectif de cette réalisation est de concourir à la définition et à la réalisation d'une machine multiprocesseurs spécialisée pour la gestion d'une base de données non numériques ; de nombreuses machines de ce type ont déjà été proposées dans la littérature et un petit nombre d'entre elles ont été réalisées, en particulier RAP [1] et CASSM [2]. Un congrès récent (Mai 1977), le SIGIR - SIGARCH - SIGMØD THIRD WORKSHOP ON COMPUTER ARCHITECTURE FOR NON-NUMERIC PROCESSING [3] a fait le point sur cette question.
L'idée de base est toujours la même, à savoir de simuler une grande mémoire rapide associative, irréalisable dans l'état actuel de la technologie, par un ensemble de **cellules** fonctionnant simultanément, chaque cellule étant constituée d'une mémoire de masse et d'une logique hardware développée autour d'un microprocesseur spécialisée dans la gestion de cette mémoire ; cette logique est capable, en particulier, de sélectionner très rapidement les données contenues dans la mémoire qu'elle gère et satisfaisant à un critère donné. Nous avons conçu et nous sommes en train de réaliser une telle cellule.

Elle comporte un disque à têtes mobiles de grande capacité (300 mégaoctets). Les données sont stockées sous forme de relations dont les tuplets sont rangés consécutivement sur le disque dans un ordre qui dépend des valeurs de leurs composantes. Le disque est contrôlé par un processeur spécialisé, construit autour d'un microprocesseur, qui est capable de lire séquentiellement, caractère par caractère, et en perdant très peu de rotations, les tuplets consécutifs d'une relation en sélectionnant "au vol" ceux qui répondent à un critère donné.

Les caractéristiques essentielles de notre "disque intelligent" sont les suivantes :

1) C'est une machine uniquement de consultation. Les données sont supposées avoir été déjà inscrites sur le disque par un moyen quelconque. Ceci est une restriction par rapport aux machines comme RAP et CASSM.

2) Pour sélectionner les tuplets d'une relation qui satisfont un critère donné, le microprocesseur de contrôle n'a pas, la plupart du temps, à lire **tous** les tuplets de la relation. Il peut en "sauter" un certain nombre en utilisant le fait que les tuplets ne sont pas rangés dans le désordre, ce qui est généralement, au contraire, le cas dans les machines comparables ; en effet la technologie d'un disque à têtes mobiles permet d'y ranger les tuplets d'une relation suivant 3 critères de
classement différents (cf [4]). Le plus simple est de faire une analogie
avec la façon dont les livres sont rangés dans certaines bibliothèques.
Les livres sont distribués sur plusieurs rayonnages, chaque rayonnage
étant constitué de plusieurs étagères, disposées les unes au-dessous
des autres. Chaque rayonnage regroupe les livres ayant trait à une
discipline donnée, et sur un rayonnage les livres sont rangés par ordre
alphabétique d'auteur. Imaginons un mode de classement un peu plus
complexe : à l'intérieur d'un rayonnage, donc d'une discipline, les livres
sont distribués par ordre alphabétique de titre, et sur chaque étagère
ils sont rangés par ordre alphabétique d'auteur. Chaque étagère comporte
une étiquette, par exemple A... - C... où A... et C... sont deux titres,
qui signifie que les titres des livres situés sur cette étagère sont
compris entre A... et C... alphabétiquement. Un lecteur qui cherche un
livre sur un sujet donné sans idée à priori sur le titre ou l'auteur du
livre devra consulter tous les livres d'un rayonnage. Si maintenant il
cherche un livre d'un titre donné, il devra consulter dans tous les
rayonnages de la bibliothèque les étagères dont les étiquettes montrent
qu'elles sont susceptibles de contenir le livre qu'il cherche.

Si enfin il connait l'auteur du livre, il
aura à chercher dans toutes les étagères de tous les rayonnages, mais sa
recherche sera facilitée par le fait que, les livres étant à priori
distribués alphabétiquement indépendamment du sujet et du titre, les
zones de chaque étagère qu'il aura à consulter seront approximativement
situées les unes en-dessous des autres. Nous voyons donc que le lecteur
peut utiliser les informations qu'il a sur le sujet, le titre et l'auteur
du livre qu'il cherche pour mettre au point un algorithme de consultation
des rayonnages de la bibliothèque fondé sur un "balayage" séquentiel mais
qui permet d'éliminer à priori un certain nombre de livres.

Les tuplets des relations sont distribués de façon analogue, en
tenant compte des valeurs de trois de leurs composantes dont les domaines
sont totalement ordonnés, sur les cylindres (rayonnages) et les pistes
(etagères) du disque. La commutation instantanée des têtes de lecture
d'un disque à têtes mobiles, qui permet de lire consécutivement le secteur $j$ de la piste $i$ et le secteur $(j+1)$ de la piste $(i+1)$ ou $(i-1)$ dans le même cylindre, est l'analogue du mouvement de l'oeil qui permet de sauter d'une étagère à une autre se trouvant immédiatement au-dessus ou en-dessous ; les "etiquettes" des rayonnages et des étagères sont inscrites sur les cylindres et les pistes eux-mêmes.

Ce système de classement particulier permet au microprocesseur qui contrôle le disque de gagner du temps, s'il est possible d'extraire du critère de sélection des informations sur les trois critères de classement (les trois clés). Il pourra en effet utiliser ces informations pour, au cours de son balayage des tuplets de la relation, "sauter" un certain nombre de tuplets. C'est la raison pour laquelle le critère de sélection $P_1$ dans les commandes de $\Lambda_0$, sera systématiquement décomposé en un critère $P_1$ portant sur les clés et un critère $P_2$. $P_1$ déterminera les zones du disque à explorer et chacun des tuplets de cette zone sera confronté au critère $P_2$. Le lecteur est renvoyé à la note technique "La Recherche Tridimensionnelle" ([4]) pour une exposition détaillée de cette méthode de classement et des méthodes de recherche associées.

3) **Troisième caractéristique** : notre machine admet des critères de sélection plus compliqués que ceux qui sont admis par les machines comparables. En effet nous avons dit au début de cette introduction que la machine avait été conçue spécialement pour la consultation de données constituées par du texte en langue naturelle ou proche de la langue naturelle. Lorsqu'on a affaire à des données qui se présentent sous la forme de texte, donc de chaînes de caractères (de longueur variable naturellement), il est utile de disposer d'outils qui permettent non seulement de tester si une chaîne de caractères est égale ou non à une chaîne de caractères donnée mais encore si elle _contient_ une ou plusieurs chaînes de caractères données, éventuellement dans un certain ordre. Aussi avons-nous conçu le hardware du processeur de contrôle du disque pour rendre apte celui-ci à exécuter en temps réel, c'est-à-dire
à la vitesse de rotation du disque, des algorithmes complexes de reconnaissance de caractère. (Consulter à ce sujet les notes techniques de Dimitri Tusera [5], [6], [7]).

4) Le disque intelligent est un processeur autonome qui communique avec un miniordinateur MITRA 125 par l'intermédiaire duquel il est commandé ; une commande reçue par le MITRA est traduite par lui en un microprogramme exécutable par le processeur ; le microprogramme est envoyé au processeur et c'est le MITRA qui en contrôle l'exécution et qui renvoie à l'utilisateur les tuplets fournis en résultat par le disque.

Nous allons maintenant présenter dans le détail le langage de commande $Λ_o$, dont la syntaxe simplifiée en BNF est donnée en annexe.

Soulignons immédiatement que $Λ_o$ n'est pas le seul langage possible pour la machine.

D'une part un certain nombre d'aspects de ce langage ont été conçus pour répondre aux besoins d'une application particulière, à savoir la consultation de résumés bibliographiques. Il s'agit par exemple du découpage du texte en 4 niveaux : paragraphe, phrase, mot, lettre. Pour d'autres applications le découpage en 2 niveaux, par exemple, suffirait. Ce qu'il est important de retenir c'est que la machine a été conçue pour opérer sur plusieurs niveaux syntaxiques.

D'autre part $Λ_o$ ne recouvre pas **toutes** les possibilités du langage machine. Il s'agit donc **d'un** langage d'utilisation possible.

Un certain nombre de contraintes, dues au hardware, en particulier sur le nombre maximal de connecteurs logiques dans le prédicat de sélection, ne sont pas explicitées. Une note technique ultérieure les précisera.

Nous commençons par quelques brefs rappel sur le concept de relation.

## II. RELATIONS

$Λ_o$ opère sur des **relations** ; rappelons qu'une **relation** $R$ définie sur les ensembles $DA_1, ..., DA_n$ est un sous-ensemble de $DA_1 \times ... \times DA_n$. Les ensembles $DA_1, ..., DA_n$ sont appelés les **domaines** de $R$. L'opération projection qui à un tuplet de $R$, $(x_1, ..., x_n)$, associe $x_i \in DA_i$ est appelée le **i-ème attribut** de $R$ et on lui donne un nom : $A_i$. On note la relation $R(A_1 : DA_1, ..., A_n : DA_n)$. On dit encore que $DA_i$ est le domaine de l'attribut $A_i$ et que les éléments de $DA_i$ sont des **valeurs d'attribut** pour $A_i$.
Les instructions de $\Lambda_o$ permettent de construire une relation R' à partir d'une relation R par **projection**, **sélection** ou une opération composée des deux précédentes.

Soit $R(A_1 : DA_1, \dots, A_n : DA_n)$ une relation définie sur $DA_1, \dots, DA_n$. Et soit $D = \{DA_{i_1}, \dots, DA_{i_k}\}$ un sous-ensemble de $\{DA_1, \dots, DA_n\}$. La **projection** de R sur D est la relation $R''(A_i : DA_{i_1}, \dots, A_i : DA_{i_k})$ ensemble de tuplets $(x_{i_1}, \dots, x_{i_k})$ de $DA_i \times \dots \times DA_{i_k}$ tels qu'il existe un tuplet $(y_1, \dots, y_n) \in R$ tel que pour tout $j, 1 \le j \le k$, $y_{i_j} = x_{i_j}$.

Le résultat de la **sélection** de R par le prédicat P défini sur $DA_1 \times \dots \times DA_n$ est la relation $R'(A_1 : DA_1, \dots, A_n : DA_n)$ ensemble des tuplets $(x_1, \dots, x_n)$ tels que P $(x_1, \dots, x_n)$ est vrai.

### III. FORME GENERALE D'UNE INSTRUCTION ET PRINCIPALES CARACTERISTIQUES DE $\Lambda_o$.

La forme générale d'une instruction de $\Lambda_o$, mis à part quelques "ornements", inessentiels à ce niveau de description, est la suivante :

I : **TROUVER** liste-de-noms-d'attribut

**DANS** R

**AVEC** P

R est un nom de relation ; liste-de-noms-d'attribut est une liste de noms d'attribut de R ; P est un prédicat défini sur les tuplets de R. I signifie :

1) Construire la relation $R''$ sélection de R par P.

2) Construire $R'$, projection de $R''$ sur $D$ où $D$ est le sous-ensemble des domaines de $R$, donc de $R''$, qui est spécifié par **liste-de-noms-d'attribut**, et afficher les tuplets de $R'$.
On peut remplacer dans I **TROUVER** par **COMPTER**. Le résultat de la requête sera dans ce cas simplement le nombre de tuplets de R'.

Λ₀ est un **langage** uniquement **de consultation** : il ne permet pas d'effectuer des créations, des suppressions ou des mises à jour.

C'est un **langage relationnel très restreint** car il opère sur des relations mais les seules opérations qu'il autorise sur les relations sont la sélection et la projection.

Mais il offre plus de possibilités que la plupart des langages de systèmes de bases de données pour sélectionner les tuplets d'une relation définie sur des domaines de données textuelles. C'est ce qui en fait un **langage spécialisé pour la consultation de données textuelles**. Nous allons décrire ces possibilités dans les paragraphes suivants.

#### IV. LETTRES, MOTS, PHRASES, PARAGRAPHES.

Dans beaucoup de langages d'interrogation de bases de données les domaines des relations manipulées sont de deux types ; ou bien il s'agit d'un ensemble de nombres ou bien il s'agit d'un ensemble de chaînes de caractères. Pour le traitement de texte, il est utile de considérer un texte, non pas comme une simple chaîne de caractères, mais par exemple comme une chaîne de phrases, chacune d'elles étant une chaîne de mots construits sur un alphabet donné. Plus précisement soit α un ensemble fini, dont les éléments sont appelés **lettres**. Un mot sur α est une élément du monoïde α*. Une phrase sur α est un élément de (α*)* et un paragraphe sur α un élément de ((α*)*)*. A partir de maintenant nous supposerons α fixé.
Λ<sub>o</sub> opère sur des relations R(A<sub>1</sub> : DA<sub>1</sub>, ..., A<sub>n</sub> : DA<sub>n</sub>) qui ont la propriété suivante : pour tout i, 1 ≤ i ≤ n, ou bien DA<sub>i</sub> est un ensemble de nombres, ou bien DA<sub>i</sub> ⊂ α ou DA<sub>i</sub> ⊂ α* ou DA<sub>i</sub> ⊂ (α<sup>*</sup>) ou DA<sub>i</sub> ⊂ ((α<sup>*</sup>)<sup>*</sup>); on dira qu'un attribut est de **type** nombre, lettre, mot, phrase ou paragraphe.
Pour la commodité de la description on utilise des numéros : type 0, 1, 2, 3, 4 pour type nombre, lettre, mot, phrase, paragraphe, et on pose :
L1 = α ∪ {lettre vide}, L2 = α<sup>*</sup>, L3 = (α<sup>*</sup>)<sup>*</sup>, L4 = ((α<sup>*</sup>)<sup>*</sup>)<sup>*</sup>; est de type texte tout ce qui n'est pas de type nombre.

V. REPRESENTATION DES CONSTANTES DE TYPE TEXTE.

Une lettre est représentée par un caractère éventuellement vide
entre < >. Un mot est représenté par une chaîne, éventuellement vide,
de représentations de lettres entre [ ]. D'une façon générale une donnée
de type n ≥ 2 est représentée par une chaîne éventuellement vide de
représentations de données de type n - 1, entre [ ] pour n = 2, $ $
pour n = 3 et \\ pour n = 4.

Exemples :

\$\$on\$\$dit\$\$que\$\$le\$\$sous-programme\$\$est\$\$récursif\$\$ \$\$ \$prenons\$
\un\$\$exemple\$\$type\$\$ \$\$

est une représentation de paragraphe. Pour améliorer la lisibilité on a
supprimé les chevrons.

La relation

DOCUMENT (CLE1 : nombre, CLE2 : mot, CLE3 : mot, AUTEUR : paragraphe,
TITRE : phrase, DESCRIPTEUR : paragraphe, DATE : nombre)

nous servira d'exemple pour la suite.
Voici un tuplet de DOCUMENT :

(8200, emelichev, properties, \§ [emelichev] v. []a. §§ [kravtsov]
[m.][k.]
§\, § [some] properties [of] vertices §, \§ [topology] §
§ [algebra] §§ [transport] polyhedra §\, 1976)

CLE1, CLE2, CLE3, sont les noms des trois attributs clés qui sont
utilisés pour le classement des tuplets de DOCUMENT. L'attribut AUTEUR
est de type paragraphe car il peut y avoir plusieurs auteurs ; la première
phrase identifie le premier auteur, la deuxième le deuxième auteur. Chaque
auteur est décrit par une phrase qui comporte d'abord le mot nom puis le
ou les mots initiales. De même pour l'attribut DESCRIPTEUR, les différentes
phrases correspondant à ce qu'on appelle d'habitude les différents mots-
clé. Par contre le titre comporte une seule phrase.

VI. FORME GENERALE DU PREDICAT DE SELECTION P.

P est de la forme $P_1 \underline{\ ET } P_2$. P₁ est relatif aux 3 attributs clés et
P₂ est relatif à tous les attributs. Appelons CLE1, CLE2, CLE3 les noms
des attributs clés.

$P_1$ est de la forme $(Q_{11}) \underline{\ ET } (Q_{12}) \underline{\ ET } (Q_{13})$ où chaque $Q_{li}$ est de la
forme $(R_{li1}) \underline{\ OU } (R_{li2}) \dots \underline{\ OU } (R_{lik})$ où chaque $R_{lij}$, $1 \le j \le k$, est un
prédicat élémentaire, de l'une des formes a), b) ou c) ci-dessous,
relatif à CLEi.

$P_2$ est une combinaison bouléenne quelconque de prédicats élémentaires
avec les opérateurs bouléens **OU**, **ET**.

Les prédicats élémentaires sont relatifs à _un seul_ attribut. Nous
les décrivons ci-après avec des exemples pour lesquels $P_1$ est vide.
## VII. PREDICATS ELEMENTAIRES

Ils sont de l'une des 4 formes suivantes :

a) nom-d'attribut op1 constante

$$où \ op1 \in \{=, >, >=, <, <=\}$$

Si nom-d'attribut est le nom d'un attribut de type texte, op1 ne peut être que = .

11. "Trouver le titre des documents publiés après 1972 par W.C. FIELDS"

TROUVER TITRE
DANS DOCUMENT
AVEC (DATE > 1972) ET (AUTEUR = \$ fields w. c. \$)

b) nom-d'attribut APPARTIENT A liste-de-constantes.

12. "Trouver l'auteurs et le titre des documents publiés en 1972 et 1973"

TROUVER AUTEUR, TITRE
DANS DOCUMENT
AVEC DATE APPARTIENT A (1972, 1973)

c) nom-d'attribut ENTRE constante ET constante
(au sens de $y_1 \le x \le y_2$)

13. "Trouver le titre des documents publiés entre 1970 et 1978"

TROUVER TITRE
DANS DOCUMENT
AVEC DATE ENTRE 1970 ET 1978
d) nom-d'attribut **APPARTIENT A** structure-syntaxique où l'attribut est de type texte et où structure-syntaxique est un ensemble de constantes qui n'est pas représenté par une liste. L'objet du paragraphe suivant est de définir la classe des structures syntaxiques admissibles.

VIII. REPRESENTATION D'UN ENSEMBLE DE CONSTANTES DE TYPE TEXTE PAR LEUR STRUCTURE SYNTAXIQUE.

Λ₀ permet de tester si une phrase donnée commence par un mot donné, ou par un mot qui contient un ensemble de lettres donné, ou si une phrase donnée contient un mot qui contient lui-même un ensemble de lettres donné, etc.... Pour cela on construit l'ensemble des éléments qui ont la propriété cherchée et on emploie l'opérateur **APPARTIENT A**.

I4. "Trouver le titre des documents dont le titre commence par ANALYSE".

**TROUVER** TITRE
**DANS** DOCUMENT
**AVEC** TITRE APPARTIENT A $ \cap \text{analyse} \cup \text{PHRASE} \}$

La suite de symboles qui figure à droite de l'opérateur **APPARTIENT A** représente l'ensemble des phrases de la forme $u_0 v$ où $u_0 = \text{analyse}$ et où $v$ est une phrase quelconque. Elle définit une occurence de la structure de données "structure syntaxique de phrase". Λ₀ admet les structures syntaxiques de lettres, de mots, de phrases et de paragraphes. Une constante donnée appartient ou n'appartient pas à un structure syntaxique donnée.
Les règles R1,...,R9 ci-dessous définissent constructivement l'ensemble S des structures syntaxiques représentables dans $\Lambda_o$ et leurs représentations. On note $r(x)$ la représentation d'un élément x de S. S est un ensemble de sous-ensembles de L1, L2, L3, et L4. Rappelons que : $L1 = \alpha \cup \text{lettre vide}$, $L2 = \alpha^*$, $L3 = (\alpha^*)^*$ et $L4 = ((\alpha^*)^*)^*$.

Un sous-ensemble de $L_n$ est dit de type n. On note $d_n$ et $f_n$ les symboles caractéristiques des éléments de $L_n$, $1 \le n \le 4$.

$$d_1 = \langle, f_1 = \rangle, d_2 = f_2 = \Box, d_3 = f_3 = \$ , d_4 = f_4 = \backslash.$$

R1. Après l'opérateur **APPARTIENT A** une chaîne de symboles commençant par $d_n$ et finissant par $f_n$ dénote une structure syntaxique de type n.□

R2. S contient tous les sous-ensembles à un élément de L1, L2, L3, L4 et ces sous-ensembles admettent les mêmes représentations que les éléments correspondants. De plus S contient L1, $\overline{L1}$, L2, $\overline{L2}$, L3, $\overline{L3}$, L4, $\overline{L4}$ ($\overline{L1}$ dénote $LI - \{VIDE\}$) qui sont respectivement représentés par [LETTRE], [LETTRE NON VIDE], [MOT], [MOT NON VIDE], [PHRASE], [PHRASE NON VIDE], [PARAGRAPHÉ], [PARAGRAPHÉ NON VIDE].□

R3. Soit $E_n \in S$, $E_n \subset L_n$, $r(E_n)$ sa représentation, $1 \le n \le 3$. Alors S contient le sous-ensemble $E_{n+1}$ des éléments de $L_{n+1}$ qui sont réduits à un élément de $E_n$, et $r(E_{n+1}) = d_{n+1} \cdot r(E_n) \cdot f_{n+1}$.□

R4. Soient $E_n$ et $F_n$ deux sous-ensembles de $L_n$ qui appartiennent à S, $1 \le n \le 3$. Alors le sous-ensemble $E_{n+1}$ des éléments de $L_{n+1}$ qui peuvent s'écrire comme la concatenation d'un élément de $E_n$ et d'un élément de $F_n$ appartient à S et

$$r(E_{n+1}) = d_{n+1} \cdot r(E_n) \cdot r(F_n) \cdot f_{n+1}. \Box$$
Par exemple à partir de la lettre a <a> et de l'ensemble des lettres non vides <[LETTRE NON VIDE]> on peut construire l'ensemble des mots de 2 lettres qui finissent par a [<LETTRE NON VIDE>] <a> [].

R5. Soient $E_n$ et $E_{n+1}$ deux éléments de $S$, $E_n \subset L_n$, $E_{n+1} \subset L_{n+1}$, $r(E_n) = R_n$, $r(E_{n+1}) = d_{n+1} R_{n+1} f_{n+1}$. Alors S contient $F_{n+1}$ l'ensemble des éléments de $L_{n+1}$ qui peuvent s'écrire comme la concaténation d'un élément de $E_n$ et d'un élément de $E_{n+1}$, et $r(F_{n+1}) = d_{n+1} R_n R_{n+1} f_{n+1}$.
De même S contient $G_{n+1}$ tel que $r(G_{n+1}) = d_{n+1} R_{n+1} R_n f_{n+1}$.

Par exemple à partir de l'ensemble des mots qui finissent par a [MOT] <a> [ ] et de la lettre b <b> on peut construire [MOT] <a> <b> [ ] l'ensemble des mots qui finissent par a b.

Les règles R1, R2, R3, R4, R5 suffisent pour exprimer en $\Lambda_o$ la requête.

I4. "Trouver l'auteur et le titre des documents dont le premier auteur a un nom qui commence par EMELI et qui se termine par EV, dont un autre auteur a BORIS parmi ses prénoms et a un nom qui contient les lettres K, R, I dans cet ordre mais non nécessairement contigues".

TROUVER AUTEUR, TITRE

DANS DOCUMENT

AVEC AUTEUR APPARTIENT A

$\backslash$

[emeli [MOT] ev]

[PHRASE]

$\backslash$

[PARAGRAPHE]

$\backslash$

[(MOT) k (MOT) r (MOT) i (MOT)]

[PHRASE]

[b. ]

[PHRASE]

$\backslash$

[PARAGRAPHE]

$\backslash$
On ne peut pas exprimer simplement avec les règles ci-dessus le
fait qu'un mot contient les lettres A,B,C dans un ordre quelconque. Pour
cela on ajoute la règle R6.

R6. Soient $E_n$ et $E'_n$ deux éléments de $S$, $1 \le n \le 4$, $E_n \subset L_n$,
$E'_n \subset L_n$, $r(E_n) = d_n R_n f_n$, $r(E'_n) = d_n R'_n f'_n$. Alors $S$ contient $E_n \cup E'_n$ et
$E_n \cap E'_n$, et l'on a :

$$
r(E_n \cup E'_n) = d_n (R_n) \underline{\cup} (R'_n) f_n
$$

$$
r(E_n \cap E'_n) = d_n (R_n) \underline{\cap} (R'_n) f_n
$$

Les parenthèses peuvent être supprimées s'il n'y a pas d'ambiguïté. [ ]

L'utilisation de R6 est illustrée par l'instruction suivante :

15. "Trouver l'auteur et le titre des documents indexés par au moins une phrase qui contient le mot POLYHEDRE, au singulier ou au pluriel, et un mot qui commence par TOPOL ou par CALC".

TROUVER AUTEUR, TITRE

DANS DOCUMENT

AVEC DESCRIPTEUR APPARTIENT A

[PARAGRAPHÉE]

§

([PHRASE])

☐polyhedre [LETTRE] ☐

[PHRASE])

ET

([PHRASE])

[]

(topol [MOT])

OU

(calc [MOT])

[]

[PHRASE])

§

[PARAGRAPHÉE]

"
## CONTIENT.

Afin de rendre la requête 15 plus lisible on peut encore l'écrire, en utilisant le symbole réservé **CONTIENT** de la façon suivante :

**TROUVER** AUTEUR, TITRE
**DANS** DOCUMENT
**AVEC** DESCRIPTEUR APPARTIENT A

\**CONTIENT** (§**CONTIENT** (☐**polyhedre** [LETTRE]☐**ET** ☐ (topol [MOT])) **OU** (calc [MOT]) ☐)
§)

\

L'utilisation de **CONTIENT** est formalisée dans la règle suivante :

R7. Soit $E_n \subset S$, $E_n \subset L_n$, $2 \le n \le 4$, tel que $r(E_n)$ est de la forme:

$d_n(\dots((R_{n-1}^1) \underline{\underline{ET}} (R_{n-1}^2)) \underline{\underline{OU}} ((R_{n-1}^3) \underline{\underline{OU}} (R_{n-1}^4))\dots f_n$

avec, pour tout $i, R_{n-1}^i$ de la forme [LETTRE] $\rho_{n-1}^i$ [LETTRE] ou [MOT] $\rho_{n-1}^i$ [MOT] ou [PHRASE] $\rho_{n-1}^i$ [PHRASE] suivant que $n$ vaut 2,3 ou 4, et $\rho_{n-1}^i = r(E_{n-1}^i)$, $E_{n-1}^i \in S$ et $E_{n-1}^i \subset L_{n-1}$ ; c'est-à-dire que $r(E_n)$ est de la forme $d_n R_n f_n$ où $R_n$ est une chaîne de parenthèses, de **ET**, de **OU** et de représentations de sous-ensembles de $L_n$ caractérisés par le fait qu'ils contiennent un élément d'un sous-ensemble donné de $L_{n-1}^1$. $E_n$ est l'ensemble des éléments de $L_n$ qui contiennent un élément de $E_{n-1}^1$ et un élément de $E_{n-1}^2$ ou bien qui contiennent un élément de $E_{n-1}^3$ ou un élément de $E_{n-1}^4$, etc.... Alors $E_n$ admet une deuxième représentation

$$r'(E_n) = d_n \underline{\underline{CONTIENT}} (\dots((\rho_{n-1}^1) \underline{\underline{ET}} (\rho_{n-1}^2)) \underline{\underline{OU}} ((\rho_{n-1}^3) \underline{\underline{OU}} (\rho_{n-1}^4))\dots f_n)$$
CONTIENT AU MOINS ... PARMI ...

On peut définir l'ensemble des éléments de $L_n$ qui contiennent au moins p éléments parmi q éléments de $L_{n-1}$ et plus généralement

R8. Soient q sous-ensembles de $L_{n-1}$, $E_{n-1}^1, \dots, E_{n-1}^q$, $2 \le n \le 4$, avec, pour tout i, $E_{n-1}^i \in S$ et r ($E_{n-1}^i$) = $R_{n-1}^i$. Alors l'ensemble $E_n$ défini de la façon suivante appartient à S. $E_n$ est le sous-ensemble des éléments de $L_n$ qui contiennent p éléments de $L_{n-1}$, $x_1, \dots, x_p$ tels que, quel que soit i compris entre l et p, il existe un entier $j_i$ compris entre l et q tel que $x_i \in E_{n-1}^j$, et les entiers $j_i$, $1 \le i \le p$, sont distincts 2 à 2. Et l'on a :

$$r(E_n) = d_n \underset{\text{CONTIENT AU MOINS p ? PARMI}}{\underbrace{\text{R8. Soient q sous-ensembles de } L_{n-1}, E_{n-1}^1, \dots, E_{n-1}^q, 2 \le n \le 4, \text{ avec, pour tout } i, E_{n-1}^i \in S \text{ et r } (E_{n-1}^i) = R_{n-1}^i. \text{ Alors l'ensemble } E_n \text{ défini de la façon suivante appartient à S. } E_n \text{ est le sous-ensemble des éléments de } L_n \text{ qui contiennent p éléments de } L_{n-1}, x_1, \dots, x_p \text{ tels que, quel que soit } i \text{ compris entre } l \text{ et } q \text{ tel que } x_i \in E_{n-1}^j, \text{ et les entiers } j_i, 1 \le i \le p, \text{ sont distincts 2 à 2. Et l'on a :}}}}}{\underbrace{(R_{n-1}^1, \dots, R_{n-1}^q) \in_n}}$$

où ? est LETTRES, MOTS ou PHRASES suivant la valeur de n. ☐

16. "Trouver l'auteur des documents dont le titre contient au moins 2 mots parmi BASE, DONNEES et un mot qui commence par COMPL".

TROUVER AUTEUR
DANS DOCUMENT
AVEC TITRE APPARTIENT A

§
CONTIENT AU MOINS 2 MOTS PARMI
(☐base☐,
☐données☐,
☐compl [MOT]☐)
§

A ? ? PRES

Enfin on peut définir, par exemple, l'ensemble des mots qui sont égaux à un mot donné à p fautes d'orthographe près.
Définition 1.

Un mot u est égal à un mot v à p lettres près si on peut obtenir
v à partir de u par p opérations élémentaires, les opérations élémentaires
étant l'addition d'une lettre, la suppression d'une lettre et la sub-
stitution d'une lettre par une autre. ⌜

Par exemple MATIN est égal à MARTIN à une lettre près car
MATIN + R → MARTIN mais MRXTIN est égal à MARTIN à 2 lettres près car
MARTIN = MRTIN + A et MRTIN = MRXTIN - X et il n'existe par de transfor-
mation permettant d'obtenir MARTIN à partir de MRXTIN en une seule
opération élémentaire.

Plus généralement, pour 2 ≤ n ≤ 4,

Définition 2.

Un élément u de L_n est égal à un élément v de L_n à p ? près, où
? = lettres, mots ou phrases, si on peut obtenir v à partir de u par p
opérations élémentaires, celles-ci étant l'addition d'un élément de L_{n-1},
la suppression d'un élément de L_{n-1} et la substitution d'un élément de
L_{n-1} par un autre.

R9. Soit n ≥ 2 et E_n = {x_n} un sous-ensemble de L_n appartenant à S et contenant un seul élément : x_n. Soit r(E_n) = d_n R_n f_n sa représentation. Alors S contient aussi le sous-ensemble E_n^P des éléments de L_n qui sont égaux à x_n à p ? près et

$$
r(E_n^P) = d_n \mathbb{R} [\underline{A} \ p \ ? \ \underline{PRES}] f_n
où \ ? = \underline{LETTRES} \ si n = 1, \ \underline{MOTS} \ si n = 2 \ et \ \underline{PHRASES} \ si n = 3. \blacksquare
$$
17. "Trouver l'ensemble des documents qui ont été écrits par les individus dont le nom s'écrit WOSZNIAKOWSKI à 2 lettres près".

TROUVER *
DANS DOCUMENTS
AVEC AUTEUR APPARTIENT A

/CONTIENT
$ woszniakowski [A 2 LETTRES PRES]$
/

Le symbole * qui suit **TROUVER** remplace la liste complète des noms d'attribut de DOCUMENTS.

## IX. IDENTIFIEURS DE STRUCTURES SYNTAXIQUES.

On peut identifier une structure syntaxique, c'est-à-dire un élément de S, par un identifieur. Dans ce cas on doit le déclarer dans une clause **JE DECLARE** qui doit précéder la clause **TROUVER**.

Exemple :

JE DECLARE X = / CONTIENT
$ woszniakowski [A 2 LETTRES PRES]
$

TROUVER *
DANS DOCUMENTS
AVEC AUTEUR APPARTIENT A X
## X. LA CLAUSE ORDONNER PAR.

Une requête de $\Lambda_o$ peut se terminer par une clause **ORDONNER PAR**. Par cette clause l'utilisateur demande que les tuplets de la relation résultat lui soient renvoyés dans un certain ordre. **ORDONNER PAR** est suivi d'une liste $C_1, ..., C_k$ où $C_i$ est soit un identificateur qui a été déclaré au début de la requête, soit un nom d'attribut. Les tuplets sont classés suivant le critère $C_1$, en cas d'égalité par rapport à ce critère, suivant le critère $C_2$, etc.... Si $C_i$ est un nom d'attribut le critère est l'ordre ascendant ou descendant défini par le domaine de $C_i$ ; c'est l'ordre alphabétique si $C_i$ est un domaine textuel. Si $C_i$ est un identificateur, ce doit être celui d'une structure syntaxique contenant les mots réservés

**CONTIENT, AU MOINS ? PARMI ? ou A ? ? PRES.**

Dans ce cas un critère de classification sera engendré automatiquement. Nous nous contentons ici, sans rentrer dans plus de détails, de donner un exemple.

18. "Trouver l'ensemble des documents de DOCUMENT dont le titre contient au moins 2 mots parmi BASE, DONNEES, et un mot qui commence par COMPL. Les ordonner suivant le nombre de coïncidences".

JE DECLARE X =
$ CONTIENT AU MOINS 2 MOTS PARMI
( base , données , compl [MOT])
$

TROUVER *
DANS DOCUMENTS
AVEC TITRE APPARTIENT A X
ORDONNER PAR X

La machine classera d'abord les documents dont les titres contiennent à la fois BASE, DONNEES et COMPL., ensuite ceux qui ne contiennent que 2 mots parmi les 3.
XI. LA VALEUR VIDE.

Un attribut peut prendre la valeur VIDE. Par exemple la valeur de
l'attribut DATE pour un document dont on ne connait pas la date de publi-
cation sera VIDE. De même une composante d'une valeur d'attribut de type
texte peut être vide. C'est le cas de la composante 2° auteur de l'attribut
AUTEUR d'un document écrit par une seule personne. Pour déterminer si un
tuplet donné satisfait la clause AVEC d'une question, on doit donc tenir
compte de cette éventualité. La méthode est la suivante : On assigne aux
prédicats qui testent des valeurs nulles la valeur de vérité ?. La valeur
de vérité de la clause AVEC est ensuite calculée en utilisant une logique
à trois valeurs pour évaluer les ET et les OU. Le tuplet est considéré
comme satisfaisant à la condition si la valeur de vérité de la clause
est VRAI mais non si sa valeur de vérité est FAUX ou ?. Les règles
d'évaluation sont :

x <u>OU</u> ? = x, VRAI <u>ET</u> ? = ?, FAUX <u>ET</u> ? = FAUX .

Remerciements.

Ce travail a été réalisé en collaboration étroite avec mes collègues
du projet "Systemes de Consultation de Données" : A. El Masri, J. Flores,
L. Hyafil, J. Rohmer, F. Schwab, D. Serain, E. Supik, D. Tusera.
## XII. BIBLIOGRAPHIE.

[1] E.A. Ozkarahan, S.A. Schuster et K.C. Smith, "RAP-- an associative processor for data base management", Proceedings of the National Computer Conference (AFIPS 1975), Vol. 44, pp 379-387.

[2] S.Y.W. Su, et G.J. Lipowski, "CASSM : a cellular system for very large data bases", Proceedings of the International Conference on Very Large Data Bases, Farmington, MA, (1975), pp 456-472.

[3] M.J. McGill, Sigir-Sigarch-Sigmod Third Workshop On Computer Architecture For Non-Numeric Processing (Syracuse, New York, 1977 May 17-18), Sigarch Vol VI NO. 2, Sigir Vol XII NO. 1, Sigmod Vol IX NO. 2.

[4] L. Hyafil, J.P. Van de Wiele, "La recherche tridimensionnelle", note technique du projet LABORIA "Systèmes de Consultation de Données" N° 1 (Décembre 1976), IRIA-LABORIA, Domaine de Voluceau, Rocquencourt, 78150 Le Chesnay.

[5] D. Tusera, "Architecture du Système de Commande", note technique du projet SCD N° 2 (Décembre 1976).

[6] J. Rohmer, D. Tusera, "Structures matérielles pour le filtrage des informations textuelles", note technique du projet SCD N° 3 (Décembre 1976).

[7] D. Tusera, "Filtre-aide à la programmation. Principe de fonctionnement du langage machine du filtre", note technique du projet SCD, à paraître.
[8] F. Schwab, D. Serain, "Communication MITRA 125 - Contrôleur", note technique du projet SCD N° 4 (Juillet 1977).

[9] J.P. Van de Wiele, "Le(s) langage(s) de Requête. Présentation générale", note technique du projet SCD N°5 (Septembre 1977).

[10] A. El Masri, "Remarques Préliminaires à la Conception du Tampon", note technique du projet SCD N° 6 (Octobre 1977).
# Annexe : Syntaxe simplifiée de $\Lambda_o$ en BNF.

Cette syntaxe est simplifiée. Un certain nombre de contraintes
seront précisées au cours de la réalisation de l'interpréteur.

{ } signifie "optionnel".

| signifie "ou".

::= signifie "se décompose en".

Entre deux composantes intervenant à droite de ::= figure au moins
un blanc. Il peut y en avoir plusieurs.

requête ::= {clause-de-déclaration} clause-de-recherche
{clause-de-classification}

clause-de-projection ::= clause-trouver clause-dans

clause-trouver ::= **TROUVER** liste-de-noms-d'attribut
| **COMPTER** liste-de-noms-d'attribut

liste-de-noms-d'attribut ::= nom-d'attribut
| liste-de-noms-d'attribut, nom-d'attribut
| *

clause-dans ::= **DANS** nom-de-relation

clause-de-sélection ::= **AVEC** prédicat-de-sélection

prédicat-de-sélection ::= {prédicat-de-clés} ET prédicat-de-balayage
prédicat-de-clés ::= terme-de-clés
| prédicat-de-clés ET terme-de-clés

terme-de-clés ::= prédicat-élémentaire
| terme-de-clés OU prédicat-élémentaire

prédicat-de-balayage ::= terme-de-balayage
| prédicat-de-balayage OU terme-de-balayage

terme-de-balayage ::= élément-de-balayage
| terme-de-balayage ET élément-de-balayage

élément-de-balayage ::= prédicat-élémentaire
| (prédicat-de-balayage)

prédicat-élémentaire ::= nom-d'attribut op1 constante-numérique
| nom-d'attribut = constante-textuelle
| nom-d'attribut APPARTIENT A
(liste-de-constantes)
| nom-d'attribut ENTRE constante ET constante
| nom-d'attribut APPARTIENT A
structure-syntaxique

op1 ::= | > | > = | < | < =

liste-de-constantes ::= constante
| liste-de-constantes, constante

constante ::= constante-numérique | constante-textuelle

constante-textuelle ::= 1-constante | 2-constante | 3-constante
| 4-constante
POUR $1 \le i \le 4$

i-constante ::= $d_i$ corps-de-i-constante $f_i$
                  | $d_i$ $f_i$.

$d_1$ ::= <, $f_1$ ::= >, $d_2$ ::= $f_2$ ::= □

$d_3$ ::= $f_3$ ::= $\$$, $d_4$ ::= $f_4$ ::= \\

corps-de-l-constante ::= caractère

POUR $2 \le i \le 4$

corps-de-i-constante ::= chaîne-de-(i-1)- constantes

chaîne-de-(i-1)-constantes ::= (i-1)-constante
                                | chaîne-de-(i-1)-constantes
                                (i-1)-constante

structure-syntaxique ::= structure-1-syntaxique
                       | structure-2-syntaxique
                       | structure-3-syntaxique
                       | structure-4-syntaxique

POUR $1 \le i \le 4$

structure-i-syntaxique ::= $d_i$ corps-de-i-structure $f_i$.

corps-de-l-structure ::= terme-de-l-structure
                        | corps-de-l-structure OU terme-de-l-structure
terme-de-l-structure ::= élément-de-l-structure
| terme-de-l-structure ET élément-de-l-structure

élément-de-l-structure ::= corps-de-l-constante
| LETTRE
| LETTRE-NON-VIDE
| (corps-de-l-structure)

POUR $2 \le i \le 4$

corps-de-i-structure ::= terme-de-i-structure
| corps-de-i-structure OU terme-de-i-structure
| CONTIENT (complexe-(i-1)-syntaxique)
| CONTIENT AU MOINS constante-numérique ?-(i-1)
| PARMI (liste-de-structures-(i-1)-syntaxiques)

terme-de-i-structure ::= élément-de-i-structure
| terme-de-i-structure ET élément-de-i-structure

élément-de-i-structure ::= corps-de-i-constante
| corps-de-i-constante
| [A constante-numérique ?-(i-1) PRES]
| i-symbole-générique
| structure-(i-1)-syntaxique
| structure-(i-1)-syntaxique
| structure-(i-1)-syntaxique
| corps-de-i-structure
| structure-(i-1)-syntaxique
| structure-(i-1)-syntaxique
| corps-de-i-structure
?-1 ::= LETTRES , ?-2 ::= MOTS , ?-3 ::= PHRASES

2- symbole-générique ::= MOT | MOT NON VIDE

3- symbole-générique ::= PHRASE | PHRASE NON VIDE

4- symbole-générique ::= PARAGRAPHE | PARAGRAPHE NON VIDE

POUR 1 ≤ i ≤ 3

complexe-i-syntaxique ::= terme-i-complexe
| complexe-i-syntaxique OU terme-i-complexe

terme-i-complexe ::= élément-i-complexe
| terme-i-complexe ET élément-i-complexe

élément-i-complexe ::= structure-i-syntaxique
| (complexe-i-syntaxique)

liste-de-structures-i-syntaxiques ::= structure-i-syntaxique
| liste-de-structures-i-syntaxiques,
structure-i-syntaxique

clause-de-déclaration ::= JE DECLARE (liste-de-déclarations)

liste-de-déclarations ::= déclaration
| liste-de-déclarations, déclaration

déclaration ::= identifieur = structure-syntaxique

clause-de-classification ::= ORDONNER PAR liste-de-critères-de-classification
liste-de-critères-de-classification ::= critère-de-classification | liste-de-critères-de-classification, critère-de-classification

critère-de-classification ::= nom-d'attribut {direction} | identifieur

direction ::= ASC | DESC

**Remarque.** Les terminaux de cette syntaxe simplifiée sont les symboles réservés qui sont soulignés et en lettres majuscules, les opérateurs arithmétiques et les symboles :

"nom-d'attribut", "nom-de-relation", "caractère", "constante-numérique", "identifieur".

Ces derniers termes seront précisés à l'implémentation.