Création d'une règle d'héritage dans une structure hiérarchique

CUCARACHA · 31/05/2012, 10h55

Salut,

Je travaille sur une structure hiérarchique dynamique, c'est à dire que les règles d'héritage (tel type de noeud ne peut avoir comme fils que des neuds dont le type est contenu dans une liste).

Dans un cas particulier d'un neud de type A qui a pour fils un noeud de type B. J'ai besoin de créer une règle dont l'algo serait le suivant :

Si Fils de A = B alors le nombre de B doit être 0 ou 1, sinon peut importe le nombre de fils.

Quelqu'un pourrait-il m'aider à créer cette règle sachant que :

TypeNoeud
Id int [PK]
Nom nvarchar(50) [Unique]

A
Id int [PK]
FK_A int [FK]
FK_TypeNoeud int [FK] a

B
Id int [PK]
FK_A int [FK] A.id
FK_TypeNoeud int [FK] b

D'avance merci pour votre aide,

Laurent

**Sergejack** · 06/06/2012, 15h23

Vous êtes sûr de vouloir un modèle de ce genre ?

Ce type d'arbre n'est pas performant en SQL (utilisez au moins le type hierarchyid sinon).

Moi, j'utiliserais ... heu... zut, j'ai aucun souvenir du nom de cet algorithme.
Bref ça ressemble à ça:

niveau 0
(Root) left: 1, right : 12

niveau 1
(A) left: 2, right :5
(A) left: 6, right : 11

niveau 2
(B) left: 3, right 4
(B) left: 7, right : 8 -- Votre règle est violée car right <> A.right - 1 *
(B) left: 9, right: 10 -- Votre règle est violée car left <> A.left + 1 *

* règle facile à vérifier

CUCARACHA · 06/06/2012, 15h27

Bonjour,

Merci pour votre réponse.

Les perfs on verra plus tard.

L'algo s'appelle d'arbre intervallaire et SQL Pro l'a super bien présenté ici : http://sqlpro.developpez.com/cours/arborescence/

En fait, je ne sais pas où écrire la règle.

D'avance merci pour la suite

Sincères salutations,

Laurent

**Sergejack** · 06/06/2012, 15h44

Vous pourriez utilisez un trigger "instead of" ou mieux (sauf si je n'ai pas tout compris) indiquer que la FK ver A de la table B est unique.

CUCARACHA · 06/06/2012, 15h46

Il faut que tu manges plus de poisson, c'est bon pour la mémoire !

**Sergejack** · 06/06/2012, 15h51

Envoyé par Laurent Jordi

Il faut que tu manges plus de poisson, c'est bon pour la mémoire !

Je mange bcp de dauphin, pourtant. Ha, zut, c'est pas du poisson

Note: j'ai fait un edit à mon post précédent.

**punkoff** · 06/06/2012, 16h03

bonjour,

Mais vous avez 2 tables ?
Quel est votre MCD ?

**Moggik** · 07/06/2012, 07h42

Personnellement, je n'essayerais pas de stocker ça dans une base SQL Server, car ce n'est vraiment pas adapté.
C'était souvent fait par le passé...avec des résultats niveau performances médiocres.

Pourquoi ne pas se pencher sur une solution plus adaptée comme Neo4J ou une autre base NoSQL orientée graphe ?

CUCARACHA · 07/06/2012, 09h19

Salut salut,

parenthèse begin

Merci de ne pas remettre en cause mon choix car il est dicté par des centaines de raisons valables que je n'ai pas le temps d'expliquer ici... Un programme ça évolue en conséquence, l'important est qu'il fonctionne au départ, c'est après qu'on optimise et on peaufine sans quoi le programme meurt avant d'être né.

parenthèse end

Pour en revenir à nos moutons à savoir est il possible de mettre une règle qui vérifie le nombre de fils d'un enregistrement lors de l'insertion (si possible sans passer par un trigger car ça je sais faire et pour le coup, c'est vraiment pénalisant en termes de perfs et ça pourrait verrouiller la base).

Pour le MCD, voici les scripts de création des tables

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
USE [InnovaCMS]
GO
 
/****** Object:  Table [DOC].[TypeNode]    Script Date: 06/07/2012 09:14:18 ******/
SET ANSI_NULLS ON
GO
 
SET QUOTED_IDENTIFIER ON
GO
 
CREATE TABLE [DOC].[TypeNode](
	[Id] [int] NOT NULL,
	[FK_HierarcyType] [int] NOT NULL,
	[Nom] [nvarchar](50) NOT NULL,
	[Description] [nvarchar](150) NULL,
	[rowversion] [timestamp] NULL,
 CONSTRAINT [PK_TypeNode] PRIMARY KEY CLUSTERED 
(
	[Id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
 
GO
 
USE [InnovaCMS]
GO
 
/****** Object:  Table [DOC].[AccesTypeNode]    Script Date: 06/07/2012 09:15:51 ******/
SET ANSI_NULLS ON
GO
 
SET QUOTED_IDENTIFIER ON
GO
 
CREATE TABLE [DOC].[AccesTypeNode](
	[Id] [int] IDENTITY(1,1) NOT NULL,
	[FK_TypeNode] [int] NOT NULL,
	[FK_TypeNodeAccess] [int] NOT NULL,
	[rowversion] [timestamp] NULL,
 CONSTRAINT [PK_AccesTypeNode] PRIMARY KEY CLUSTERED 
(
	[Id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
 
GO
 
ALTER TABLE [DOC].[AccesTypeNode]  WITH CHECK ADD  CONSTRAINT [R_TypeNode_AccessTypeNode_TypeNodeConcerne] FOREIGN KEY([FK_TypeNode])
REFERENCES [DOC].[TypeNode] ([Id])
GO
 
ALTER TABLE [DOC].[AccesTypeNode] CHECK CONSTRAINT [R_TypeNode_AccessTypeNode_TypeNodeConcerne]
GO
 
ALTER TABLE [DOC].[AccesTypeNode]  WITH CHECK ADD  CONSTRAINT [R_TypeNode_AccessTypeNode_TypesNodeAutorisees] FOREIGN KEY([FK_TypeNodeAccess])
REFERENCES [DOC].[TypeNode] ([Id])
GO
 
ALTER TABLE [DOC].[AccesTypeNode] CHECK CONSTRAINT [R_TypeNode_AccessTypeNode_TypesNodeAutorisees]
GO

C'est juste un arbre indépendant du reste de la base dont les règles d'héritage sont dynamiques. Le truc c'est qu'en plus de dynamiser le fait que papa ne peut avoir que tels types d'enfants, j'ai aussi besoin de programmer le fait que papa ne peut avoir que 2 enfants si papa est de tel type.

Je pourrais le faire en complexifiant la jointure mais avant, je voudrais savoir s'il est possible de le créer sous forme d'une simple règle peut-être avec une fonction utilisateur dans un champ calculé qui renvoie true/false...

D'avance merci pour votre aide,

Laurent

**Sergejack** · 07/06/2012, 09h47

Un trigger instead of n'est pas si pénalisant que ça (à ne pas faire l'amalgame avec les performances d'un trigger after, comme le font certains...).

CUCARACHA · 07/06/2012, 11h01

Je ne connais pas le instead... je connais les classiques insert/update/delete...
Tu peux m'en dire plus ?
Merci
Laurent

**Sergejack** · 07/06/2012, 11h51

L’écriture est la même que celle des triggesr AFTER.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
CREATE TRIGGER <nom>
ON <table>
INSTEAD OF { INSERT, UPDATE , DELETE }
AS
BEGIN
<...>
END

Ces triggers s’exécute lors des DML plutôt qu'après (ce qui évite de "faire" pour "défaire" ensuite).
La grosse différence est que dans ces triggers, il faut inclure la modification à faire.

Genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
CREATE TRIGGER ... ON dbo.maTable INSTEAD OF INSERT
AS
BEGIN
 IF <règle violée> BEGIN
 ROLLBACK TRANSACTION
 EXIT
 END
 
 INSERT INTO dbo.maTable (
  ...
 )
 SELECT
  ...
 FROM inserted
END

En plus avec MERGE qui permet INSERT + UPDATE + DELETE simultanément, il devient très facile d'écrire un seul trigger pour gérer les 3 opérateurs.

**iberserk** · 10/06/2012, 11h25

Si vous ne voulez pas utiliser de TRIGGER créez une contrainte de type CHECK appelant un fonction scalaire de votre cru incluant vos règles...

**azur668** · 11/06/2012, 15h10

Bonjour Laurent,
Tu nous a communiqué la structure des types de noeuds et des Types de noeuds enfant autorisés.
Quelle est la structure de la table d'arborescence elle-même ?
Si tu stocke dans ta table d'arborescence le type du Noeud Parent en plus du FK du Noeud Parent,
il y a une possibilité avec un index unique filtré.

CUCARACHA · 11/06/2012, 15h17

Meaculpa mais bon, elle est super simple en fait...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
USE [InnovaCMS]
GO
 
/****** Object:  Table [DOC].[Hierarchy]    Script Date: 06/11/2012 15:15:45 ******/
SET ANSI_NULLS ON
GO
 
SET QUOTED_IDENTIFIER ON
GO
 
CREATE TABLE [DOC].[Hierarchy](
	[Id] [int] IDENTITY(1,1) NOT NULL,
	[FK_HierarchyType] [int] NOT NULL,
	[FK_Hierarchy] [int] NULL,
	[FK_TypeNode] [int] NOT NULL,
	[Title] [nvarchar](255) NOT NULL,
	[Position] [int] NOT NULL,
	[rowversion] [timestamp] NULL,
 CONSTRAINT [IX_PK_HierarchyType] PRIMARY KEY CLUSTERED 
(
	[Id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
 
GO
 
ALTER TABLE [DOC].[Hierarchy]  WITH CHECK ADD  CONSTRAINT [R_Hierarchy_Hierarchy] FOREIGN KEY([FK_Hierarchy])
REFERENCES [DOC].[Hierarchy] ([Id])
GO
 
ALTER TABLE [DOC].[Hierarchy] CHECK CONSTRAINT [R_Hierarchy_Hierarchy]
GO
 
ALTER TABLE [DOC].[Hierarchy]  WITH CHECK ADD  CONSTRAINT [R_Hierarchy_TypeNode] FOREIGN KEY([FK_TypeNode])
REFERENCES [DOC].[TypeNode] ([Id])
ON UPDATE CASCADE
ON DELETE CASCADE
GO
 
ALTER TABLE [DOC].[Hierarchy] CHECK CONSTRAINT [R_Hierarchy_TypeNode]
GO

That's all la mécanique n'est pas dans la base, c'est de l'ajax...

++

Laurent

**azur668** · 11/06/2012, 16h34

1) dans la table Hierarchy, tu rajoutes le champ ParentTypeNode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ALTER TABLE [DOC].[Hierarchy]  WITH CHECK ADD  CONSTRAINT [R_Hierarchy_Hierarchy] FOREIGN KEY([FK_Hierarchy],ParentTypeNode) REFERENCES [DOC].[Hierarchy] ([Id], [DOC].FK_TypeNode)

2) Tu crée un index filtré sur FK_TypeNode, ParentTypeNode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
CREATE UNIQUE NONCLUSTERED INDEX [Regle1] ON [DOC].[Hierarchy]  
(FK_Hierarchy,[FK_TypeNode],  ParentTypeNode ASC) 
WHERE FK_TypeNode = x and ParentTypeNode =y
GO

-Fonctionne uniquement sur SQLserver 2008 (sinon utiliser les vues indexées)
-On ne peut que interdire plus d'un enfant, pas contrôler précisément le nombre d'enfants autorisés.
-Il faut créer un index par paire Parent/Enfant
-Seuls les enfant de type X seront limités, cela ne limite pas le nombre d'autres enfants d'autres types.

CUCARACHA · 11/06/2012, 18h09

Merci à tous, je crois que la réponse qui me séduit le plus est celle d'iberserk.
Création d'une contrainte Check avec une fonction que je ponds moi-même.

Il faut comprendre que tout ça est très dynamique puisqu'il peut-y avoir plusieurs types d’arborescences.

En conséquence, les règles d'héritage doivent impérativement être dynamiques comme le reste sans quoi ça verrouillerait tout.

Je pense que je vais modifier légèrement la table des acces pour ajouter le nombre de fils autorisés : 1 à n pour un nombre limité et -1 pour retirer la limite.

Ceci combiné à la proposition d'iberserk devrait faire l'affaire.

Je ne sais pas si ça risque d'être pénalisant pour les perfs, je vais faire des tests.

Encore merci à tous pour votre aide,

Laurent

**iberserk** · 12/06/2012, 06h38

Laurent, tout dépend de ta volumétrie.

Si ta table possède de nombreux enregistrement avec des INSERT/UPDATE/DELETE pointant sur plusieurs de ses enregistrement en même temps un TRIGGER sera probablement plus performant.

Le mieux comme tu le dis est de tester... et penser aux bons index.

A+

CUCARACHA · 12/06/2012, 07h24

Le jour où le volumétrie sera trop importante, je seras tellement riche que ça sera certainement quelqu'un d'autre qui se chargera de l'optim... En attendant, je trim