Création d'un ramasse-miettes en Python

L’idée ci-dessous est de construire une arborescence en SQL, avec son API en Python. Cette arborescence sera relativement simple:

• Chaque noeud de l’arbre peut avoir entre 1 et N enfants.
• Si un noeud ne possède pas de parent, il sera considéré comme une racine.
• Si un noeud ne possède aucun enfant, il sera considéré comme une feuille.

En SQL

#

Au niveau de la représentation relationnelle, le plus simple est d’avoir une table Node qui possède une référence vers elle-même. De cette manière, nous pouvons représenter un noeud grâce à trois attributs:

• Son identifiant, Id
• L’identifiant de son parent, ParentId, qui peut être éventuellement nul
• Un libellé, Label.

Un petit exemple ci-dessous en T-SQL:

CREATE TABLE Node (
	[Id] int IDENTITY(1,1) NOT NULL PRIMARY KEY,
	[ParentId] int NULL FOREIGN KEY REFERENCES Entity(Id),
	[Label] nvarchar(255) NOT NULL
)

Cette méthode rend par contre impossible la récupération des descendants ou ascendants grâce à une requête directe. En fonction du nombre de niveaux à parcourir, il sera nécessaire d’effectuer autant de requêtes distinctes qu’il y a de niveaux. Pour construire une arborescence sur trois niveaux, nous devrons bien exécuter trois requêtes différentes:

1. Une première pour trouver un noeud par rapport à son identifiant
2. Une deuxième pour récupérer son parent,
3. Suivie d’une troisième qui permettra de récupérer le parent du parent.

A ce stade, nous devrions être à la racine de notre arbre, puisque le champ ParentId du dernier résultat sera nul.

Une autre possibilité est de construire une fonction tabulaire qui, pour un identifiant donné, va construire la liste et la retourner dans une table temporaire, en y ajoutant un indice de position. Dans cette implémentation, la racine aura la position zéro:

CREATE FUNCTION [dbo].[BreadCrumb]
(
	@currentid int
)
RETURNS @Tab TABLE (Id int, pos int, ParentId int, Label nvarchar(255))
	AS
Begin
	Declare @parentid int;
	Declare @label nvarchar(max);
	Declare @entitytypeid int;
	Declare @i int;

	Set @parentid = @currentid;
	Set @i = 0;

	While(@parentid is not null)
	Begin
		set @currentid = @parentid;

		(Select @parentid = ParentId, @label = Entity.Label
			From Entity Where Entity.Id = @currentid);

		INSERT INTO @Tab (id, pos, label, parentid)
		VALUES (@currentid, @i, @label, @parentid)
		set @i = @i + 1;
	End

	return;
END;

Comme expliqué ci-dessus, le résultat retourne une table qui contient quelques colonnes (l’id, le parentid, le label et la position), et permet de chipoter un peu parmi les liens de l’arborescenc: il suffit de communiquer un identifiant en paramètre à la fonction, pour ressortir toute l’arborescence. Magique (ou presque, jusqu’à ce que la table soit trop peuplée que pour être efficiente).

Avec un ORM

#

Une autre approche est de passer par un ORM. Pour l’exemple (et parce que “c’est le plus mieux” ©), ça sera l’ORM de Django. Pour l’exemple, j’ai créé une simple classe ‘Album’ (de photos), chacun d’entre eux pouvant contenir plusieurs sous-albums. Le principe est le même: pour retracer l’arborescence d’un élément, il faut remonter jusqu’à la racine, afin de pouvoir construire le ramasse-miettes.

class Album(models.Model):
	name = models.CharField(verbose_name='Nom', max_length=50)
	slug = models.SlugField(max_length=50, blank=False, editable=True)
	description = models.CharField(
        verbose_name='Description', 
        max_length=255, 
        null=True, 
        blank=True
    )
	parent = models.ForeignKey('self', null=True, blank=True)	

	def __unicode__(self):
		return self.name

	def illustration(self):
		""" returns an illustration for the album """
		pictures = self.picture_set.all()

		if len(pictures) > 0:
			return pictures[0].picture
		else:
			return None

	def parentbreadcrumb(self):
		return self.breadcrumb()[:-1]

	def breadcrumb(self):
		""" Returns the breadcrumb for the current album """
		if self.parent == None:
			return (self,)

		return self.parent.breadcrumb() + (self,)

	def path(self):
		"""
		returns the path where the album structure should be stored
		"""
		return os.sep.join((x.name for x in self.breadcrumb()))

Le problème reste entier, puisque le nombre de requêtes à effectuer sera toujours égal aux nombres de niveaux à parcourir. Mais cela devrait suffire pour des cas relativement simples.