JpaTreeDao - Hierarchies in Database Tables

Author: Ritzberger Fritz, September 2013

Download Sources
from here until I find the time to publish this. You can do what you like with it, except publishing it under your own name. That means this is freeware, but I claim its authorship.

Introduction

Nested Sets
Closure Table

Terms
Programming with JpaTreeDao

Common Behavior

Nested Sets

Provide the entity
Provide the database layer
Allocate the DAO
Remarks

Closure Table

Provide the entities
Provide the database layer
Allocate the DAO
Remarks

Temporal Extensions

Common behaviour
Nested Sets
Closure Table

DAO API
Concurrency

Unique Constraints
The Update Problem
Caching Trees
Another Recoverable Remove Method
Copying Nodes

CopiedNodeTemplate parameter
CopiedNodeRenamer interface

List of examples

Introduction

JpaTreeDao enables you to add hierarchical structure to database tables managed by a Java ORM layer (Object-Relational Mapping) like Hibernate or EclipseLink.

This document tries to make the use of JpaTreeDao library quick and easy. It is not an introduction to Nested Sets and Closure Table concepts. Please read about this on the internet. I learnt a lot from (and want to thank) Bill Karwin, who published articles and slides about trees in database tables.

What do you need to know about these methods when using JpaTreeDao?

Nested Sets

Uses indexes stored within the managed entity to model the hierarchy. That means you need to

add two integer fields to your entity that should become a tree: "lft" and "rgt"
(can not use "left" and "right" as these are SQL key words).

To enable several roots within the same table, you also need to

add a "topLevel" field, which is a reference (foreign key) to the root of the tree the entity belongs to.

Because tree info is stored directly within the entity, such an entity can belong to only one tree.
Although there can be several roots within a "nested sets" database table, these trees can not share nodes.
Because the structural management is done by lft and rgt indexes, children lists always have a defined order. You can not get rid of that order.

Advantages:

can read a whole tree (or sub-tree) using only one query (-> not just children lists)
most operations (add, remove, copy, move) are fast

Disadvantages:

an entity can belong to only one tree
there are no parent references and no children lists in entities, all of that must be done through DAO calls
children listings require reading the whole sub-tree below parent node and thus might be slow

Closure Table

Uses an additional paths-table where tree structures (references, level, order) are stored. No additional fields are needed in your entity.
Through that, a tree node entity can belong to more than one tree, lets call it tree-aspect. For each tree-aspect you will need one additional paths-table.
Nevertheless several roots (that can not share nodes) can exist in just one paths-table.

Advantages:

several tree-aspects of one node table are possible
several roots in one tree-aspect are possible
the node table needs no additional attributes to become a tree

Disadvantages:

several roots within one tree-aspect can not share nodes
operations are slower than Nested Sets tree operations (due to lots of path references to manage)

Remark

Adjacency List is the traditional way to hold trees in database tables. This method uses a simple parent reference in every entity. With a JPA back-reference, a children list would be available directly in such an entity. Such trees are nice for subsequent tree branch expansion, but complicated when you need to read the whole tree at once (e.g. for a report). JpaTreeDao doesn't provide an Adjacency List implementation.

Terms

Entity, *Node, Tree Node*	The Java object representation of a database record in memory.
Children	The direct children of a parent, not the whole tree below it.
Temporal	Is used to indicate that no physical database deletion takes place when a node is removed. Records are deleted by historicizing them, i.e. setting a validTo timestamp property. There are DAO methods that provide access to historicized nodes and allow recovery. You can even override DAO methods to implement another deletion-mechanism than validFrom and validTo fields (see "Another Recoverable Remove Method").

Programming with JpaTreeDao

You have to provide classes to get productive with JpaTreeDao:

provide the entity class to manage as tree by implementing one of the NestedSetsTreeNode or ClosureTableTreeNode interfaces

for ClosureTable, provide also a path-entity by implementing the TreePath interface

provide the database layer by implementing the DbSession interface

The programming model is a DAO, meaning you have no children-list and no parent-reference in your entity, you need to call the DAO to get these. You need the DAO for any operation on the tree. For a quick insight look at the examples in test directory.

Note: Although this library is based on JPA EntityManager, you can use it with Hibernate Session, too (older Hibernate versions). Look for the

DbSessionHibernateImpl

Java class in test directory. It is an alternative implementation of the DbSession interface. It contains a workaround for the differences between HQL and JPQL. There are also unit-tests that prove that everything works with HQL.

Common Behaviour

As said, the DAO abstracts

the managed entities (database tables), and
the database layer needed to perform persistence actions

Here are the constructors of NestedSetsTreeDao (manages one database table) and ClosureTableTreeDao (manages two database tables, one for nodes and one for paths).

	public NestedSetsTreeDao(
			Class<? extends NestedSetsTreeNode> entityClass,
			DbSession session)
	
	public NestedSetsTreeDao(
			Class<? extends NestedSetsTreeNode> entityClass,
			String entityName,
			DbSession session)


	public ClosureTableTreeDao(
			Class<? extends ClosureTableTreeNode> treeNodeEntityClass,
			Class<? extends TreePath> treePathsEntityClass,
			boolean orderIndexMatters,
			DbSession session)
	
	public ClosureTableTreeDao(
			Class<? extends ClosureTableTreeNode> treeNodeEntityClass,
			String treeNodeEntity,
			Class<? extends TreePath> treePathEntityClass,
			String treePathEntity,
			boolean orderIndexMatters,
			DbSession session)

You need to pass the entity class and the database layer (as instance) to the DAO at construction time. Additionally you can pass in the name of the according JPQL entity (differing from the simple class-names of the Java entity). This is for the case that your entities are just interfaces and have a backing implementation with another name. JpaTreeDao uses entityClass.getSimpleName() as default entityName. While with NestedSetsTreeDao you can not get rid of children order, you can tell the ClosureTableTreeDao if order matters or not.

Nested Sets

Provide the entity

Your entity needs additional fields lft, rgt and topLevel like in the following example (see also class PersonNst in test-package).
For copy-actions clone() is required, which should leave the clone's primary key null.
In other words: the interface NestedSetsTreeNode must be implemented by your entity to fit to the DAO.

@Entity
public class Person implements NestedSetsTreeNode
{
	@Id
	@GeneratedValue
	private String id;	// primary key

	private String name;	// some person property
	
	@ManyToOne(targetEntity = Person.class)
	private NestedSetsTreeNode topLevel;	// root reference
    
	private int lft;	// NestedSets index - "left" would be a SQL keyword!
	private int rgt;	// NestedSets index - "right" would be a SQL keyword!
	
	public Person() {
	}
	public Person(String name) {
		this.name = name;
	}
	
	@Override
	public String getId() {
		return id;
	}

	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}

	@Override
	public NestedSetsTreeNode getTopLevel() {
		return topLevel;
	}
	@Override
	public void setTopLevel(NestedSetsTreeNode topLevel) {
		this.topLevel = topLevel;
	}
	
	@Override
	public int getLeft() {
		return lft;
	}
	@Override
	public void setLeft(int left) {
		this.lft = left;
	}

	@Override
	public int getRight() {
		return rgt;
	}
	@Override
	public void setRight(int right) {
		this.rgt = right;
	}

	@Override
	public Person clone()	{
		return new Person(getName());
	}
}

Mind that you should not access your entity table through another mechanism than the DAO. Only the DAO provides the necessary knowledge for an entity to be identified as a tree member. For example, an empty root node has lft=1, rgt=2 and topLevel = this.

Provide the database layer (ORM)

Next you need to provide a DbSession implementation to the DAO. This interface abstracts the database layer from the DAO. For JPA-compatible database layers (ORM) like EclipseLink or Hibernate-EntityManager you need just one implementation, configuring the layer by a persistence-unit name from persistence.xml.

You can simply copy the implementation that is in the test-package, called

DbSessionJpaImpl.java:

public class DbSessionJpaImpl implements DbSession
{
	private final EntityManager entityManager;
	
	public DbSessionJpaImpl(EntityManager entityManager) {
		this.entityManager = entityManager;
	}
	
	@Override
	public Object get(Class<?> entityClass, Serializable id) {
		return entityManager.find(entityClass, id);
	}
	@Override
	public Object save(Object node)	{
		return entityManager.merge(node);
	}
	@Override
	public void flush() {
		entityManager.flush();
	}
	@Override
	public void refresh(Object node) {
		entityManager.refresh(node);
	}
	@Override
	public void delete(Object node) {
		entityManager.remove(node);
	}
	@Override
	public List<?> queryList(String queryText, Object[] parameters) {
		return query(queryText, parameters).getResultList();
	}
	@Override
	public int queryCount(String queryText, Object[] parameters) {
		List result = queryList(queryText, parameters);
		return ((Number) result.get(0)).intValue();
	}
	@Override
	public void executeUpdate(String sqlCommand, Object[] parameters) {
		Query query = query(sqlCommand, parameters);
		query.executeUpdate();
	}
	
	private Query query(String queryText, Object[] parameters) {
		Query query = entityManager.createQuery(queryText);
		if (parameters != null)	{
			int i = 1;
			for (Object parameter : parameters)	{
				if (parameter == null)
					throw new IllegalArgumentException("Binding parameter at position "+i+" can not be null: "+queryText);
				query.setParameter(i, parameter);
				i++;
			}
		}
		return query;
	}
}

For Hibernate-Session variant (not JPA-compatible) you can copy following implementation, again in test-package:

DbSessionHibernateImpl.java

Of course you will need the JPA EntityManager as constructor parameter, here is sample code to get one:

		final String PERSISTENCE_UNIT_NAME = "your-persistence-unit-name";
		final EntityManagerFactory entityManagerFactory = Persistence.createEntityManagerFactory(PERSISTENCE_UNIT_NAME);
		final EntityManager entityManager = entityManagerFactory.createEntityManager();

This works with a JPA persistence.xml in META-INF directory (see test/resources package). Following example uses Hiberate-EntityManager (see Maven POM for Version) and H2 as in-memory database. To avoid auto-scanning for classes annotated with @Entity you need to remove hibernate.archive.autodetection and use <class>your.package.YourEntity</class> elements instead (refer to persistence.xml schema).

<persistence
		xmlns="http://java.sun.com/xml/ns/persistence"
		xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
		xsi:schemaLocation="http://java.sun.com/xml/ns/persistence http://java.sun.com/xml/ns/persistence/persistence_2_0.xsd"
		version="2.0">

	<persistence-unit name="your-persistence-unit-name">
		<provider>org.hibernate.ejb.HibernatePersistence</provider>
		
		<properties>
			<property name="javax.persistence.jdbc.driver" value="org.h2.Driver"/>
			<property name="javax.persistence.jdbc.user" value="sa"/>
			<property name="javax.persistence.jdbc.password" value=""/>
			<property name="javax.persistence.jdbc.url" value="jdbc:h2:mem:db1;DB_CLOSE_DELAY=-1;MVCC=TRUE"/>
			
			<property name="hibernate.dialect" value="org.hibernate.dialect.H2Dialect"/>
			
			<!-- Make Hibernate scan for annotated classes -->
			<property name="hibernate.archive.autodetection" value="class" />
		</properties>
	</persistence-unit>
</persistence>

Allocate the DAO

After this all has been done, you are ready to apply the DAO. Its name is NestedSestTreeDao (temporal extension is TemporalNestedSestTreeDao). You can find this example code in test-package in

examples/nestedsets/JpaExample.java

		final EntityTransaction transaction = entityManager.getTransaction();
		transaction.begin();

		final DbSession dbSession = new DbSessionJpaImpl(entityManager);
		final NestedSetsTreeDao dao = new NestedSetsTreeDao(Person.class, dbSession);
		
		// add a constraint that checks that a person's name is unique across the whole tree
		dao.setUniqueTreeConstraint(new UniqueWholeTreeConstraintImpl(
						new String [][] { { "name" } },
						false));
		
		// create a tree
		final NestedSetsTreeNode walter = dao.createRoot(new Person("Walter"));
		assert dao.getRoots().size() == 1;
		
		// insert root children
		final NestedSetsTreeNode linda = dao.addChild(walter, new Person("Linda"));
		final NestedSetsTreeNode mary = dao.addChild(walter, new Person"Mary"));
		assert dao.size(walter) == 3;
		
		// add children to a child
		final NestedSetsTreeNode peter = dao.addChild(mary, new Person("Peter"));
		final NestedSetsTreeNode paul = dao.addChild(mary, new Person("Paul"));
		assert dao.size(walter) == 5;
		assert dao.size(mary) == 3;
		
		// retrieve children lists
		final List<NestedSetsTreeNode> childrenOfWalter = dao.getChildren(walter);
		assert childrenOfWalter.size() == 2 && childrenOfWalter.get(0).equals(linda) && childrenOfWalter.get(1).equals(mary);
		
		final List<NestedSetsTreeNode> childrenOfMary = dao.getChildren(mary);
		assert childrenOfMary.size() == 2 && childrenOfMary.get(0).equals(peter) && childrenOfMary.get(1).equals(paul);

		transaction.commit();

How to do this with Hibernate-Session you can see in test-package in classes named

HibernateSessionExample.java

For this you will need a hibernate.cfg.xml file in your CLASSPATH root, you can find an example in test/resources package.

Remarks

Do not use getLeft() and getRight() indexes and getTopLevel() in any way, and do not change them. Changes might break the tree. Left/right values may have gaps when TemporalNestedSetsTreeDao is used, so their values might not be what you expect.

Do not use a deleted entity anymore after deletion, e.g. inserting it again, not even after its managing JPA session was closed. If you need its values, clone it and insert the clone. This also applies to all children that were below a deleted parent!

Closure Table

Provide the entities

You need the node entity and another entity that describes the tree structure (so there will be two database tables). The first needs no additional tree properties, just clone() is required for implementing interface ClosureTableTreeNode. The second must implement interface TreePath.

Following is an example node entity (see also class PersonCtt in test-package):

@Entity
public class Person implements ClosureTableTreeNode
{
	@Id
	@GeneratedValue
	private String id;

	@Column(nullable = false)
	private String name;

	public Person() {
	}
	public Person(String name) {
		this.name = name;
	}

	@Override
	public String getId() {
		return id;
	}

	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}

	@Override
	public ClosureTableTreeNode clone() {
		return new Person(getName());
	}
}

You can access the node table through other mechanisms than the DAO, but only nodes that were added through the DAO will be in tree. Adding a node through the DAO will also make it persistent (if it is not yet).

This is an example TreePath implementation (see also class PersonOrganizationalTreePath in test-package):

@Entity
@IdClass(CompositePersonTreePathId.class)
public class PersonTreePath implements TreePath
{
	@Id
	@ManyToOne(targetEntity = Person.class)
	@JoinColumn(name = "ancestor", nullable = false)
	private ClosureTableTreeNode ancestor;

	@Id
	@ManyToOne(targetEntity = Person.class)
	@JoinColumn(name = "descendant", nullable = false)
	private ClosureTableTreeNode descendant;

	@Column(nullable = false)
	private int depth;

	private int orderIndex;

	@Override
	public ClosureTableTreeNode getAncestor() {
		return ancestor;
	}
	@Override
	public void setAncestor(ClosureTableTreeNode ancestor) {
		this.ancestor = ancestor;
	}

	@Override
	public ClosureTableTreeNode getDescendant() {
		return descendant;
	}
	@Override
	public void setDescendant(ClosureTableTreeNode descendant) {
		this.descendant = descendant;
	}

	@Override
	public int getDepth() {
		return depth;
	}
	@Override
	public void setDepth(int depth) {
		this.depth = depth;
	}

	@Override
	public int getOrderIndex() {
		return orderIndex;
	}
	@Override
	public void setOrderIndex(int position) {
		this.orderIndex = position;
	}
}

The primary key of PersonTreePath is composed by the primary keys of ancestor and descendant (JPA @IdCass annotation). Here is an implementation for primary keys of type String (see also class CompositePersonTreePathId in test-package):

public class CompositePersonTreePathId implements Serializable
{
	private String ancestor;	// must have same name as TreePathImpl.ancestor, and data-type like TreePathImpl.ancestor.id
	private String descendant;	// must have same name as TreePathImpl.descendant, and data-type like TreePathImpl.descendant.id
	
	public String getAncestor() {
		return ancestor;
	}
	public void setAncestor(String ancestorId) {
		this.ancestor = ancestorId;
	}
	public String getDescendant() {
		return descendant;
	}
	public void setDescendant(String descendantId) {
		this.descendant = descendantId;
	}
	
	@Override
	public boolean equals(Object o) {
		if (o == this)
			return true;
		if (o instanceof CompositePersonTreePathId == false)
			return false;
		final CompositePersonTreePathId other = (CompositePersonTreePathId) o;
		return other.getDescendant().equals(getDescendant()) && other.getAncestor().equals(getAncestor());
	}
	
	@Override
	public int hashCode() {
		return getDescendant().hashCode() * 31 + getAncestor().hashCode();
	}
}

Provide the database layer (ORM)

This is the same as with Nested Sets, see there.

Allocate the DAO

Ready to start programming with the DAO. Its name is ClosureTableTreeDao (temporal extension is TemporalClosureTableTreeDao).

Following sample code shows how two tree-aspects are built upon the same node table. The first is a organizational hierarchy of persons, the usual chief/staff thing, while the second is a functional one, lets say an expert/beginner thing. Mind that you need two different TreePath implementations (tree-aspects) for that! You can find this example code (and the two TreePath implementations used in it) in test-package in class

examples/closuretable/JpaExample.java

		final EntityTransaction transaction = entityManager.getTransaction();
		transaction.begin();

		final DbSession dbSession = new DbSessionJpaImpl(entityManager);
		final ClosureTableTreeDao organizationalDao = new ClosureTableTreeDao(Person.class, PersonOrganisationalTreePath.class, true, dbSession);
		final ClosureTableTreeDao functionalDao = new ClosureTableTreeDao(Person.class, PersonFunctionalTreePath.class, true, dbSession);
		
		// create persons and build organizational tree

		final ClosureTableTreeNode walter = organizationalDao.createRoot(new Person("Walter"));
		
		final ClosureTableTreeNode linda = organizationalDao.addChild(walter, new Person("Linda"));
		final ClosureTableTreeNode mary = organizationalDao.addChild(walter, new Person("Mary"));
		
		final ClosureTableTreeNode peter = organizationalDao.addChild(mary, new Person("Peter"));
		final ClosureTableTreeNode paul = organizationalDao.addChild(mary, new Person("Paul"));
		
		final List<ClosureTableTreeNode> organizationalChildrenOfWalter = organizationalDao.getChildren(walter);
		assert organizationalChildrenOfWalter.size() == 2 &&
			organizationalChildrenOfWalter.get(0).equals(linda) &&
			organizationalChildrenOfWalter.get(1).equals(mary);
		
		final List<ClosureTableTreeNode> organizationalChildrenOfMary = organizationalDao.getChildren(mary);
		assert organizationalChildrenOfMary.size() == 2 &&
			organizationalChildrenOfMary.get(0).equals(peter) &&
			organizationalChildrenOfMary.get(1).equals(paul);
		
		// build functional tree using the same persons
		
		functionalDao.createRoot(walter);
		functionalDao.createRoot(linda);	// "Linda" is another root 

		functionalDao.addChild(linda, peter);
		functionalDao.addChild(linda, paul);
		
		functionalDao.addChild(walter, mary);
		
		final List<ClosureTableTreeNode> functionalChildrenOfWalter = functionalDao.getChildren(walter);
		assert functionalChildrenOfWalter.size() == 1 &&
			functionalChildrenOfWalter.get(0).equals(mary);
		
		final List<ClosureTableTreeNode> functionalChildrenOfLinda = functionalDao.getChildren(linda);
		assert functionalChildrenOfLinda.size() == 2 &&
			functionalChildrenOfLinda.get(0).equals(peter) &&
			functionalChildrenOfLinda.get(1).equals(paul);

		transaction.commit();

Remarks

The DAO by default does not remove anything from the node table when a tree path is removed. You can change this by dao.setRemoveReferencedNodes(true), default is false. When using several tree-aspects (paths tables) upon the same entity, this could be dangerous, a foreign key constraint would hit when removing a node that is still referenced by another tree-aspect.

Maintaining child node order is optional. When you pass orderIndexMatters = false to the DAO constructor, children lists would have a random order. Maybe tree operations will be a little faster then.

When you put additional fields into your TreePath entity, you can access them by calling dao.getTreePathEntity(node). The parameter is the entity of the node table you want to get information for. The returned TreePath is the one that represents the self-reference of the given node entity. Do not change order or depth in the returned TreePath, this could break the tree!

Temporal extensions

The temporal DAO variants extend their base-DAO and override several methods to manage the removal of nodes. Nodes won't be removed physically but "historicized", meaning a Timestamp field named validTo gets the current date when the entity is removed. Afterwards it will not be visible anymore, although still present in the tree.

There are methods to find and recover removed nodes, and to physically remove them, see TemporalTreeDao API. You can also replace the JpaTreeDao historization logic by overriding certain DAO methods, see below.

Common behavior

Your Nested Sets node entity (or Closure Table path entity) must provide a validTo field of type Date (JPA annotation Timestamp), and optionally can provide a validFrom field (same type). If validFrom is in future, the entity with such a value won't be visible.

If your entity can provide validFrom and validTo properties, pass Temporal.VALID_FROM and Temporal.VALID_TO as arguments to the constructor.
If you have other names for validFrom and/or validTo properties, pass these names to the DAO constructor. Nevertheless you MUST implement the Temporal interface, annotate these methods as @Transient in your entity (else validFrom and validTo fields would be generated in database table) and redirect them to the other properties.
If you have no validFrom field (no support for future validity), pass null as validFromPropertyName argument to the DAO constructor.
If you decide to use a deleted flag or similar for removal, see "Another Recoverable Remove Method".

Following examples will show how to program the TemporalTreeDao variants.

Nested Sets

Your node entity must implement interface TemporalNestedSestTreeNode, and you must pass the names of the Temporal properties to the DAO constructor (typically "validFrom" and "validTo").

Following example is different, it shows a special case, not a typical application. The validTo property is redirected to an endValid property, and validFrom is dismissed. This is to demonstrate how to use the temporal extension when your entity can't provide a property with name "validTo" for some reason, and you won't support future validity (validFrom).

Here is the example node entity. Mind how you can implement Temporal, leaving out validFrom with do-nothing implementations, and using @Transient annotations for all Temporal methods.

@Entity
public class Person implements TemporalNestedSetsTreeNode
{
	@Id
	@GeneratedValue
	private String id;

	@Column(nullable = false)
	private String name;

	@ManyToOne(targetEntity = Person.class)
	private NestedSetsTreeNode topLevel;

	private int lft;
	private int rgt;

	@Temporal(TemporalType.TIMESTAMP)
	private Date endValid;	// the "validTo" substitute, "validFrom" is not present at all

	public Person() {
	}

	public Person(String name) {
		this.name = name;
	}

	@Override
	public String getId() {
		return id;
	}

	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}

	public Date getEndValid() {
		return endValid;
	}
	public void setEndValid(Date endValid) {
		this.endValid = endValid;
	}
	
	@Override
	public NestedSetsTreeNode getTopLevel() {
		return topLevel;
	}
	@Override
	public void setTopLevel(NestedSetsTreeNode topLevel) {
		this.topLevel = topLevel;
	}

	@Override
	public int getLeft() {
		return lft;
	}
	@Override
	public void setLeft(int left) {
		this.lft = left;
	}

	@Override
	public int getRight() {
		return rgt;
	}
	@Override
	public void setRight(int right) {
		this.rgt = right;
	}

	@Override
	public Person clone() {
		return new Person(getName());
	}

	@Transient	// will not generate a validTo field
	@Override
	public Date getValidTo() {	// redirect to endValid
		return endValid;
	}
	@Transient
	@Override
	public void setValidTo(Date validTo) {	// redirect to endValid
		this.endValid = validTo;
	}
	
	@Transient
	@Override
	public Date getValidFrom() {	// do nothing than implement Temporal
		return null;
	}
	@Transient
	@Override
	public void setValidFrom(Date validFrom) {	// do nothing than implement Temporal
	}
}

And here is an example application for that entity, you find it in test-package in class

examples/nestedsets/temporal/JpaExample

Mind how the DAO is constructed. We pass null as validFrom property name, as we do not support future validity, and we pass "endValid" as the real validTo property name (needed by the DAO for JPQL queries).

		final EntityTransaction transaction = entityManager.getTransaction();
		transaction.begin();

		final DbSession dbSession = new DbSessionJpaImpl(entityManager);
		final TemporalNestedSetsTreeDao dao = new TemporalNestedSetsTreeDao(
				Person.class,
				null,	// entity does not support validFrom property
				"endValid",	// entity's substitute for validTo property, needed in JPQL queries
				dbSession);
		
		final NestedSetsTreeNode walter = dao.createRoot(new Person("Walter"));
		final NestedSetsTreeNode peter = dao.addChild(walter, new Person("Peter"));
		final NestedSetsTreeNode paul = dao.addChild(walter, new Person("Paul"));
		final NestedSetsTreeNode mary = dao.addChild(walter, new Person("Mary"));
		
		final List<NestedSetsTreeNode> childrenOfWalter = dao.getChildren(walter);
		assert childrenOfWalter.size() == 3 &&
			childrenOfWalter.get(0).equals(peter) &&
			childrenOfWalter.get(1).equals(paul) &&
			childrenOfWalter.get(2).equals(mary);
		
		dao.remove(peter);
		
		final List<NestedSetsTreeNode> newChildrenOfWalter = dao.getChildren(walter);
		assert newChildrenOfWalter.size() == 2 &&
			newChildrenOfWalter.get(0).equals(paul) &&
			newChildrenOfWalter.get(1).equals(mary);
		
		// recover node
		final Map<String,Object> criteria = new Hashtable<String,Object>();
		criteria.put("name", "Peter");
		final List<NestedSetsTreeNode> result = dao.findRemoved(walter, criteria);
		final Person removedPeter = (Person) result.get(0);
		dao.unremove(removedPeter);

		transaction.commit();

Closure Table

Your path entity must implement interface TemporalTreePath, and you must pass the names of the Temporal properties to the DAO constructor (typically "validFrom" and "validTo").

Here is a typical path entity (use the normal Person as node entity like in the non-temporal example).

@Entity
@IdClass(CompositePersonTreePathId.class)
public class PersonTreePath implements TemporalTreePath
{
	@Id
	@ManyToOne(targetEntity = Person.class)
	@JoinColumn(name = "ancestor", nullable = false)
	private ClosureTableTreeNode ancestor;

	@Id
	@ManyToOne(targetEntity = Person.class)
	@JoinColumn(name = "descendant", nullable = false)
	private ClosureTableTreeNode descendant;

	@Column(nullable = false)
	private int depth;

	private int orderIndex;

	@Temporal(TemporalType.TIMESTAMP)
	private Date validFrom;
    
	@Temporal(TemporalType.TIMESTAMP)
	private Date validTo;
	
	@Override
	public ClosureTableTreeNode getAncestor() {
		return ancestor;
	}
	@Override
	public void setAncestor(ClosureTableTreeNode ancestor) {
		this.ancestor = ancestor;
	}

	@Override
	public ClosureTableTreeNode getDescendant() {
		return descendant;
	}
	@Override
	public void setDescendant(ClosureTableTreeNode descendant) {
		this.descendant = descendant;
	}

	@Override
	public int getDepth() {
		return depth;
	}
	@Override
	public void setDepth(int depth) {
		this.depth = depth;
	}

	@Override
	public int getOrderIndex() {
		return orderIndex;
	}
	@Override
	public void setOrderIndex(int position) {
		this.orderIndex = position;
	}

	@Override
	public Date getValidTo() {
		return validTo;
	}
	@Override
	public void setValidTo(Date validTo) {
		this.validTo = validTo;
	}

	@Override
	public Date getValidFrom() {
		return validFrom;
	}
	@Override
	public void setValidFrom(Date validFrom) {
		this.validFrom = validFrom;
	}
}

Following example DAO application you find in test-package in class

examples/closuretable/temporal/JpaExample

		final EntityTransaction transaction = entityManager.getTransaction();
		transaction.begin();
		
		final DbSession dbSession = new DbSessionJpaImpl(entityManager);
		
		final TemporalClosureTableTreeDao dao = new TemporalClosureTableTreeDao(
				Person.class,
				PersonTreePath.class,
				true,
				Temporal.VALID_FROM,
				Temporal.VALID_TO,
				dbSession);
		
		final ClosureTableTreeNode walter = dao.createRoot(new Person("Walter"));
		dao.remove(walter);
		
		assert dao.getRoots().size() == 0;
		assert dao.getAllRoots().size() == 1;	// it is still there!

		dao.unremove(walter);
		assert dao.getRoots().size() == 1;

		transaction.commit();

DAO API

Here is an outline of the DAO API. Please refer to JavaDoc for detailed semantics.

public interface TreeDao <N extends TreeNode> 
{
	N createRoot(N root) throws UniqueConstraintViolationException;
	List<N> getRoots();
	
	N addChild(N parent, N child) throws UniqueConstraintViolationException;
	N addChildAt(N parent, N child, int position) throws UniqueConstraintViolationException;
	N addChildBefore(N sibling, N child) throws UniqueConstraintViolationException;

	void update(N entity) throws UniqueConstraintViolationException;

	void remove(N node);
	void removeAll();

	N find(Serializable id);
	List<N> find(N parent, Map<String,Object> criteria);
	
	int size(N tree);
	N getRoot(N node);
	N getParent(N node);
	List<N> getPath(N node);
	List<N> getChildren(N parent);
	int getChildCount(N parent);
	boolean isEqualToOrChildOf(N child, N parent);
	boolean isChildOf(N child, N parent);
	boolean isRoot(N entity);
	boolean isLeaf(N node);
	int getLevel(N node);

	List<N> getTreeCacheable(N parent);
	List<N> findSubTree(N parent, List<N> treeCacheable);
	List<N> findDirectChildren(List<N> treeCacheable);
	
	List<N> getTree(N parent);
	
	void move(N node, N newParent) throws UniqueConstraintViolationException;
	void moveTo(N node, N parent, int position) throws UniqueConstraintViolationException;
	void moveBefore(N node, N sibling) throws UniqueConstraintViolationException;
	void moveToBeRoot(N child) throws UniqueConstraintViolationException;
	
	N copy(N node, N parent, N copiedNodeTemplate) throws UniqueConstraintViolationException;
	N copyTo(N node, N parent, int position, N copiedNodeTemplate) throws UniqueConstraintViolationException;
	N copyBefore(N node, N sibling, N copiedNodeTemplate) throws UniqueConstraintViolationException;
	N copyToBeRoot(N child, N copiedNodeTemplate) throws UniqueConstraintViolationException;

	void setUniqueTreeConstraint(UniqueTreeConstraint<N> uniqueTreeConstraint);
	void setCheckUniqueConstraintOnUpdate(boolean checkUniqueConstraintOnUpdate);
	void checkUniqueConstraint(N cloneOfExistingNodeWithNewValues, N root, N originalNode) throws UniqueConstraintViolationException;

	public interface CopiedNodeRenamer <N extends TreeNode>
	{
		void renameCopiedNode(N node);
	}
	
	void setCopiedNodeRenamer(CopiedNodeRenamer<N> copiedNodeRenamer);
}

Remarks:

For all copy, move and addChild method calls it is important to use the returned entity after the operation, not the one passed as argument. The reason is the implementation of save(), which performs a JPA merge(), and this might return another instance than the one passed in.
You need a special method to copy or move a sub-tree to root level: copyToBeRoot(), moveToBeRoot().
The update() method might be not so useful, see "Update Problem", as well as the getTree() method, because you can not extract children lists from its result.

The temporal extension adds following methods:

public interface TemporalTreeDao <N extends TreeNode> extends TreeDao<N>
{
	List<N> findRemoved(N parent, Map<String,Object> criteria);

	void unremove(N node);
	
	List<N> getAllRoots();
	
	List<N> getFullTreeCacheable(N parent);
	List<N> findValidDirectChildren(List<N> treeCacheable);
	
	void removePhysically(N node);
	void removeHistoricizedTreesPhysically();
	void removeAllPhysically();
}

You can apply the non-temporal method findDirectChildren() on a getFullTreeCacheable() result to find both removed and valid children, and with the result of findValidDirectChildren() you can generate a difference list that will contain just the removed children.

Concurrency

A JpaTreeDao instance is thread-safe, but does no transaction management and no table locking. In a multi-threaded and multi-process environment thread-safety is not enough. The caller of any DAO write method is expected to ensure that no other thread or process accesses the targeted table(s) until the write has terminated. In other words, you have to grant atomicity, consistency and isolation. JpaTreeDao does not do that.

For instance, when adding a child node into a Nested Sets Tree, the DAO performs several database statements:

it reads all nodes of the affected sub-tree
it calculates new left/right indexes for them
it inserts the new node and updates the sub-tree with new left/right indexes

Imagine one application reads nodes before another application can write its pending new indexes for those nodes. The first application would write wrong indexes then. You could end up with inconsistent or destroyed trees. So every DAO needs exclusive access to the table it writes. You could achieve this by a table lock, or a SERIALIZABLE transaction (not allowing read- or write-access until it has terminated).

Mind further that when you cache sub-trees (getTreeCacheable()), you need to release the cache as soon as the tree was modified.

Unique Constraints

There are problems with hierarchies and unique constraints. When you define constraints on database level, all nodes of all trees in the table would be affected by them. But you might want uniqueness only per tree root, moreover you might want it only per tree level (unique children lists). Database level constraints can not cover that. Thus we need programmed constraints.

Basically you can write your own constraints by implementing the interface UniqueTreeConstraint. You can install this by calling

dao.setUniqueTreeConstraint(constraint)

That constraint will be called on any addChild(), copy*() and move*(). It will not be called on update(), unless you configure dao.setCheckUniqueConstraintOnUpdate(true). See "Update Problem" chapter.

JpaTreeDao comes with following UniqueTreeConstraint implementations:

UniqueWholeTreeConstraintImpl checks that given properties are unique in the whole tree below a certain root
UniqueChildrenConstraintImpl checks that given properties are unique in every children list of every parent below a certain root
plus the temporal variants of both: UniqueWholeTreeTemporalConstraintImpl, UniqueChildrenTemporalConstraintImpl

Mind that the DAO does not use any constraint by default, you must configure it explicitly.
All of them accept a String[][] array in constructor, containing the names of properties to be unique. Combined property-sets are in inner arrays. For example, to check properties

"name" combined with "code", and
"acronym"

for uniqueness, you must do the following:

		dao.setUniqueTreeConstraint(new UniqueWholeTreeConstraintImpl(
						new String [][] { { "name","code" }, { "acronym" } },
						false));

As a result every combination of name and code property values will be unique per tree root, and so will acronym values.

The Update Problem

When you change a unique property of an entity which is already in persistent state, the JPA layer notices it and prepares an SQL update statement. When you start a constraint check (query) after that modification, the JPA layer will flush its pending changes. When the constraint check now finds a violation, it would throw an exception. When you somehow commit the transaction after that exception, the invalid value will be stored, by-passing the constraint, because it already has been flushed. Even when you rollback the transaction, the invalid value stays in the entity and might be stored later in another transaction which re-attaches the entity.

So what to do against such pitfalls?

never commit a transaction that received a UniqueConstraintViolationException
restore the old value(s) in the entity that caused the exception (but do not do that by a refresh(), as this would refresh from the already flushed invalid entity; evict() does not help either), or do not use that entity anymore.

It might be difficult to restore the old value (recorded it before the update?), as well as it might be difficult to use the entity no more (is it in some cache?). When you are sure that your transaction and cache management can handle UniqueConstraintViolationException adequately and somehow get rid of the entity with the invalid value, then do a dao.setCheckUniqueConstraintOnUpdate(true), which will cause the DAO to check unique constraints on any update() call. Default is false.

Here is a safe way to update a constrained property:

		dao.setCheckUniqueConstraintOnUpdate(true);
		
		final String oldName = peter.getName();
		try	{
			peter.setName("Pietro");
			dao.update(peter);	// throws exception when not unique and dao.checkUniqueConstraintOnUpdate == true
		}
		catch (UniqueConstraintViolationException e)	{
			peter.setName(oldName);
			throw e;
		}

Alternatively you can explicitly check the constraint before calling the setter of a unique property (the "do not let it happen" strategy). This goes with dao.checkUniqueConstraintOnUpdate == false (default).

clone() the existing node to be updated (every TreeNode is Cloneable) to achieve a detached template node
set the new value(s) to the clone
call dao.checkUniqueConstraint(clone, root, existingNode)
in case this throws UniqueConstraintViolationException, report this to the user
else set the new value to the existing node and call dao.update(existingNode), or simply commit the transaction.

		final String petersNewName = "Pietro";
		final Person peterClone = (Person) peter.clone();	// clone has null primary key
		peterClone.setName(petersNewName);
		dao.checkUniqueConstraint(	// would throw exception when not unique
				peterClone,	// the rename candidate
				walter,	// the root node
				peter);	// the existing node

		peter.setName(petersNewName);	// no exception was thrown
		dao.update(peter);	// will not check again when dao.checkUniqueConstraintOnUpdate == false (is default)

Caching Trees

The advantage of using JpaTreeDao is that you can read a whole tree with just one query. The disadvantage is that reading children lists is quite slow, at least for Nested Sets.

JpaTreeDao supports gaining performance by providing following methods:

getTreeCacheable(parent)
findDirectChildren(treeCacheable)
findSubTree(topNode, treeCachable)

The first reads a whole tree (or sub-tree) as a List, the second can extract children lists or sub-trees from that List without accessing the database at all (and thus is very fast). So when you cache the result of getTreeCacheable, you can apply findDirectChildren or findSubTree on that result to read very quickly:

		final List<N> waltersTree = dao.getTreeCacheable(walter);
		
		final List<N> marysSubTree = dao.findSubTree(mary, waltersTree);
		
		final List<N> waltersChildren = dao.findDirectChildren(waltersTree);
		final List<N> marysChildren = dao.findDirectChildren(marysSubTree);

JpaTreeDao does not cache anything by itself, it is up to you to put the cacheable results into some cache implementation.

Another Recoverable Remove Method

This is about the temporal DAOs. Following example shows how historization is redirected to a simple boolean deleted flag, without any Date fields. The sample is built upon TemporalClosureTableTreeDao, but it would be the same for TemporalNestedSetsTreeDao, except that you must use the node entity for redirection, not the path entity.

You find this example code in

examples/closuretable/temporal/deletedflag/JpaExample

The node entity is the same as in the non-temporal example.
Here is the path entity with its deleted flag:

@Entity
@IdClass(CompositePersonTreePathId.class)
public class PersonTreePath implements TemporalTreePath
{
	@Id
	@ManyToOne(targetEntity = Person.class)
	@JoinColumn(name = "ancestor", nullable = false)
	private ClosureTableTreeNode ancestor;

	@Id
	@ManyToOne(targetEntity = Person.class)
	@JoinColumn(name = "descendant", nullable = false)
	private ClosureTableTreeNode descendant;

	@Column(nullable = false)
	private int depth;

	private int orderIndex;

	private boolean deleted;

	@Override
	public ClosureTableTreeNode getAncestor() {
		return ancestor;
	}
	@Override
	public void setAncestor(ClosureTableTreeNode ancestor) {
		this.ancestor = ancestor;
	}

	@Override
	public ClosureTableTreeNode getDescendant() {
		return descendant;
	}
	@Override
	public void setDescendant(ClosureTableTreeNode descendant) {
		this.descendant = descendant;
	}

	@Override
	public int getDepth() {
		return depth;
	}
	@Override
	public void setDepth(int depth) {
		this.depth = depth;
	}

	@Override
	public int getOrderIndex() {
		return orderIndex;
	}
	@Override
	public void setOrderIndex(int position) {
		this.orderIndex = position;
	}

 	// dummy implementation of interface Temporal
	
	@Transient	// will not generate a validTo field
	@Override
	public Date getValidTo() {
		return null;
	}
	@Transient	// will not generate a validTo field
	@Override
	public void setValidTo(Date validTo) {
	}
	@Transient	// will not generate a validTo field
	@Override
	public Date getValidFrom() {
		return null;
	}
	@Transient	// will not generate a validTo field
	@Override
	public void setValidFrom(Date validFrom) {
	}
	
	// the really used remove-implementation
	
	public boolean isDeleted() {
		return deleted;
	}
	public void setDeleted(boolean deleted) {
		this.deleted = deleted;
	}
}

And here the related example application, you can find this in

examples/closuretable/temporal/deletedflag/JpaExample

Mind how we pass null for both validFrom and validTo property names to the DAO constructor, to it make it ignore both fields. The override will adjust the queries and removals to do what they are expected.

		final EntityTransaction transaction = entityManager.getTransaction();
		transaction.begin();
		
		final DbSession dbSession = new DbSessionJpaImpl(entityManager);
		
		final TemporalClosureTableTreeDao dao = new TemporalClosureTableTreeDao(Person.class, PersonTreePath.class, true, null, null, dbSession)
		{
			@Override
			public boolean isValid(Temporal node, Date validityDate) {
				return ((PersonDeletedFlagTreePath) node).isDeleted() == false;
			}
			
			@Override
			protected void assignInvalidity(TreePath path) {
				((PersonDeletedFlagTreePath) path).setDeleted(true);
			}
			@Override
			protected void assignValidity(TreePath path) {
				((PersonDeletedFlagTreePath) path).setDeleted(false);
			}
			
			@Override
			public void appendValidityCondition(String tableAlias, StringBuilder queryText, List<Object> parameters) {
				appendCondition(true, tableAlias, queryText, parameters);
			}
			@Override
			protected void appendInvalidityCondition(String tableAlias, StringBuilder queryText, List<Object> parameters) {
				appendCondition(false, tableAlias, queryText, parameters);
			}
			
			private void appendCondition(boolean validity, String tableAlias, StringBuilder queryText, List<Object> parameters) {
				queryText.append(buildAliasedPropertyName(tableAlias, "deleted")+" = "+buildIndexedPlaceHolder(parameters));
				parameters.add(validity ? Boolean.FALSE : Boolean.TRUE);
			}
		};
		
		final ClosureTableTreeNode walter = dao.createRoot(new Person("Walter"));
		dao.remove(walter);
		
		assert dao.getRoots().size() == 0;
		assert dao.getAllRoots().size() == 1;
		
		transaction.commit();

Copying Nodes

When copying nodes, you might want to do some changes to the copied nodes before they are stored to persistence. This is particularily useful when copying a node and pasting it into the same parent, but a unique constraint would then complain about duplicate names.

There are two ways to do this:

copiedNodeTemplate parameter
TreeDao.CopiedNodeRenamer interface

CopiedNodeTemplate parameter

This is an optional parameter (can be null) for all copy*() methods. When not null, this node would be used as the top-level node of the copied tree. None of the copied sub-nodes would be affected by that template. Such would be useful for trees with UniqueChildrenConstraint on pasting a copied tree into its own parent, because then the copied sub-nodes will not violate the constraint, but the top-level node will.

		final Person copiedMaryTemplate = (Person) mary.clone();
		copiedMaryTemplate.setName("Copy of "+mary.getName());
		
		// walter is root, mary is child, with peter and paul as children
		final Person copiedMary = dao.copy(mary, walter, copiedMaryTemplate);
		assert copiedMary.getName().equals("Copy of Mary");
		
		List<Person> copiedMarysChildren = dao.getChildren(copiedMary);
		for (Person person : copiedMarysChildren)	{
			assert person.getName().startsWith("Copy of ") == false;
		}

CopiedNodeRenamer interface

This is a more sophisticated solution that provides an interface you can implement and then install into the DAO. Once installed, the CopiedNodeRenamer would receive any copied node after it has been copied and before it gets stored to persistence. The implementation is expected to do edits on the node which avoid constraint violations. e.g. by person.setName("Copy of "+person.getName()). By means of CopiedNodeRenamer you can edit all nodes of a copied tree, useful when having UniqueWholeTreeConstraint.

		dao.setCopiedNodeRenamer(new TreeDao.CopiedNodeRenamer<Person>() {
			@Override
			public void renameCopiedNode(Person person) {
				person.setName("Copy of "+person.getName());
			}
		});
		
		// walter is root, mary is child, with peter and paul as children
		final Person copiedMary = dao.copy(mary, walter, null);
		assert copiedMary.getName().equals("Copy of Mary");
		
		List<Person> waltersTree = dao.getTree(walter);
		assert waltersTree.contains(copiedMary);

		for (Person person : waltersTree)	{
			assert person.getName().startsWith("Copy of ");
		}

List of examples

You find all available examples in

src/test/java/fri/util/database/jpa/tree/examples

directory, their names are JpaExample or HibernateSessionExample. Most example entities are in the same directory as the example that uses them. Their names differ from the names used in this documentation, because all entity names must be unique when using auto-scanning for annotated classes, so there are PersonNst, PersonCtt, PersonTctt and so on.

JpaTreeDao - Hierarchies in Database Tables

Contents

Introduction

Nested Sets

Advantages:

Disadvantages:

Closure Table

Advantages:

Disadvantages:

Remark

Terms

Programming with JpaTreeDao

Common Behaviour

Nested Sets

Provide the entity

Provide the database layer (ORM)

Allocate the DAO

Remarks

Closure Table

Provide the entities

Provide the database layer (ORM)

Allocate the DAO

Remarks

Temporal extensions

Common behavior

Nested Sets

Closure Table

DAO API

Concurrency

Unique Constraints

The Update Problem

Caching Trees

Another Recoverable Remove Method

Copying Nodes

CopiedNodeTemplate parameter

CopiedNodeRenamer interface

List of examples