# Une plate-forme dynamique pour l'évaluation des performances des bases de données à objets

Zhen He, Jérôme Darmont

► To cite this version:

Zhen He, Jérôme Darmont. Une plate-forme dynamique pour l'évaluation des performances des bases de données à objets. Revue des Sciences et Technologies de l'Information - Série ISI: Ingénierie des Systèmes d'Information, 2004, 9 (1), pp.109-127. 10.3166/isi.9.1.109-127. hal-01448650

HAL Id: hal-01448650

https://hal.science/hal-01448650v1

Submitted on 1 Feb 2017

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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Une plate-forme dynamique pour l'évaluation des
performances des bases de données à objets

Zhen He* et Jérôme Darmont**

*Department of Computer Science
University of Vermont
Burlington, VT 05405, USA
zhenhe@emba.uvm.edu

**ERIC, Université Lumière Lyon 2
5 avenue Pierre Mendès-France
F-69676 Bron cedex
jerome.darmont@univ-lyon2.fr

Abstract

Dans les bases de données orientées-objets ou relationnelles-objets, les séquences d'accès aux objets ne sont pas statiques : les applications n'accèdent pas systématiquement aux mmes objets dans le mme ordre. C'est néanmoins en utilisant de telles séquences d'accès que les performances de ces systèmes de gestion de bases de données et de techniques d'optimisation associées telles que le regroupement ont été évaluées jusqu'ici. Cet article propose une plate-forme dynamique pour l'évaluation des performances des bases de données à objets baptisée DOEF. DOEF permet des évolutions de séquence d'accès par la définition de styles d'accès paramétrables. De nouveaux modèles d'évolution de séquence d'accès peu-vent facilement tre inclus dans notre plate-forme. Pour illustrer les possibilités offertes par DOEF, nous avons mené deux séries d'expérimentations dans lesquelles nous avons comparé les performances de quatre algorithmes de regroupement d'objets dynamiques et de deux gestionnaires d'objets persistants : Platypus et SHORE.

**Mots clés :** bases de données orientées-objets et relationnelles-objets, bancs d'essais, évaluation de performance, regroupement.
# 1 Introduction

L'évaluation de performance est une tâche critique à la fois pour les concepteurs de Systèmes de Gestion de Bases de Données à Objets<fnref n="1" /> (architecture ou optimisation) et leurs utilisateurs (comparaison de performance, optimisation). Traditionnellement, ces évaluations s'effectuent à l'aide de bancs d'essais constitués de modèles de charge synthétiques (bases de données et opérations) et de mesures de performance. Aucun des bancs d'essais conçus pour les SGBDO ne permet de modifier en cours de test les séquences d'accès aux objets. Cependant, dans la réalité, la plupart des applications n'accèdent pas de manière répétitive au même ensemble d'objets, dans le même ordre. Par ailleurs, aucune des nombreuses études concernant le regroupement (clustering) dynamique d'objets ne contient d'indication sur la manière dont les algorithmes proposés réagissent dans un tel environnement dynamique.

La capacité d'adaptation aux évolutions de séquence d'accès est pourtant critique pour obtenir de bonnes performances. Optimiser une base de données pour bien répondre à une séquence d'accès particulière peut d'ailleurs entraner des dégradations de performance importantes lorsque d'autres séquences d'accès sont employées. De plus, l'étude des performances d'un système sur une seule trace donnée fournit peu d'indications aux concepteurs d'un système, qui ont besoin de cerner et d'optimiser le comportement des composants de leur système dans différents cas d'utilisation.
En opposition aux bancs d'essais du TPC [TPC02], qui proposent des outils d'évaluation *standardisés* permettant aux vendeurs et aux clients de comparer des systèmes, l'objectif de notre plate-forme DOEF (*Dynamic Object Evaluation Framework*) est de leur permettre d'explorer les performances d'un SGBDO pour *différents* modèles d'évolution de séquence d'accès aux données.

DOEF est une première tentative de modélisation du comportement dynamique d'une application. La plate-forme décrit un ensemble de protocoles qui définissent à leur tour un ensemble de modèles d'évolution de séquence d'accès. DOEF a été conçu comme une surcouche logicielle d'OCB [DS00], qui est un banc d'essais générique capable de simuler le comportement des principaux bancs d'essais orientés-objets. DOEF réutilise la base de données très riche et les opérations d'OCB. En tant que surcouche, DOEF est facile à ajouter sur toute implémentation existante d'OCB.

DOEF ne comprend certainement pas tous les styles d'accès possibles. Cependant, nous avons conçu notre plate-forme pour treize totale-ment extensible. D'une part, il est facile d'y inclure de nouveaux modèles d'évolution de séquence d'accès. D'autre part, le modèle générique d'OCB peut tre implémenté dans un système relationnel-objet et la plupart de ses opérations demeurent pertinentes. DOEF peut donc également tre utilisé dans un contexte relationnel-objet.

Pour illustrer les possibilités offertes par DOEF, nous avons dans un premier temps évalué les performances de quatre algorithmes de regroupe-

<footnote n="1">¹Dans la suite de cet article, nous utilisons les termes Systèmes de Gestion de Bases de Données à Objets (SGBDO) pour désigner indifféremment les systèmes orientés-objets et relationnels-objets. La plupart des SGBD multimédias et XML sont des SGBDO.</footnote>
ment dynamique d'objets, et ce pour trois raisons. Premièrement, le regroupement d'objet est une technique d'optimisation des performances efficace [GKM96]. Deuxièmement, les performances des algorithmes de regroupement dynamique d'objets sont très sensibles aux évolutions de séquence d'accès. Troisièmement, malgré cela, les performances de ces techniques n'ont jamais été évaluées dans cette optique. Finalement, afin de tester l'efficacité de DOEF pour évaluer les performances de systèmes réels, nous avons également comparé les performances de deux gestionnaires d'objets persistants existants.

Cet article est organisé comme suit. La section 2 décrit brièvement les bancs d'essais pour SGBDO. La section 3 présente le banc d'essais OCB. La section 4 détaille les spécifications de la plate-forme DOEF. Nous présentons les résultats expérimentaux que nous avons obtenus dans la section 5. Finalement, nous concluons cet article et présentons quelques perspectives de recherche dans la section 6.

## 2 Bancs d'essais existants

Nous décrivons ici les principaux bancs d'essais pour SGBDO, hormis OCB, qui ont été proposés dans la littérature. Il est important de noter qu'aucun d'eux ne présente de comportement dynamique.

Les bancs d'essais orientés-objets, dont les principaux sont OO1 [Cat91], HyperModel [ABM+90], OO7 [CDN93] et Justitia [Sch94], ont tous été conçus pour modéliser des applications d'ingénierie (CAO, AGL, etc.). Leur spectre s'étend d'OO1, qui présente un schéma très simple (deux classes) et seulement trois opérations, à OO7, qui est plus générique et fournit un schéma complexe et paramétrable (dix classes), ainsi qu'une gamme d'opérations étendue (quinze opérations complexes). Justitia présente la particularité de prendre en compte des utilisateurs multiples, ce qui lui permet de mieux modéliser des applications de type client-serveur. Néanmoins, mme le schéma d'OO7 demeure statique et n'est pas suffisamment générique pour modéliser d'autres types d'applications que des applications d'ingénierie (comme des applications financières, multimédias, ou de télécommunication, par exemple [TNL95]). De plus, chaque pas vers une plus grande complexité a rendu ces bancs d'essais de plus en plus difficiles à implémenter.

Les bancs d'essais relationnels-objets, tels que BUCKY [CDN+97] et BORD [LKK00], sont orientés-requtes et uniquement dédiés aux systèmes relationnels-objets. Par exemple, BUCKY ne propose que des opérations spécifiques de ces systèmes, considérant que la navigation typique parmi des objets est déjà traitée par d'autres bancs d'essais (voir ci-dessus). Ces bancs d'essais se concentrent donc sur des requotes impliquant des identifiants d'objets, l'héritage, les jointures, les références de classes et d'objets, les attributs multivalués, l'"applatissement" des requotes, les méthodes d'objets et les types de données abstraits. Les schémas des bases de données de ces bancs d'essais sont également statiques.

Finalement, des ensembles de charges ont été proposés pour mesurer les performances de SGBDO clients-serveurs [CFLS91, FCL93]. Ces charges
opèrent sur des pages plutôt que sur des objets. La notion de région chaude ou froide (certaines "zones" de la base de données sont plus fréquemment accédées que d'autres) est également avancée afin de modéliser le comportement d'applications réelles. Cependant, la région chaude ne varie jamais. Le modèle de comportement n'est donc pas dynamique.

# 3 Banc d'essais OCB

OCB (*Object Clustering Benchmark*) est un banc d'essais générique et paramétrable destiné à évaluer les performances des SGBD orientés-objets [DS00]. Dans un premier temps spécialisé dans l'évaluation des stratégies de regroupement, il a été étendu par la suite pour devenir totalement générique. Sa flexibilité et son adaptabilité sont obtenues à l'aide d'un ensemble complet de paramètres. OCB est capable de simuler le fonctionnement des bancs d'essais orientés-objets qui constituent des standards de fait (OO1, HyperModel et OO7). De plus, le modèle générique d'OCB peut tre implémenté au sein d'un SGBD relationnel-objet et la plupart de ses opérations y demeurent pertinentes. Nous ne proposons ici qu'un survol d'OCB. Ses spécifications complètes sont disponibles dans [DS00]. Les deux composants principaux d'OCB sont sa base de données et ses opérations.

## 3.1 Base de données

Le schéma de la base de données d'OCB est constitué de *NC* classes dérivées d'une mme métaclasse (figure 1). Les classes sont définies par deux paramètres : *MAXNREF*, le nombre maximum de références à d'autres classes et *BASESIZE*, un incrément utilisé pour calculer la taille des instances (*InstanceSize*). Chaque référence de classe (*CRef*) possède un type *TRef*. Il existe *NTREF* différents types de références (héritage, aggrégation...). Finalement, un itérateur (*Iterator*) est maintenu au sein de chaque classe pour sauvegarder les références à toutes ses instances. Chaque objet possède *ATTRANGE* attributs entiers qui peuvent tre lus et mis à jour par les opérations. Une chane de caractères (*Filler*) de taille *InstanceSize* permet de simuler la taille réelle de l'objet. Après instantiation du schéma, un objet *O* de classe *C* pointe à travers les références *ORef* vers au plus *C.MAXNREF* objets. Il existe également une référence inverse (*BackRef*) qui lie chaque objet référencé à celui qui le référence. Les principaux paramètres qui définissent la base de données sont résumés dans le tableau 1.

## 3.2 Opérations

Les opérations d'OCB sont subdivisées en quatre catégories.

* *Accès aléatoire* : accès à *NRND* objets sélectionnés aléatoirement.

* *Balayage séquentiel* : sélection aléatoire d'une classe et accès à toutes ses instances. Une recherche par intervalle effectue en plus un test sur la valeur de *NTEST* attributs, pour chaque instance lue.
<figure><img src="image_2.png" /><figcaption>Figure 1: Schéma de la base de données d'OCB</figcaption></figure>

<table><caption>Table 1: Principaux paramètres de la base de données d'OCB</caption><thead><tr><td>Nom</td><td>Paramètre</td><td>Valeur par défaut</td></tr></thead><tbody><tr><td>NC</td><td>Nombre de classes dans la BD</td><td>50</td></tr><tr><td>MAXNREF(i)</td><td>Nombre maxi de références par classe</td><td>10</td></tr><tr><td>BASESIZE(i)</td><td>Taille de base des instances, par classe</td><td>50 octets</td></tr><tr><td>NO</td><td>Nombre total d'objets</td><td>20000</td></tr><tr><td>NREFT</td><td>Nombre de types de références</td><td>4</td></tr><tr><td>ATTRANGE</td><td>Nombre d'attributs d'un objet</td><td>1</td></tr><tr><td>CLOCREF</td><td>Localité de référence de classe</td><td>NC</td></tr><tr><td>OLOCREF</td><td>Localité de référence d'objet</td><td>NO</td></tr></tbody></table>

* *Parcours* : il existe deux types de parcours. Les *accès ensemblistes* (ou associatifs) effectuent un parcours en largeur d'abord. Les *accès navigationnels* sont subdivisés en *parcours simples* (en profondeur d'abord), en *parcours hiérarchiques* qui suivent toujours le même type de référence, et en *parcours stochastiques* qui sélectionnent le lien à déréférencer de manière aléatoire. Chaque parcours démarre d'un objet racine sélectionné aléatoirement et procède jusqu'à une profondeur prédéterminée. Tous les parcours peuvent être inversés pour suivre les liens *BackRef*.

* *Mise à jour* : il existe trois types de mises à jour. Les *évolutions de schéma* et les *évolutions de base de données* sont des insertions et des suppressions aléatoires de classes et d'objets, respectivement. Les *mises à jour d'attributs* sélectionnent aléatoirement *NUPDT* objets à mettre à jour ou bien sélectionnent aléatoirement une classe et
mettent à jour toutes ses instances (mise à jour séquentielle).

# 4 Spécification de DOEF

## 4.1 Contexte dynamique

Afin d'illustrer notre propos, nous commençons par donner un exemple de scénario que notre plate-forme peut simuler. Supposons que nous modélisons une librairie en ligne dans laquelle certains types de livres se vendent bien à des périodes données. Par exemple, les guides touristiques sur l'Australie ont pu tre populaires lors des Jeux Olympiques 2000. Mais une fois l'événement terminé, ces livres se sont soudainement ou graduellement moins bien vendus.

Une fois un livre sélectionné, des informations le concernant peuvent tre demandées, comme un résumé, une photo de la couverture, des extraits, des critiques, etc. Dans un SGBDO, cette information est stockée sous la forme d'objets référencés par l'objet (le livre) sélectionné. Accéder à ces informations revient donc à naviguer dans un graphe d'objets dont la racine est l'objet initialement sélectionné (ici, un livre). Après avoir consulté les informations concernant un livre, un utilisateur peut ensuite choisir un autre ouvrage du même auteur, qui devient alors la racine d'un nouveau graphe de navigation.

Nous décrivons ici les cinq principales étapes de notre démarche et les illustrons à l'aide de l'exemple que nous venons de présenter.

1. **Paramétrage des H-régions** : nous divisons tout d'abord la base de données en régions à probabilité d'accès homogène (appelées H-régions). Dans notre exemple, chaque H-région représente un ensemble de livres différent, chacun de ces ensembles possédant une probabilité d'accès propre.

2. **Spécification de la charge** : les H-régions permettent d'assigner des probabilités d'accès aux objets, mais pas de déterminer les actions à effectuer une fois un objet sélectionné. Nous appelons ces objets sélectionnés *racines de la charge* ou simplement *racines*. Dans cette étape, nous sélectionnons le type d'opération à effectuer sur une racine parmi ceux proposés dans OCB. Dans notre exemple, la charge est un parcours de graphe d'objets qui va de l'ouvrage sélectionné à l'information requise (par exemple, un extrait du livre).

3. **Spécification du protocole régional** : les protocoles régionaux exploitent les H-régions pour accomplir l'évolution de séquence d'accès. Différents modèles d'évolution de séquence d'accès peuvent tre obtenus en faisant varier le paramétrage des H-régions au cours du temps. Par exemple, un protocole régional peut tout d'abord affecter une grande probabilité d'accès à une H-région donnée, tandis que les autres H-régions ont une faible probabilité d'accès. Après un certain temps, une H-région différente hérite de la grande probabilité d'accès. Dans notre exemple de librairie en ligne, cela modélise la baisse d'intérêt pour les guides touristiques sur l'Australie après la fin des Jeux Olympiques.
4. **Spécification du protocole de dépendance** : les protocoles de dépendance nous permettent de spécifier une relation entre la racine courante et la racine suivante. Dans notre exemple, cela peut modéliser un client qui choisit de consulter un ouvrage écrit par le mme auteur que l'ouvrage qu'il a sélectionné précédemment.

5. **Intégration du protocole régional et du protocole de dépendance** : dans cette étape, nous intégrons les protocoles régionaux et de dépendance afin de modéliser des évolutions de dépendance entre des racines successives. Par exemple, un client de notre librairie en ligne peut sélectionner un livre qui l'intéresse, puis découvrir une liste d'ouvrages du mme auteur qui font partie des meilleures ventes actuelles. Le client sélectionne alors l'un des livres (protocole de dépendance). L'ensemble des livres du mme auteur, qui font partie des meilleures ventes actuelles, est lui susceptible de changer avec le temps (protocole régional).

## 4.2 H-régions

Les H-régions sont des sous-ensembles de la base de données de probabilité d'accès homogène. Les paramètres qui les définissent sont détaillés ci-dessous.

* `HR_SIZE` : taille de la H-région (fraction de la taille de la base).

* `INIT_PROB_W` : poids initial de la H-région. La probabilité d'accès est égale à ce poids divisé par la somme des poids de toutes les H-régions.

* `LOWEST_PROB_W` : poids minimum pour la H-région.

* `HIGHEST_PROB_W` : poids maximum pour la H-région.

* `PROB_W_INCR_SIZE` : incrément par lequel le poids est augmenté ou diminué lorsqu'une évolution survient.

* `OBJECT todayASSIGN_METHOD` : détermine la manière dont les objets sont assignés à une H-région. La sélection *aléatoire* permet de les choisir au hasard dans la base de données. La sélection *par classe* trie tout d'abord les objets selon leur identifiant de classe, avant de sélectionner les *N* premiers, *N* étant le nombre d'objets alloués à la H-région.

* `INIT_DIR` : direction initiale dans laquelle évolue l'incrément de poids (haut ou bas).

## 4.3 Protocoles régionaux

Les protocoles régionaux simulent les évolutions de séquence d'accès en initialisant tout d'abord les paramètres de toutes les H-régions. Ces paramètres sont ensuite modifiés périodiquement de manière prédéterminée. Cet article présente trois modèles d'évolution régionale.
### 4.3.1 Fentre mobile

Ce protocole régional simule des changements brusques dans la séquence d'accès. Dans notre exemple, cela correspond à un livre qui devient populaire tout d'un coup (suite à une promotion TV, par exemple). Une fois l'événement passé, l'ouvrage retrouve sa cote de popularité initiale très rapidement. Ce modèle d'évolution est obtenu en déplaçant une fentre dans la base de données. Les objets de la fentre présentent une probabilité d'être sélectionnés comme racine très supérieure à celle des autres objets de la base. Nous atteignons cet objectif en divisant la base de données en N H-régions de tailles égales. Une de ces H-régions est choisie pour tre la première région " chaude" (celle qui a la plus haute probabilité d'accès). Après un certain nombre de sélections de racine successives, une nouvelle H-région devient la région chaude.

* La base de données est divisée en N H-régions de tailles égales.

* Le paramètre *INIT_PROB_W* d'une H-région est fixé à *HIGHEST_PROB_W* (région chaude). La valeur de *INIT_PROB_W* pour les autres H-régions est fixée à *LOWEST_PROB_W*.

* Pour chaque H-région, *PROB_INCR_SIZE* est égal à *HIGHEST_PROB_W - LOWEST_PROB_W*. Toutes les H-régions doivent avoir les mêmes *LOWEST_PROB_W* et *PROB_W_INCR_SIZE*.

* Soit un paramètre *H* défini par l'utilisateur, qui reflète la vitesse d'évolution de séquence d'accès.

* Le paramètre *INIT_DIR* de toutes les H-régions est fixé vers le bas. La fentre est au départ placée dans la région chaude. Après 1 / *H* sélections de racines, la fentre se déplace d'une H-région à une autre. La région qu'elle quitte a son paramètre *INIT_DIR* réinitialisé vers le bas, tandis que celle sur laquelle elle arrive a son paramètre *INIT_DIR* réinitialisé vers le haut. Les poids des H-régions sont ensuite incrémentés ou décrémentés, selon la valeur de *INIT_DIR*.

### 4.3.2 Fentre mobile graduelle

Ce protocole est similaire au précédent, mais la région chaude " se réfroidit" graduellement et non brutalement. Les régions froides " se réchauffent" également graduellement au fur et à mesure que la fentre passe au-dessus. Cela permet de tester la faculté d'un système ou d'un algorithme à s'adapter à des types d'évolution plus doux. Dans notre exemple, ce modèle d'évolution peut décrire la baisse d'intérêt graduel pour les guides touristiques sur l'Australie après les Jeux Olympiques. Simultanément, les guides touristiques pour d'autres destinations peuvent rencontrer plus de succès.

Ce protocole est défini de la même manière que le précédent, à deux exceptions près. Premièrement, le paramètre *PROB_INCR_SIZE* est fixé par l'utilisateur et non plus calculé. Sa valeur détermine l'intensité avec laquelle la séquence d'accès change à chaque itération. Deuxièmement, l'évolution des probabilités d'accès à une H-région change. Lorsque la fentre arrive sur une H-région, la valeur de son paramètre *INIT_DIR* est inversée. Lorsque la fentre quitte une H-région, elle reste
en revanche inchangée. Cela permet à la H-région de continuer à se
" réchauffer" ou à se " refroidir" graduellement.

4.3.3 Cycles d'évolution

Ce modèle d'évolution décrit, par exemple, le comportement des clients d'une banque, qui tendraient à appartenir à une catégorie (comportementale, socio-professionnelle...) le matin et à une autre catégorie l'après-midi. Réitéré, ce processus crée un cycle d'évolution.

* La base de données est divisée en trois H-régions. Les deux premières représentent l'ensemble d'objets qui subit le cycle, la dernière la partie de la base qui demeure inchangée. Les valeurs du paramètre *HR_SIZE* des deux premières H-régions doivent tre égales et sont spécifiées par l'utilisateur. Celle de la troisième H-région correspond à la taille du reste de la base.

* Les valeurs de *LOWEST_PROB_W* et *HIGHEST_PROB_W* pour les deux premières H-régions sont fixées de manière à refléter les valeurs extrimes du cycle.

* La valeur de *PROB_INCR_SIZE* est égale à *HIGHEST_PROB_W* - *LOWEST_PROB_W* pour les deux premières H-régions, à zéro pour la dernière.

* La valeur de *INIT_PROB_W* est fixée à *HIGHEST_PROB_W* pour la première H-région et à *LOWEST_PROB_W* pour la deuxième.

* La valeur de *INIT_DIR* est dirigée vers le bas pour la région " chaude" et vers le haut pour la région " froide".

* Un paramètre *H* est de nouveau employé pour faire varier la vitesse d'évolution des séquences d'accès.

4.4 Protocoles de dépendance

Il existe de nombreux scénarios au cours desquels une personne exécute
une requete, puis décide d'en exécuter une autre en se basant sur les
résultats de la première, établissant ainsi une dépendance entre les deux
requotes. Nous avons spécifié dans cet article quatre protocoles de dépendance.

4.4.1 Sélection aléatoire

Cette méthode utilise simplement une fonction aléatoire pour sélectionner
la racine courante. Ce protocole modélise une personne qui lance une toute
nouvelle requete après avoir exécuté la précédente.

rᵢ = *RAND1()*, où rᵢ est l'identifiant du iᵉme objet racine. La fonction *RAND1()* ne suit pas nécessairement une loi uniforme.

4.4.2 Sélection par référence

La racine courante est choisie parmi les objets référencés par la racine
précédente. Dans notre exemple, ce scénario correspond à une personne
qui termine la consultation d'un livre, puis recherche l'ouvrage suivant
dans la mme série ou collection.

$r_{i+1} = \text{RAND2}(\text{RefSet}(r_i, D))$, où $\text{RefSet}(r_i, D)$ est une fonction qui retourne l'ensemble des objets référencés par la $i^{\text{eme}}$ racine. Nous avons utilisé deux types de références. Les références structurelles (S-références) sont simplement celles qui sont issues du graphe d'objets. Nous avons de plus introduit les D-références dans le seul but d'établir des dépendances entre les racines de parcours. Le paramètre $D$ est utilisé pour spécifier le nombre de D-références par objet.

### 4.4.3 Sélection par objets parcourus

La racine courante est sélectionnée dans l'ensemble d'objets retournés par la requte précédente. Par exemple, un client demande une liste de livres avec leurs auteurs et leurs éditeurs, puis décide ensuite de lire un extrait de l'un des ouvrages.

$r_{i+1} = \text{RAND3}(\text{TraversedSet}(r_i, C))$, où $\text{TraversedSet}(r_i, C)$ retourne l'ensemble des objets référencés pendant le parcours effectué à partir de la $i^{\text{eme}}$ racine. Le paramètre $C$ sert à limiter le nombre d'objets retournés par $\text{TraversedSet}(r_i, C)$. C'est une fraction de la cardinalité de l'ensemble des objets retournés. Ainsi, le degré de localité des objets renvoyés par $\text{TraversedSet}(r_i, C)$ peut tre contrôlé (plus $C$ est petit, plus le degré de localité est grand).

### 4.4.4 Sélection par classe

La racine courante doit appartenir à la mme classe que la racine précédente. De plus, la sélection de la racine est réduite à un sous-ensemble des objets de cette classe qui dépend de la racine précédente. Par exemple, un client de notre librairie en ligne choisit un livre du mme auteur que l'ouvrage qu'il vient de consulter. Dans ce cas, la fonction de sélection par classe retourne les livres écrits par le mme auteur.

$r_{i+1} = \text{RAND4}(f(r_i, \text{Class}(r_i), U))$, où $\text{Class}(r_i)$ retourne la classe de la $i^{\text{eme}}$ racine. Le paramètre $U$ est défini par l'utilisateur et indique la cardinalité de l'ensemble d'objets retourné par la fonction $f()$. C'est en fait une fraction de la cardinalité totale de la classe. Il peut tre utilisé pour faire varier le degré de localité entre les objets retournés par $f()$. $f()$ doit tre injective.

### 4.4.5 Sélection hybride

Ce type de sélection permet d'utiliser une combinaison des protocles de dépendance décrits ci-dessus. Cette possibilité est importante, car elle peut simuler par exemple un utilisateur qui initie une requte totalement nouvelle après avoir suivi des dépendances. La sélection hybride est implémentée en deux phases. La première *phase aléatoire* utilise la sélection aléatoire pour sélectionner une première racine. Dans la seconde *phase de dépendance*, un des protocoles de dépendance ci-dessus est appliqué pour sélectionner la racine suivante. La seconde phase est répétée $R$ fois avant
que la première ne survienne à nouveau. Les deux phases sont réitérées de manière continue.

La probabilité de sélectionner un protocole de dépendance donné dans la *phase de dépendance* est spécifiée à l'aide des paramètres suivants : *RANDOM_DEP_PROB* (sélection aléatoire), *SREF_DEP_PROB* (sélection par référence sur les S-références), *DREF_DEP_PROB* (sélection par référence sur les D-références), *TRAVERSED_DEP_PROB* (sélection par objets parcourus) et *CLASS_DEP_PROB* (sélection par classe).

## 4.5 Intégration des protocoles régionaux et de dépendance

Les protocoles de dépendance modélisent le comportement des utilisateurs.

Comme ce dernier peut changer au cours du temps, ces protocoles doivent également tre capables d'évoluer. En intégrant les protocoles régionaux et de dépendance, nous parvenons à simuler des évolutions de dépendance entre des sélections successives de racines. Ceci est facilement accompli en exploitant la propriété des protocoles de dépendance de retourner un ensemble d'objets racines candidats en fonction d'une racine précédente donnée. Jusqu'à présent, la racine courante était sélectionnée dans cet ensemble à l'aide d'une fonction aléatoire. Au lieu de procéder ainsi, nous avons partitionné l'ensemble de racines candidates en H-régions et appliqué les protocoles régionaux à ces H-régions. Lorsque le protocole de dépendance " sélection par objets parcourus" est utilisé, la propriété suivante doit tre vérifiée : pour un mme objet racine, le mme ensemble d'objets doit tre parcouru. Ainsi, une racine donnée donne toujours lieu au mme parcours.

# 5 Résultats expérimentaux

## 5.1 Regroupement dynamique

Dans cette série de tests, nous avons utilisé DOEF pour comparer les performances de quatre algorithmes dynamiques de regroupement d'objets parmi les plus récents : DSTC [BS96], DRO [DFR<sup>+</sup>00], OPCF-PRP et OPCF-GP [HMB00]. L'objectif du regroupement est de placer automatiquement les objets qui sont susceptibles d'être utilisés au mme moment dans une mme page disque, afin de minimiser les entrées/sorties.

DSTC, qui est basé sur la collecte de statistiques d'utilisation au volume contrôlé, entrane néanmoins une surcharge de regroupement élevée. DRO se base en partie sur DSTC, mais utilise une plus petite quantité de statistiques et génère une surcharge beaucoup plus faible. Finalement, OPCF est une plate-forme qui permet de transformer des algorithmes de regroupement statiques en algorithmes dynamiques. Elle a été appliquée sur des stratégies de partitionnement de graphe (GP) et de hiérarchisation de probabilités (PRP).

Le paramétrage de ces techniques de regroupement est indiqué dans le tableau 2. Il permet, dans chaque cas, d'aboutir au meilleur résultat
avec l'algorithm concerné. Par manque de place, ces paramètres ne sont pas décrits ici, mais ils sont complètement documentés dans les articles qui présentent les travaux correspondants.

<table><caption>(a) DSTC</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>n</td><td>200</td></tr><tr><td>n<sub>p</sub></td><td>1</td></tr><tr><td>p</td><td>1000</td></tr><tr><td>T<sub>fa</sub></td><td>1,0</td></tr><tr><td>T<sub>fe</sub></td><td>1,0</td></tr><tr><td>T<sub>fc</sub></td><td>1,0</td></tr><tr><td>w</td><td>0,3</td></tr></tbody></table>

<table><caption>(b) DRO</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>MinUR</td><td>0.001</td></tr><tr><td>MinLT</td><td>2</td></tr><tr><td>PCRate</td><td>0,02</td></tr><tr><td>MaxD</td><td>1</td></tr><tr><td>MaxDR</td><td>0,2</td></tr><tr><td>MaxRR</td><td>0,95</td></tr><tr><td>SUInd</td><td>true</td></tr></tbody></table>

<table><caption>(c) OPCF</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>N</td><td>200</td></tr><tr><td>CBT</td><td>0,1</td></tr><tr><td>NPA</td><td>50</td></tr><tr><td>NRI</td><td>25</td></tr></tbody></table>

<caption>Table 2: Paramétrage des algorithmes de regroupement dynamiques</caption>

Nous avons mené nos expérimentations à l'aide de la plate-forme de simulation à événements discrets VOODB [DS99], qui permet d'évaluer les performances des SGBDO en général et des méthodes d'optimisation comme le regroupement en particulier. Nous avons fait ce choix de la simulation pour deux raisons. Premièrement, cela nous a permis de développer et de tester rapidement plusieurs algorithmes de regroupement dynamiques, alors que les études menées jusqu'ici en comparaient deux au plus. Deuxièmement, il est relativement aisé de simuler de manière précise des entrées/sorties, qui sont la mesure d'efficacité principale des algorithmes de regroupement. Le paramétrage de VOODB pour ces expérimentations est indiqué dans le tableau 3 (a).

Puisque DOEF utilise la base d'objets d'OCB et ses opérations, il est également important d'indiquer le paramétrage d'OCB pour ces tests (tableau 3 (b)). La taille des objets varie de 50 à 1600 octets, pour une moyenne de 233 octets. Nous avons utilisé une base de 100 000 objets, soit une taille de 23,3 Mo. Bien que ce soit une petite base, nous avons également utilisé un petit cache mémoire (4 Mo) afin que le rapport taille de la base sur taille du cache demeure important. Les performances des algorithmes de regroupement sont en effet plus sensibles à ce rapport qu'à la taille de la base seule. Nous avons par ailleurs utilisé une seule opération d'OCB : le parcours simple (de pronfondeur 2), car c'est la seule qui permet de toujours accéder au même ensemble d'objets à partir d'une racine donnée. Cela établit un lien direct entre des variations de sélection des racines et des évolutions de séquence d'accès. Lors de chaque test,
nous avons exécuté 10 000 transactions.

Finalement, les principaux paramètres de DOEF sont présentés dans le tableau 3 (c). La valeur de `HR_SIZE` permet de créer une région chaude qui représente 3 % de la base. Les valeurs de `HIGHEST_PROB_W` et de `LOWEST_PROB_W` permettent d'affecter une probabilité d'accès de 80 % à la région chaude et de 20 % aux régions froides, globalement. Nous avons paramétré DOEF ainsi afin de refléter le comportement typique d'une application [GP87, CFLS91, FCL93].

<table><caption>(a) VOODB</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>Système</td><td>Centralisé</td></tr><tr><td>Taille page</td><td>4 Ko</td></tr><tr><td>Taille cache</td><td>4 Mo</td></tr><tr><td>Gestion cache</td><td>LRU</td></tr><tr><td>Préchargement</td><td>—</td></tr><tr><td>Nb serveurs</td><td>1</td></tr><tr><td>Nb utilisateurs</td><td>1</td></tr><tr><td>Placement initial</td><td>Séquentiel</td></tr></tbody></table>

<table><caption>(b) OCB</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>Nb classes</td><td>50</td></tr><tr><td>Nb références</td><td>10</td></tr><tr><td>Taille objets</td><td>50</td></tr><tr><td>Nb objets</td><td>100 000</td></tr><tr><td>Nb types références</td><td>4</td></tr><tr><td>Dist. types réf.</td><td>Uniforme</td></tr><tr><td>Dist. réf. classes</td><td>Uniforme</td></tr><tr><td>Dist. objets ds classes</td><td>Uniforme</td></tr><tr><td>Dist. réf. objets</td><td>Uniforme</td></tr></tbody></table>

<table><caption>(c) DOEF</caption><thead><tr><td>Paramètre</td><td>Valeur</td></tr></thead><tbody><tr><td>HR_SIZE</td><td>0,003</td></tr><tr><td>HIGHEST_PROB_W</td><td>0,80</td></tr><tr><td>LOWEST_PROB_W</td><td>0,0006</td></tr><tr><td>PROB_W_INCR_SIZE</td><td>0,02</td></tr><tr><td>OBJECT today METHOD</td><td>Aléatoire</td></tr></tbody></table>

<caption>Table 3: Paramétrage de l'environnement de test</caption>

Pour cette série de tests, nous nous concentrons sur la faculté des algorithmes de regroupement à s'adapter à des évolutions de séquence d'accès, et non sur leur performance pure. Tous les résultats présentés ici sont exprimés en termes de nombre d'entrées/sorties total, c'est-à-dire de somme des entrées/sorties nécessaires à l'exécution des transactions et du regroupement (surcharge). Dans les figures qui suivent, l'étiquette **NC** indique une expérience étalon sans regroupement d'objets.

### 5.1.1 Application de protocoles régionaux

Dans cette série de tests, nous avons utilisé les protocoles régionaux *fentre mobile* et *fentre mobile graduelle* pour évaluer la capacité des algorithmes de regroupement à s'adapter à des évolutions de séquence d'accès. Pour cela, nous avons fait varier le paramètre *H* (vitesse de changement des séquences d'accès).
Les résultats que nous avons obtenus sont représentés dans la figure 2. Nous pouvons en tirer trois conclusions. Premièrement, quand la vitesse de changement des séquences d'accès est faible ($H < 0,0006$), tous les algorithmes ont des performances similaires en termes de tendance. Cela signifie qu'ils réagissent tous de manière analogue lorsque les séquences d'accès évoluent lentement. Deuxièmement, quand la vitesse d'évolution est plus élevée (figure 2 (a)), leurs performances deviennent rapidement plus mauvaises que si aucun regroupement n'était effectué (en raison de la surcharge qu'ils engendrent). Troisièmement, quand la vitesse de changement des séquences d'accès est élevée ($H > 0,0006$), les algorithmes DRO, GP et PRP se montrent plus robustes que DSTC. Cela est d au fait que ces techniques ne réorganisent qu'un nombre limité de pages disque (celles qui sont mal regroupées). Nous appelons cette propriété " regroupement prudent et flexible". Par contraste, DSTC peut déplacer une page disque même quand le gain potentiel est faible. Ainsi, quand les séquences d'accès changent rapidement, DSTC engendre une surcharge importante pour un bénéfice faible, ce qui explique ses moins bonnes performances.

<figure><img src="image_3.png" /><figcaption>Figure 2: Résultat de l'application de protocoles régionaux</figcaption></figure>

### 5.1.2 Intégration de protocoles régionaux et de dépendance

Dans cette expérience, nous avons exploré les effets d'une évolution de séquence d'accès sur le protocole de dépendance sélection par S-référence en l'intégrant avec les protocoles régionaux *fentre mobile* et *fentre mobile graduelle*. La valeur du paramètre *R* de cette sélection hybride a été fixée à 1.

Les résultats que nous avons obtenus sont représentés dans la figure 3. Lorsque le protocole *fentre mobile* est appliqué (figure 3 (a)), DRO, GP et PRP se montrent à nouveau plus robustes que DSTC. Cependant, contrairement à ce qui se produisait dans l'expérience précédente, leurs performances ne deviennent jamais pires que lorsque qu'aucun regroupement n'est effectué, mme quand la séquence d'accès change à chaque transaction ($H = 1$). Cela s'explique par le fait que la sélection par S-référence induit des évolutions de séquence d'accès moins
brutales que le protocole *fentre mobile* seul. Dans le cas du protocole *fentre mobile graduelle* (figure 3 (b)), l'écart de performance entre DSTC et les autres algorithmes demeure le même lorsque la vitesse de changement des séquences d'accès augmente. Cela indique que DSTC est suffisamment robuste pour absorber ce type d'évolution très lente (la seule propriété qui change est le refroidissement et le réchauffement lent des S-références).

<figure><img src="image_4.png" /><figcaption>Figure 3: Résultat de l’intégration de protocoles régionaux et du protocole de dépendance par S-référence</figcaption></figure>

## 5.2 Gestionnaires d'objets persistants

Dans cette série d'expériences, nous avons utilisé DOEF pour comparer les performances de deux gestionnaires d'objets persistants existants : SHORE [CDF+94] et Platypus [HBKZ00].

SHORE a été conçu pour répondre de façon efficace aux besoins de nombreux types d'applications, y compris les langages de programmation orientés-objets. Il s'appuie sur un modèle distribué de type pair à pair et a été spécifiquement conçu pour être performant. L'architecture en couches de SHORE permet aux utilisateurs de sélectionner le niveau de service souhaité pour une application particulière. La couche la plus basse, le SSM (SHORE Storage Manager), fournit les primitives de base pour accéder aux objets persistants. La politique de gestion de cache de SHORE est CLOCK. Nous avons utilisé la version 2.0 de SHORE dans tous nos tests.

Platypus est également un gestionnaire d'objets persistants conçu pour offrir les meilleurs temps d'accès possibles. Il peut fonctionner selon trois modèles distribués : centralisé, client-serveur ou client-pair et comprend différents services typiques des SGBDO tels que la journalisation, la reprise sur panne, un ramasse-miettes et la possibilité d'intégrer des algorithmes de regroupement. La politique de gestion de cache de Platypus est LRU.

Dans ces expériences, nous avons voulu tester les éléments " de base" entrant en compte dans les performances de SHORE et Platypus. Aussi n'avons-nous pas intégré de stratégie de regroupement dans ces deux systèmes. Nos tests ont été effectués sur une station de travail Solaris 7
dotée de deux processeurs Celeron à 433 MHz, de 512 Mo de mémoire vive et d'un disque dur de 4 Go. A partir du SSM de SHORE, nous avons construit une interface PSI [Bla98] baptisée PSI-SSM qui nous a permis d'utiliser le mme code de DOEF pour SHORE et Platypus. Le paramétrage de DOEF et OCB est le mme que dans nos expériences sur le regroupement (tableau 3), à l'exception de la taille de la base qui compte 400 000 objets dont la taille varie entre 50 et 1200 octets – soit une taille moyenne de 269 octets et une taille totale de la base de 108 Mo. La taille du cache de SHORE et Platypus a été fixée à 61 Mo.

Nous avons appliqué le protocole *fentre mobile* pour comparer les ef-
fets d'évolutions de séquence d'accès sur les performances de Platypus
et SHORE. Les résultats que nous avons obtenus (figure 4) montrent
que Platypus présente de meilleures performances que SHORE lorsque
la vitesse d'évolution des séquences d'accès (paramètre *H*) est faible,
mais que l'écart se réduit nettement lorsque cette vitesse augmente. Cela
s'explique par l'évolution de la localité d'accès. Lorsque la vitesse de
changement des séquences d'accès est basse, la localité d'accès est élevée
(la région chaude est petite et se déplace lentement). Les objets les plus
demandés se trouvent donc en général dans le cache. En revanche, quand
les séquences d'accès changent plus rapidement, la localité d'accès diminue
et les accès disques deviennent les plus fréquents. Nous attribuons ce
phénomène à une déficience de Platypus en termes de pagination disque,
en raison de la granularité de verrouillage trop élevée entre son serveur de
pages et les processus clients, qui entrane un faible degré de concurrence.

<figure><img src="image_5.png" /><figcaption>Figure 4: Résultat de l'application du protocole fentre mobile</figcaption></figure>

6 Conclusion et perspectives

Nous avons présenté dans cet article les spécifications d'une nouvelle plate-
forme d'évaluation des performances, DOEF, qui permet aux concepteurs
et aux utilisateurs de SGBDO de tester un système donné à l'aide d'une
charge dite dynamique. C'est là l'originalité de notre proposition, car
si la plupart des applications réelles présentent des évolutions dans leurs
séquences d'accès aux données, les bancs d'essais actuels ne modélisent pas ce type de comportement.

Nous avons conçu DOEF comme une plate-forme ouverte et extensiblable, selon deux axes. Premièrement, comme c'est à notre connaissance la première tentative d'étudier le comportement dynamique des SGBDO, nous avons pris grand soin de garantir l'intégration facile de nouveaux modèles d'évolution de séquence d'accès, principalement grâce à la définition des H-régions. Nous encourageons les chercheurs à utiliser et à enrichir cette plate-forme pour tester leurs propres idées. Le code utilisé dans nos expériences de simulation et nos implémentations sur Platypus et SHORE est par ailleurs librement disponible en ligne<fnref n="2" />.

Deuxièmement, bien que nous ayons employé un environnement purement orienté-objets dans cette première étude, nous pourrions appliquer les concepts développés dans cet article aux bases de données relationnelles-objets. En effet, puisqu'OCB peut tre assez aisément adapté au modèle relationnel-objet (bien que des extensions soient clairement nécessaires, comme les types de données abstraits et les tables embotées, par exemple), DOEF, qui est une surcouche d'OCB, peut également tre utilisé dans un contexte relationnel-objet.

L'objectif principal de DOEF est de permettre aux chercheurs et aux ingénieurs d'observer les performances des SGBDO (identifier les composants qui forment des goulots d'étranglement, par exemple) lorsque les séquences d'accès aux données varient. Les résultats de nos expérimentations sur les algorithmes de regroupement dynamiques et les gestionnaires d'objets persistants ont démontré que DOEF permettait d'atteindre cet objectif. Dans le cas des algorithmes de regroupement, nous avons mis deux choses en évidence. Ces techniques peuvent s'adapter à des évolutions lentes des séquences d'accès, mais leurs performances s'effondrent lorsque les changements sont rapides. De plus, un regroupement dit prudent et flexible est indispensable pour prendre en compte de telles évolutions. En ce qui concerne Platypus et SHORE, l'utilisation de DOEF a permis de mettre en évidence les problèmes de pagination disque de Platypus.

Ce travail de recherche ouvre plusieurs perspectives. La première concerne évidemment l'exploitation de DOEF, de manière à continuer d'accumuler de l'expertise et des connaissances sur le comportement dynamique des SGBDO. De plus, comparer le comportement dynamique de différents systèmes, qui constitue déjà une tâche intéressante en soi, pourrait nous permettre d'identifier de nouveaux modèles d'évolution de séquence d'accès à inclure dans DOEF, puisque nous n'avons certainement pas pris en compte tous les cas possibles. Améliorer ou affiner la définition des H-régions pour prendre en compte la structure du graphe d'objets pourrait également enrichir DOEF.

Par ailleurs, l'adaptation de DOEF au modèle relationnel-objet se révèle indispensable pour pouvoir tester et comparer les performances de ces systèmes et tenter d'identifier leurs goulots d'étranglement. Puisque le schéma d'OCB peut tre implémenté directement dans un système relationnel-objet, cela reviendrait à adapter les opérations d'OCB et à en ajouter de

<footnote n="2">²http://eric.univ-lyon2.fr/~jdarmont/download/docb-voodb.tar.gz
http://eric.univ-lyon2.fr/~jdarmont/download/docb-platypus-shore.tar.gz</footnote>
nouvelles, spécifiques ou pertinentes dans ce contexte.

Finalement, la capacité de DOEF à évaluer d'autres aspects des performances des SGBDO pourrait tre explorée. Le regroupement est en effet une technique efficace, mais d'autres stratégies comme la gestion de cache et le préchargement, ainsi que leur utilisation conjointe, pourraient également faire l'objet d'une étude.

## Remerciements

Les auteurs remercient Stephen M. Blackburn pour ses suggestions et commentaires pertinents lors de nos expérimentations et de la rédaction de cet article.

## References

[ABM$^{+90}$] T. Anderson, A. Berre, M. Mallison, H. Porter, and B. Scheider. The HyperModel benchmark. In *International Conference on Extending Database Technology (EDBT 90)*, volume 416 of LNCS, pages 317–331, March 1990.

[Bla98] S. M. Blackburn. *Persistent Store Interface: A foundation for scalable persistent system design*. PhD thesis, Australian National University, Canberra, Australia, August 1998.

[BS96] F. Bullat and M. Schneider. Dynamic clustering in object databases exploiting effective use of relationships between objects. In *10th European Conference on Object-Oriented Programming (ECOOP 96)*, volume 1098 of LNCS, pages 344–365, July 1996.

[Cat91] R. Cattell. An engineering database benchmark. In J. Gray, editor, *The Benchmark Handbook for Database Transaction Processing Systems*, pages 247–281. Morgan Kaufmann, 1991.

[CDF$^{+94}$] M. J. Carey, D. J. DeWitt, M. J. Franklin, N. E. Hall, M. McAuliffe, J. F. Naughton, D. T. Schuh, M. H. Solomon, C. K. Tan, O. Tsatalos, S. White, and M. J. Zwilling. Shoring up persistent applications. In *1994 ACM SIGMOD International Conference on Management of Data*, pages 383–394, May 1994.

[CDN93] M. Carey, D. DeWitt, and J. Naughton. The OO7 benchmark. In *1993 ACM SIGMOD International Conference on Management of Data*, pages 12–21, May 1993.

[CDN$^{+97}$] M. Carey, D. DeWitt, J. Naughton, M. Asgarian, P. Brown, J. Gehrke, and D. Shah. The BUCKY object-relational benchmark. In *1997 ACM SIGMOD International Conference on Management of Data*, pages 135–146, May 1997.

[CFLS91] M. J. Carey, M. J. Franklin, M. Livny, and E. J. Shekita. Data caching tradeoffs in client-server DBMS architectures. In *1991 ACM SIGMOD International Conference on Management of Data*, pages 357–366, May 1991.
[DFR+00] J. Darmont, C. Fromantin, S. Regnier, L. Gruenwald, and M. Schneider. Dynamic clustering in object-oriented databases: An advocacy for simplicity. In *ECOOP 2000 Symposium on Objects and Databases*, volume 1944 of LNCS, pages 71–85, June 2000.

[DS99] J. Darmont and M. Schneider. VOODB: a generic discrete-event random simulation model to evaluate the performances of OODBs. In *25th International Conference on Very Large Databases (VLDB 99)*, pages 254–265, September 1999.

[DS00] J. Darmont and M. Schneider. Benchmarking OODBs with a generic tool. *Journal of Database Management*, 11(3):16–27, Jul-Sept 2000.

[FCL93] M. J. Franklin, M. J. Carey, and M. Livny. Local disk caching for client-server database systems. In *19th International Conference on Very Large Data Bases (VLDB 93)*, pages 641–655, August 1993.

[GKM96] C. Gerlhof, A. Kemper, and G. Moerkotte. On the cost of monitoring and reorganization of object bases for clustering. *SIGMOD Record*, 25(1):22–27, 1996.

[GP87] J. Gray and G. R. Putzolu. The 5 minute rule for trading memory for disk accesses and the 10 byte rule for trading memory for CPU time. In *ACM Special Interest Group on Management of Data 1987 Annual Conference*, pages 395–398, May 1987.

[HBKZ00] Z. He, S. M. Blackburn, L. Kirby, and J. Zigman. Platypus: The design and implementation of a flexible high performance object store. In *9th International Workshop on Persistent Object Systems (POS9)*, pages 100–124, September 2000.

[HMB00] Z. He, A. Marquez, and S. Blackburn. Opportunistic prioritised clustering framework (OPCF). In *ECOOP 2000 Symposium on Objects and Databases*, volume 1944 of LNCS, pages 86–100, June 2000.

[LKK00] S. Lee, S. Kim, and W. Kim. The BORD benchmark for object-relational databases. In *11th International Conference on Database and Expert Systems Applications (DEXA 00)*, volume 1873 of LNCS, pages 6–20, September 2000.

[Sch94] H. Schreiber. JUSTITIA: a generic benchmark for the OODBMS selection. In *4th International Conference on Data and Knowledge Systems in Manufacturing and Engineering*, pages 324–331, May 1994.

[TNL95] A. Tiwary, V. Narasayya, and H. Levy. Evaluation of OO7 as a system and an application benchmark. In *OOPSLA 95 Workshop on Object Database Behavior, Benchmarks and Performance*, October 1995.

[TPC02] TPC. Transaction processing performance council homepage. http://www.tpc.org, 2002.