Knowledge Base Management Systems are not designed to manage large amounts of data in an efficient manner, contrary to DBMS of which it is the primary purpose. We present an approach that unifies KBMS and DBMS, by providing an efficient management of wide volumes of (shared) data and reasoning capabilities (instance classification). We propose a conceptual structuring of the object space that relies on logical properties used in the definition of classes, namely the Classification Space, which supports instance classification, integrity checking and object indexing through an appropriate physical representation. This representation also supports semantic query optimization and integration of heterogeneous data.
Les fonctions classiques d’un SGBD (Système de Gestion de Bases de Données)
restent d’actualité, même si l’avènement des entrepôts de données a initié un nouveau
paradigme, les bases de données OLAP (On-Line Analytical Processing), où l’accès
rapide à de grandes masses de données devient un enjeu majeur. C’est dans la
perspective des bases de données classiques (OLTP) qu’a été conçu le modèle de
données dont il est question ici. Sa conception a été guidée par le souci de permettre
le partage des données par diverses catégories d’utilisateurs, chacune les percevant
selon ses points de vue. Les vues des bases de données relationnelles ont en quelque
sorte « élargi » l’intention initiale des auteurs du modèle relationnel, pour qui les vues
étaient une « fenêtre » sur les données [
Le terme « base de connaissances », qui à l’origine, dans la décennie 70, désignait
l’ensemble des règles d’un système expert (à base de règles), est aujourd’hui utilisé
pour désigner une large gamme de représentations informatiques dont le seul
dénominateur commun est de faire appel à du raisonnement logique. Ce même terme,
dans la communauté française de l’IA des années 80, désignait principalement un
système de type « frames » [
Les communautés des bases de données et des bases de connaissances sont
demeurées relativement séparées. Il y a bien eu quelques tentatives d’utilisation des
systèmes à base de connaissances pour effectuer certains travaux sur les données des
bases de données, par exemple pour le data mining ou l’intégration de données, mais
les deux systèmes restaient distincts et il était nécessaire de convertir les données
d’une représentation à l’autre, ce qui les limitait au rôle de prototype de recherche
[
Or, il nous semble que le traitement des très grandes quantités de données et de connaissances disponibles dans des entreprises ou sur le web, nécessite des systèmes mixtes de type SGBD-BC, c'est-à-dire des systèmes intégrant les fonctionnalités des SGBD – notamment sa capacité de stockage de très grandes masses de données, de gestion de confidentialité et de cohérence –, ainsi que les fonctionnalités des SGBC, notamment le classement et d’autres formes de raisonnement. Le système Osiris est un SGBD-BC qui implémente le modèle des P-types.
Le modèle des P-types (P signifie Partagé) a été conçu avec une vision très orientée vers l’expression directe des besoins des utilisateurs, à travers un usage intensif des vues, qui représentent le point de vue d’un groupe homogène d’utilisateurs. Dans cette perspective, les « vues » constituent la définition même d’un P-type, et c’est le système – et non pas l’analyste comme dans l’approche classique de conception – qui détermine les tables appropriées2 pour la gestion des données. Ainsi, un P-type est défini par la collection des points de vue qu’ont les utilisateurs sur les objets de ce type (cf §2). Les vues sont définies dans une hiérarchie de spécialisation 1 Les termes classement et classification existaient déjà en analyse des données. Dans le domaine des bases de connaissances, la classification de concepts (ou de classes) désigne le calcul de la subsomption entre concepts, sur la base de leurs définitions respectives en termes de logique. D’un point de vue ensembliste, la subsomption est le calcul de la relation d’inclusion entre concepts. 2 Dans l’optique d’une implantation relationnelle. stricte3, par ses vues parentes (sauf la vue racine, appelée vue minimale) et ses attributs et contraintes propres. Un P-type représente un ensemble homogène d’objets du monde réel, par exemple des personnes, des véhicules, des maladies. De tels ensembles sont par nature disjoints et un objet appartient à un P-type et un seul.
L’identification des vues d’un objet devant être permanente, aussi bien à la création de l’objet que lors de toute modification, une attention particulière a été portée à cette opération, qui est fortement optimisée, en particulier lors des mises à jour des objets. Le classement d’objet et la représentation des vues reposent sur une structuration de l’espace des objets qui est dérivée des propriétés logiques qui définissent les vues. L’espace des objets d’un P-type est ainsi partitionné en classes d’équivalence, appelées Eq-classes, qui regroupent des objets ayant le même comportement vis-à-vis de l’ensemble des vues de ce P-type : tous les objets de la même Eq-classe satisfont exactement le même ensemble de vues du P-type. Dès lors, l’unité de représentation et de raisonnement n’est plus l’objet élémentaire mais l’Eqclasse, qui à un instant donné représente l’ensemble des objets équivalents vis-à-vis du classement dans les vues. L’espace des objets structuré en Eq-classes est appelé l’Espace de Classement du P-type.
Nous présentons d’abord le modèle des P-types et le système Osiris, qui est le prototype qui implante le modèle. Dans cette partie nous introduisons également l’Espace de Classement, qui constitue la structuration conceptuelle de l’espace des objets. Nous présentons ensuite la représentation physique de l’Espace de classement et son usage pour l’indexation des objets. Nous montrons comment cette structuration de l’Espace de Classement peut servir de support à l’optimisation sémantique des requêtes et nous évoquons en conclusion le support à l’intégration de données que constitue cet espace. 2
Le système Osiris implante le modèle des P-types, qui a été initialement conçu dans
l’optique d’un SGBD-BC privilégiant le partage d’information à travers les vues et
assurant la vérification automatique de contraintes d’intégrité élaborées et le
classement d’objets [
P-types. L’ensemble des objets du domaine est organisé en sous-espaces disjoints, où
chaque sous-espace, nommé P-type, représente les objets d’une même « famille ».
Lors de la conception d’un Système d’Information, le choix des P-types est le premier
3 Le modèle des P-types a été défini dans le paradigme des Types Abstraits Algébriques, qui a
également été utilisé pour modéliser la notion d’objet dans les langages à objets. Il s’ensuit
une certaine similarité entre une hiérarchie de spécialisation et une hiérarchie d’héritage.
Toutefois, la première est strictement ensembliste alors que la seconde ne l’est
qu’accidentellement, car son objectif est la réutilisation du code [
Vues. Un P-type est défini par une hiérarchie de vues dont la racine, appelée vue minimale, contient tous les objets du P-type. Une vue est définie par les vues qu’elle spécialise (sauf la vue minimale) et par ses attributs et contraintes propres. Attributs. Un attribut a un nom (unique dans le P-type) et un type. Le type peut être prédéfini (INTEGER, REAL, BOOLEAN, CHARACTER, STRING), un P-TYPE (i.e., une référence à un P-type), ou une collection (set, list) de types prédéfinis ou de P-TYPEs. Bien que les attributs puissent être définis dans n’importe quelle vue (et même dans plusieurs vues), dans cet article nous considèrerons pour simplifier que les attributs d’un P-type sont définis dans la vue minimale. Un attribut qui intervient dans au moins une contrainte est appelé un attribut classificateur.
Contraintes. Les contraintes définissant les vues sont des clauses de Horn dont les
littéraux sont des prédicats élémentaires de domaine, de la forme Attr ∈ Domaine, où
le domaine peut être un intervalle, (e.g., [
Considérons un P-Type PERSON, avec quelques vues qui illustrent les définitions cidessus.
view PERSON attr name: STRING; id: INT; age: INT in [0..120]; sex: CHAR in {m, f}; salary : INT ≥ 0; owns: setof CAR; … (a1) age < 18 Î end PERSON; view MINOR: PERSON
age < 18 end MINOR; view ADULT: PERSON age ≥ 18 salary ≥ 600 end ADULT; salary < 1200
-- Dépendance Inter-Attributs -- Vue minimale du P-type PERSON -- Contrainte de domaine : Age ∈ [0..120] -- Contrainte de domaine :Sex ∈ {m, f} -- Contrainte de domaine : salary ∈ [0..SUP] -- Le P-type CAR est défini par ailleurs -- Spécialise la vue (minimale) PERSON -- Contrainte de domaine: age ∈ [0..18[ -- Spécialise la vue (minimale) PERSON -- Contrainte de domaine: age ∈ [18..120] 4 les Simple Predicates sont des prédicats de la forme Attr R Valeur, où R ∈ {=, <, ≤, >, ≥, ≠ } view SENIOR: ADULT age ≥ 65 end SENIOR; view MALE: PERSON
sex = m end MALE; view EMPLOYEE: ADULT
salary ≥ 1200,00 end EMPLOYEE; -- Spécialise la vue ADULT -- Spécialise la vue PERSON -- Contrainte de domaine: sex ∈ {m}
-- Specialise la vue ADULT view CEO: EMPLOYEE -- Spécialise la vue EMPLOYEE attr manages : COMPANY ; -- attribut propre à la vue CEO
salary > 3000,00; end CEO; La forme la plus générale des contraintes (ou assertions) est celle des clauses de Horn (cf assertion (a1)). Nous en donnons un autre exemple ci-dessous, qui pourrait être associé à la définition de la vue minimale PERSON.
(a2) sex=m Î nbGrossesses = undefined
L’assertion (a2) est une contrainte d’intégrité qui exprime que le nombre de grossesses pour un individu masculin est indéfini. Osiris distingue les valeurs indéfini et inconnu, qui sont regroupées dans les bases de données classiques sous l’appellation null. Indéfini doit s’entendre ici au sens mathématique, de la même manière que la racine carrée d’un nombre négatif est indéfinie. En l’absence de cette distinction entre indéfini et inconnu, il est nécessaire (par exemple dans les bases relationnelles) de « fabriquer » un codage, du type nBgrossesses = 0, alors que la valeur indéfini traduit exactement la réalité de la situation. La valeur indéfini est utilisée par ailleurs dans le modèle des P-types, par exemple pour traduire qu’un attribut déclaré dans une vue « n’a pas de sens » hors de cette vue. C’est le cas par exemple de l’attribut manages déclaré dans la vue CEO, qui peut avoir la valeur indéfini pour un objet n’appartenant pas à la vue CEO.
L’Espace de Classement est une partition de l’espace des objets en classes d’équivalence (Eq-classes) telles que tous les objets d’une même Eq-classe appartiennent au même ensemble de vues.
Definition L’Espace de Classement d’un P-type est l’espace quotient de l’espace des objets relativement à la relation d’équivalence « avoir la même valeur de vérité vis-àvis de chacun des prédicats de domaine utilisés dans les contraintes de toutes les vues du P-type » Sous-Domaines Stables (SDS) Dans un P-type T, pour chaque attribut Attri soit Ρ(Attri) l’ensemble des prédicats élémentaires sur Attri qui apparaissent dans les contraintes des vues de T. Un prédicat élémentaire est de la forme Attri ∈ Dik où Dik est un sous-ensemble du domaine de définition Δi de Attri.
Un prédicat élémentaire Attri ∈ Dik détermine une partition de Δi en deux
éléments: Dik et (Δi - Dik). Le produit de toutes les partitions [
Un SDS vérifie la propriété de stabilité : lorsque la valeur d’un attribut Attri d’un objet ok varie à l’intérieur d’un SSD dij, l’objet ok continue de satisfaire exactement les mêmes prédicats de P(Attri).
Etant donné l’ensemble des contraintes définies dans les vues du P-type PERSON, les produits des partitions pour les attributs age, sex et salary conduisent aux partitions suivantes de leur domaine: age : d11=[0,18[, d12=[18,65[, d13=[65,120] sex: d21={f}, d22={m} salary : d31=[0,600[, d32=[600,1200[, d33=[1200,3000[, d34=[3000,SUP] où SUP désigne la plus grande valeur possible du domaine.
On note SDSATTR l’ensemble de tous les SDS de l’attribut Attr. Dans l’exemple cidessus, les SDS des trois attributs classificateurs considérés sont :
SSDage = {d11, d12, d13} SSDsex = {d21, d22}
SSDsalary = {d31, d32 d33, d34} Eq-classe La partition du domaine de chaque attribut d’un P-type est prolongée en une partition de l’espace des objets, qui constitue l’Espace de Classement du P-type. Chacun des n attributs classificateurs du P-type ayant été partitionné en SDS, l’Espace de Classement du P-type est un sous-ensemble du produit cartésien de ses SDS :
SSD1 * SSD2 * …*SSDi *… *SSDn = {<d1i, d2j, …,dnk> ⏐ d1i ∈ SSD1 ∧…∧ dnk ∈ SSDn} où SDSj représente l’ensemble des SDS de Attrj, pour j ∈ [1..n].
L’Espace de classement est un espace n-dimensionnel, où chaque Eq-classe est un hyper-cube représenté par un n-uplet de SDS. Pour des questions de représentation graphique, nous nous limitons à des espaces 3D. Ainsi, en considérant uniquement les trois attributs age, sex et salary l’Espace de Classement du P-Type PERSON est représenté dans la Fig. 1.
Les Eq-classes valides du P-type PERSON sont celles qui satisfont la vue minimale, représentées en gras sur la Fig.1. Par exemple, l’Eq-classe (d13, d22, d34), qui, en particulier, contient l’objet (age=70, sex=f, salary = 5000) est valide, tandis que tout objet de l’Eq-classe (d11, d22, d33) est invalide, car toute personne âgée de moins de 18 ans (age ∈ d11) ne peut que satisfaire d31= [0..600[ ou d32= [600..1200[.
La propriété de stabilité d’un attribut peut être étendue à tout l’Espace de Classement.
Propriété de stabilité d’une Eq-classe : tous les objets d’une même Eq-classe ont la même valeur de vérité pour toutes les vues du P-Type.
Corollaire 1 : lorsque la valeur d’un attribut d’un objet est modifiée tout en continuant d’appartenir au même SDS, l’objet continue de satisfaire les mêmes prédicats, donc les mêmes assertions, et en conséquence les mêmes vues. Corollaire2 : Lorsque plusieurs attributs d’un objet sont modifiés tout en se maintenant dans leur SDSs initiaux, l’objet continue de satisfaire les mêmes prédicats, donc les mêmes assertions, et en conséquence les mêmes vues.
d13 [65,140[
d12 [18,65[ d11 [0,18[
Sex age = 65 sex = m salary = 4000 o1
Salary d21 {f} d22 {m}
Comme deux objets de la même Eq-classe satisfont les mêmes assertions, et en conséquence valident (et invalident) les même vues, il est possible de déterminer à priori les vues que les objets d’une Eq-classe satisfont. En conséquence, il est possible d’associer à chaque vue les Eq-classes qui la satisfont.
Age Nombre d’Eq-classes. Soit n le nombre d’attributs classificateurs du P-type T. Si chaque attribut a p SDS, le nombre d’Eq-classes de T est pn.
Ainsi, la taille de l’Espace de Classement est exponentielle au nombre d’attributs classificateurs, ce qui interdit en pratique sa représentation explicite. Le classement est réalisé par un réseau où les Eq-classes ne sont pas explicites, et les structures d’indexation ne représentent que les Eq-classes qui contiennent au moins un objet (cf §3.4), garantissant ainsi l’absence d’explosion combinatoire.
On notera que les DIAs (Dépendances Inter-Attributs) créent des « trous » dans l’Espace de Classement. Ainsi, les Eq-classes (d11, d21, d33), (d11, d22, d33), (d11, d21, d34) et (d11, d22, d34) sont exclues de la zone de validité de la vue minimale de PERSON et donc du P-type, ce qui traduit qu’aucune personne mineure ne peut avoir un salaire supérieur à 1200 (assertion (a1) dans PERSON). La « vérification » de la contrainte (a1) consiste simplement à s’assurer qu’aucun objet n’est situé dans les Eq-classes invalides de l’Espace de Classement. Ainsi, l’objet étant classé dans une Eq-classe, il faut et il suffit que cette Eq-classe appartienne aux Eq-classes valides du P-type pour que l’ensemble des contraintes d’intégrité du P-type soient satisfaites, sans qu’il soit nécessaire de les vérifier individuellement. Le classement de chaque instance suffit pour valider (ou invalider) les assertions du P-type.
L’Espace de Classement constitue un pivot du système Osiris, car il sous-tend de
nombreux processus tels que le classement des objets, la classification des vues, la
vérification des contraintes d'intégrité, la vérification de cohérence des contraintes
elles-mêmes, l'indexation des objets, et l'optimisation sémantique des requêtes qui en
découle. Nous présenterons succinctement chacun de ces processus, qui sont détaillés
en [
Le classement d'un objet consiste à déterminer ses vues valides et invalides, ainsi que
ses vues potentielles lorsqu'il est incomplètement connu. Cette opération est réalisée
en Osiris au moyen d'un automate à architecture connexionniste5, que nous
désignerons par réseau de classement. La couche d'entrée est constituée des
sousdomaines stables des attributs classificateurs, et la couche de sortie par les vues du
Ptype. Pour un objet complètement connu, les activités possibles des cellules sont 1 et
0, représentant respectivement les SDS et les vues valides (1) et invalides (0) d'un
objet donné. L'architecture de ce réseau est complètement déterminée par l'analyse du
p-type, et il n'a pas besoin d'apprentissage. C'est donc un réseau exact, contrairement à
la plupart des réseaux neuronaux qui sont utilisés pour le classement dans les bases de
N
∑ n i + (N+1)n a + n v
connaissances. Sa taille est i = 1 pour un P-type ayant N attributs,
na assertions, nv vues, et où l'attribut i a ni sous-domaines stables. Une variante de ce
réseau permet également la détermination des vues potentielles d'un objet
incomplètement connu, et, lorsque des probabilités peuvent être associées aux
sousdomaines stables, il calcule la probabilité qui en résulte pour les vues potentielles [
La vérification des contraintes d'intégrité, représentées par les assertions des vues, est un « sous-produit » du classement. La question de la vérification des contraintes d'intégrité se pose lors d'une affectation impérative d'un objet à une vue (par ex. create EMPLOYEE (…)), et plus tard d'une mise à jour de l'objet. Il est nécessaire de vérifier que les assertions de la vue EMPLOYEE sont vérifiées par les valeurs des attributs de l'objet créé. Comme tout objet est classé lors de sa création, ses vues sont déterminées. La vérification des contraintes d'une vue Vi revient donc à vérifier que cette vue appartient à l'ensemble des vues valides de l'objet. Lors d'une modification, si l'objet reste dans la même Eq-classe, ce qui est testé simplement en vérifiant que les 5 Une architecture connexionniste, appelée aussi réseau de neurones, est constituée d'un graphe orienté de cellules où chaque cellule calcule une activité à partir des activités de ces cellules d'entrée et communique son activité aux cellules connectées en sortie. attributs modifiés restent dans les mêmes sous-domaines stables, le reclassement est inutile, de même que la vérification des contraintes, puisque l'objet continue d'appartenir exactement aux mêmes vues. Lorsque certains attributs changent de sousdomaine stable, l'objet est à nouveau classé.
La classification des vues, i.e., la détermination de la relation de subsomption
(d’inclusion) entre les vues, n'est pas réalisée explicitement. En effet, c'est une
opération coûteuse, dont la complexité est NP dans le cas d'Osiris, comme pour la
plupart des langages terminologiques [
Une structure d'indexation, nommée ISD (Indexing Structure Descriptor), est définie
pour chaque P-type [
Un objet, même partiellement connu, appartient à un seul ISD. En effet, dans le cas où un attribut est inconnu, on considère que l’étendue de son SDS est le domaine de l’attribut dans le P-type, noté *. On parle alors d’Eq-classe généralisée (ou simplement d’Eq-classe s’il n’y a pas d’ambiguïté). Dans cette situation, les ensembles d'Eq-classes correspondant à des ISD distincts peuvent ne pas être disjoints. Lorsqu'un attribut inconnu devient connu, l'objet change d'ISD (un nouvel ISD, subsumé par le précédent, est créé s'il n'existe pas déjà).
Lorsqu'un objet est créé, il est automatiquement classé. Ses sous-domaines stables et ses vues sont donc déterminés. Il est alors rangé dans un ISD, qui peut être créé si nécessaire. Lorsqu'un objet est modifié, il reste dans le même ISD si aucun attribut n'a changé de sous-domaine stable.
L’optimisation sémantique consiste à transformer une requête en une requête
équivalente, c’est à dire une requête dont le résultat est le même que celui de la
requête initiale pour tout état de la base de données, sur la base des informations
6 On rappelle qu'au niveau du P-type, le domaine d’un attribut qui n'est pas défini dans la vue
minimale contient valeur null.
sémantiques associées aux classes du schéma conceptuel de la base de données. Ces
informations sont essentiellement les contraintes d’intégrité associées aux classes et
aux vues. Dans [
En Osiris, une requête est évaluée à l’intérieur d’un P-type donné. Elle est assimilée à une vue (dynamique) du P-type et n’est pas classée explicitement par rapport aux autres vues du P-type. Par contre, elle est réécrite en termes des sousdomaines stables des attributs qu’elle contient, ce qui revient à la situer dans l’espace de classement en termes d’Eq-classes.
En Osiris, les requêtes sont de la forme (Ptype| Contexte | Condition), où Ptype identifie le P-type d’intérêt de la requête ; le Contexte est donné par une formule propositionnelle Φ(Vi) sur les vues, utilisant les connecteurs and, or et not. PERSON est un exemple de Ptype ; ADULT or MALE est un exemple de Contexte. La Condition exprime une condition logique sur les attributs du P-type et a la même forme que les assertions du langage Osiris. Toutefois, par simplicité, nous ne considérons pas ici le cas où la condition est une implication, et nous examinons uniquement les conditions qui sont sous la forme d'une conjonction de littéraux, constitués eux-mêmes de prédicats élémentaires ou de leur négation. Enfin, nous présentons uniquement le cas où le contexte n’est pas précisé, ce qui revient à considérer l’évaluation de la requête dans le P-type complet. Cette simplification permet d’oublier le vecteur de vues des ISD et donc de raisonner au niveau de leurs Eq-classes.
Soit le p-type PERSON (§2.2). Un exemple de requête est (PERSON|age<15). En classant la requête dans la hiérarchie des vues, l’optimisation sémantique classique permettrait de restreindre la recherche des objets d’intérêt aux objets de la vue MINOR. En Osiris, la recherche du sous-espace englobant minimal d’une requête se fait de manière plus ciblée en utilisant les ISD. Lors de l’évaluation d’une requête, l’enjeu est donc de déterminer les propriétés logiques des ISD, qui permettent de les classer en trois catégories : 1) ceux dont les objets font, de manière certaine, partie de la réponse, 2) ceux dont il faut examiner les objets individuellement, et 3) ceux dont les objets ne font pas partie de la réponse.
Ainsi, en considérant la requête
Q = (PType | Attr1 ∈ δ1∧ … ∧ Attr j ∈ δj ∧ ... ∧ Attr n ∈ δn) la méthodologie de principe pour l’optimisation sémantique est la suivante : 1. pour chaque attribut, détermination du plus petit nombre de SDS, dij, dik, … tel que dij∪ dik, ∪… ⊇ δi, où δi est le domaine du prédicat de domaine sur l’attribut Attri dans la requête. 2. détermination du sous-espace englobant minimal de la requête. Pour cela on qualifie les ISD (ici restreints aux Eq-classes).
Une Eq-classe (d1i, … djk, …, dnl) est : • • •
Valide (noté VS) : d1i ⊆ δ1, …, djk ⊆ δj, … dnl ⊆ δn Invalide : d1i ∩ δ1= φ or …, djk ∩ δj= φ or … dnl ∩ δn = φ
Potentielle (noté VP) : ni Valide ni Invalide.
L’ensemble des Eq-classes Valides et Potentielles constitue le sous-espace englobant minimal de la requête. 3. extraction des objets des Eq-classes actives du SI subsumées par les Eq-classes VS et VP de la requête, notées Eq-classes propres de la requête.
Par exemple, soient les SDS de l’attribut age : age : d11 = [0, 18[, d12 = [18, 65[, d13 = [65,120] et la requête : (PERSON | age < 70) Les Eq-classes (ISD) d’intérêt de cette requête sont :
{(d12, *, *), (d13, *, *)} où * désigne l’ensemble des SDS d’un attribut qui n’apparaît pas dans la requête.
La première est une Eq-classe (généralisée) VS et la seconde une Eq-classe (généralisée) VP. Lors de l’évaluation d’une telle requête, et en fonction des ISD présents dans le SI, les ISD actifs sont ceux se projetant sur l’une ou l’autre des Eqclasses ci-dessus (Eq-classes propres). Selon que l’Eq-classe propre est un ISD à valeur de vérité VS ou VP, les objets d’un tel ISD satisfont la requête ou doivent être filtrés par la condition de la requête. Ainsi, en considérant l’ISD <(d12, d21, *) (…)…>, cet ISD est bien un ISD d’intérêt pour la requête car il se projette sur l’Eqclasse propre (d12, *, *). De plus, comme cette Eq-classe est de type VS, tous les objets de l’ISD appartiennent à la réponse.
Nous considérons la situation où toutes les Eq-classes sont actives. Dans ce contexte, considérons la requête Q1 et l’espace de classement limité aux attributs age et salary de la requête (Fig. 2) :
Q1 : {PERSON ⏐ age > 25 and salary < 3000}
valid (12) (6) potential
invalid (13)
invalid (7)
Salary 140
d13 60 d12 d11 18
Age (8) (2) (0) valid potential invalid d31 valid (9) potential (3) (1) invalid
d32 600 1200 d33 3000 d34 sup • les Eq-classes (8), (9) et (12) sont Valides, i.e., tous les objets de ces Eqclasses font partie du résultat de la requête. • les Eq-classes (0), (1), (7) et (13) sont Invalides, i.e., aucun objet de ces Eqclasses ne fait partie du résultat de la requête. • les Eq-classes (2), (3) et (6) sont Potentielles, i.e., les objets de ces Eqclasses doivent être testés individuellement pour décider s’ils font partie ou non du résultat de la requête.
Un travail est aujourd’hui en cours de réalisation pour indexer l’espace des ISD afin d’optimiser la recherche des ISD actifs d’intérêt pour une requête.
Conçu originellement pour la gestion des données, avec l’objectif de privilégier le
rôle des utilisateurs et la vérification automatique des contraintes d’intégrité, le
modèle des P-types offre également la fonction de classement des objets,
caractéristique des bases de connaissances et toujours ignorée des SGBD classiques.
Ce classement opère dans une hiérarchie de vues, qui peut être considérée comme une
hiérarchie de classes dans le paradigme objet ou une hiérarchie de concepts dans le
paradigme des ontologies. La nature ensembliste des vues, qui sont définies par des
propriétés logiques, nous a conduits à considérer ce modèle dans la perspective des
Logiques de Description [
L’optimisation du classement, qui est fondamentale pour un usage dans les bases de données, où par nature un objet évolue dans le temps et peut changer de classe9 (de vue dans le modèle des P-types). L’organisation de l’espace des objets autour des contraintes de domaine, qui constituent en pratique la forme de contraintes la plus utilisée, a permis de définir un nouvel espace dont les éléments sont les classes d’objets équivalents vis-à-vis des contraintes. C’est l’Espace de Classement, dont les éléments, appelés Eq-classes, deviennent les unités élémentaires de traitement en lieu et place des objets.
Les Eq-classes forment un hypercube dont les dimensions sont les attributs classificateurs du P-type. En pratique, comme sa taille est exponentielle au nombre des attributs classificateurs, il n’est jamais représenté explicitement. La représentation pratique de l’espace de classement se limite aux Eq-classes actives, c’est-à-dire qui contiennent au moins un objet, évitant ainsi l’explosion combinatoire, car la taille de l’Espace de Classement est alors bornée par le nombre d’objets de la base10.
Cet hypercube n’est pas sans rappeler celui des entrepôts de données. Cette
ressemblance n’est pas anodine, et l’implantation de vues semi-persistantes dans les
7 On peut voir une certaine similarité entre l’émergence de KL-One, conçu dans un paradigme
ensembliste et logique par réaction aux Frames qui étaient très « opératoires », et celle du
modèle des P-types environ à la même époque. KL-One était dédié aux bases de
connaissances tandis que les P-types répondaient à une problématique des bases de données,
mais les deux modèles ont en commun de reposer sur une vision ensembliste des données.
8 Mais tout concept primitif dans une DL ne peut être assimilé à un P-type.
9 Les bases de données objet [
La vérification des contraintes d’intégrité est un « effet de bord » du classement et ne nécessite pas de vérification spécifique des contraintes. En effet, l’Espace de Classement résulte d’une compilation des contraintes et l’identification de l’Eq-classe d’un objet suffit à déterminer si l’objet est valide pour le P-type.
Le modèle des P-types et son système de vues ont été appliqués à l’intégration de
données. Deux thèses sont en cours, l’une sur l’intégration de données structurées et
l’autre sur l’intégration de données semi-structurées de type XML. Dans les deux cas,
la hiérarchie de vues d’un P-type joue le rôle dévolu aux ontologies dans les
approches à base de médiateurs sémantiques, et l’Espace de Classement permet une
semi-matérialisation du schéma global d’intégration [
Nous terminons en évoquant la question des données incomplètes (ou données
manquantes). La réponse des SGBD classiques, qui consiste à attribuer la valeur null
à un attribut inconnu11, ne permet pas d’autre exploitation de ces données que leur
élimination pour tout travail d’analyse de données. Dans l’univers des bases de
connaissances et de l’aide à la décision, les travaux actuels s’orientent vers l’usage
des réseaux Bayésiens ou l’introduction d’aspects probabilistes dans les approches
classiques comme les arbres de décision [
En présence de valeurs d’attribut manquantes, le classement en Osiris détermine
les vues Valides, Invalides et Potentielles. C’est le classement VIP. Lorsqu’un objet o
n’est pas complètement valué, l’objet n’appartient pas à une Eq-classe, mais
potentiellement à un certain nombre d’Eq-classes. Pour prendre en compte les objets
incomplets, la méthodologie et le réseau de classement ont été adaptés [