deep copy with bidirectional relationship

[Dr.J]

Hi All. I was hoping for some feedback on how others manage a deep
copy between two entities when they share a bidirectional association.
For illustration, consider the two entities Person and Address where a
Person can be associated with multiple addresses, an Address can be
associated with multiple Persons, and there is a requirement that
Person must know of its Addresses and Address must know of its
Persons.

As a result of performing a 100% deep copy with this type of
association you can end up with infinite recursion:
- Make a copy one of the Person requires that a copy is made of
each Address with which it is associated
- Making a copy of each Address requires that a copy is made of
each Person with which it is associated
- ad nauseum ...

While this problem is independent of the cardinality of the
association, there are some likely solutions when you make assumptions
about the association. For example, if 1:1 and the entities are simple
(not complex graphs with even more entity associations) then you could
copy each entity separately and then recreate the association.

No doubt there are a known suite of solutions to this problem but I
have been unable to track them down. To that end, any pointers would
be gratefully accepted. Furthermore, this is really a generic
programming question but one that I hoped would be of benefit to the
list.

TIA

 

[John B. Matthews]

Hi All. I was hoping for some feedback on how others manage a deep
copy between two entities when they share a bidirectional
association. For illustration, consider the two entities Person and
Address where a Person can be associated with multiple addresses, an
Address can be associated with multiple Persons, and there is a
requirement that Person must know of its Addresses and Address must
know of its Persons.

As a result of performing a 100% deep copy with this type of
association you can end up with infinite recursion:
- Make a copy one of the Person requires that a copy is made of
each Address with which it is associated
- Making a copy of each Address requires that a copy is made of
each Person with which it is associated
- ad nauseum ...

While this problem is independent of the cardinality of the
association, there are some likely solutions when you make
assumptions about the association. For example, if 1:1 and the
entities are simple (not complex graphs with even more entity
associations) then you could copy each entity separately and then
recreate the association.

If Person and Address were entities in a relational database, a
PersonAddress table would be used to model the many-to-many association.
Suitable constraints would preclude spurious Persons and phony
Addresses. Joining through the PersonAddress table would permit queries
such as a Person's Address(es), Person(s) residing at an Address,
homeless Person(s), and vacant Address(es).

Creating an object model might start by loading Map<Key, Person>,
Map<Key, Address> and List<PersonAddress>, where each PersonAddress
instance would contain a pair of foreign Keys. These could be used to
construct Map<Person, List<Address>> and Map<Address, List<Person>>. A
deep copy would simply repeat the process.

Absent a relational database and starting with Map<Person,
List<Address>> and Map<Address, List<Person>>, it should be possible
construct List<Person>, List<Address> and List<PersonAddress>, where
each PersonAddress instance would contain a pair of object references
instead of two foreign keys. Cloning these would preclude the recursion
problem when recreating the two starting Maps.

No doubt there are a known suite of solutions to this problem but I
have been unable to track them down. To that end, any pointers would
be gratefully accepted. Furthermore, this is really a generic
programming question but one that I hoped would be of benefit to the
list.

Someone with more experience in Object Relational Mapping might be able
to offer more insight.

 

[Dr.J]

If Person and Address were entities in a relational database, a
PersonAddress table would be used to model the many-to-many association.
Suitable constraints would preclude spurious Persons and phony
Addresses. Joining through the PersonAddress table would permit queries
such as a Person's Address(es), Person(s) residing at an Address,
homeless Person(s), and vacant Address(es).

Creating an object model might start by loading Map<Key, Person>,
Map<Key, Address> and List<PersonAddress>, where each PersonAddress
instance would contain a pair of foreign Keys. These could be used to
construct Map<Person, List<Address>> and Map<Address, List<Person>>. A
deep copy would simply repeat the process.

Absent a relational database and starting with Map<Person,
List<Address>> and Map<Address, List<Person>>, it should be possible
construct List<Person>, List<Address> and List<PersonAddress>, where
each PersonAddress instance would contain a pair of object references
instead of two foreign keys. Cloning these would preclude the recursion
problem when recreating the two starting Maps.


Someone with more experience in Object Relational Mapping might be able
to offer more insight.

Thanks for replying John. I think your suggestion above falls into the
"making assumptions about the association" bucket that I mentioned
above and would likely become unwieldy in the general sense, i.e.
deep, complex object graphs.

I have since poked around some more and found a number of candidates
that are agnostic to the object graph:
a) Serialization: http://www.javaworld.com/javaworld/javatips/jw-javatip76.html?page=2
b) Recursion using a "memo": http://rebrained.com/?p=24

Of course there are constraints that may prevent you implementing
either of these approaches in that
(a) every entity in the association supports serialization;
performance, and
(b) every entity implements a deep copy method that uses a memo.

I chose (b).

 

[Dr.J]

If Person and Address were entities in a relational database, a
PersonAddress table would be used to model the many-to-many association.
Suitable constraints would preclude spurious Persons and phony
Addresses. Joining through the PersonAddress table would permit queries
such as a Person's Address(es), Person(s) residing at an Address,
homeless Person(s), and vacant Address(es).

Creating an object model might start by loading Map<Key, Person>,
Map<Key, Address> and List<PersonAddress>, where each PersonAddress
instance would contain a pair of foreign Keys. These could be used to
construct Map<Person, List<Address>> and Map<Address, List<Person>>. A
deep copy would simply repeat the process.

Absent a relational database and starting with Map<Person,
List<Address>> and Map<Address, List<Person>>, it should be possible
construct List<Person>, List<Address> and List<PersonAddress>, where
each PersonAddress instance would contain a pair of object references
instead of two foreign keys. Cloning these would preclude the recursion
problem when recreating the two starting Maps.


Someone with more experience in Object Relational Mapping might be able
to offer more insight.

Thanks for replying John. Your suggestion falls into the "make
assumptions about the association" bucket I mentioned. In contrast, I
was looking for a solution that made as few assumptions as possible.

After some further digging I came across two alternative approaches
that fall into this category.
a) Serialization: http://www.javaworld.com/javaworld/javatips/jw-javatip76.html?page=2
b) Recursion: http://rebrained.com/?p=24

The simplicity of (b) and the likely performance hit of (a) makes for
a straightforward choice, IMHO.

 

[Mark Rafn]

Hi All. I was hoping for some feedback on how others manage a deep
copy between two entities when they share a bidirectional association.

This is a fairly standard reference graph.

As a result of performing a 100% deep copy with this type of
association you can end up with infinite recursion:

You need to keep track of what objects you've already copied, and make sure
that you don't make second copies when you should just set a second reference.

For example, if 1:1 and the entities are simple
(not complex graphs with even more entity associations) then you could
copy each entity separately and then recreate the association.

Why bother? It'll break as soon as you hit an interesting case. Handling the
general case isn't much work.

No doubt there are a known suite of solutions to this problem but I
have been unable to track them down. To that end, any pointers would
be gratefully accepted. Furthermore, this is really a generic
programming question but one that I hoped would be of benefit to the
list.

During your copy, keep an IdentityHashMap with original as key and copy as
value. Whe you're about to copy something, instead see if it's in the
map already, and if so, just use it. If not, copy it and add the entry to
the map.

 

[John B. Matthews]

<0b1958e5-fee5-43ae-a71d-b61cf8bda...@c18g2000prh.googlegroups.com>,

[...]
Thanks for replying John. Your suggestion falls into the "make
assumptions about the association" bucket I mentioned. In contrast, I
was looking for a solution that made as few assumptions as possible.

After some further digging I came across two alternative approaches
that fall into this category.
a) Serialization:
http://www.javaworld.com/javaworld/javatips/jw-javatip76.html?page=2

This would be a good alternative to using a database if you'd already
implemented Serializable for some other reason.

b) Recursion: http://rebrained.com/?p=24

The simplicity of (b) and the likely performance hit of (a) makes for
a straightforward choice, IMHO.

Yes, memoization will likely give you a more general solution with less
effort. Mark Rafn's suggestion above to use IdentityHashMap in this
context is particularly apropos:

http://java.sun.com/javase/6/docs/api/java/util/IdentityHashMap.html

 

[Dr.J]

This is a fairly standard reference graph.


You need to keep track of what objects you've already copied, and make sure
that you don't make second copies when you should just set a second reference.


Why bother? It'll break as soon as you hit an interesting case. Handling the
general case isn't much work.


During your copy, keep an IdentityHashMap with original as key and copy as
value. Whe you're about to copy something, instead see if it's in the
map already, and if so, just use it. If not, copy it and add the entry to
the map.

Thanks Mark/John for the courteous and timely responses. Graph theory isn't my strong suit
so thanks for the pointers.

Dr.J