Data structure for partial orders

Hello,

I'm looking for possible choices of data structures for storing a partial order P. The structure should allow for (relatively) fast

- element checks (given A and B find out if (A,B) in P or (B,A) in P)

- calculation of transitive closure (The closure itself doesn't have to be stored explicitely if checking whether A and B can be compared using transitivity can be done in a "fast" way)

- locating incomparable elements (i.e. elements A and B such that neither (A,B) in P nor (B,A) in P)

- updating with new elements (i.e. adding (A,B) to P)

As a bonus it would be nice if checking for inconsistences with respect to a possible new element could be easily done (e.g. checking whether after adding (A,B) P is still a partial order).

Any pointers on this are greatly appreciated.


Regards,
Florian
.