I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures. Any connections with UML models and reasoning about them (other than drawing diagrams) would also be of interest to me.

[There is of course a lot of work - and tool sets - for mapping data structures to relational databases and back. But my interest is in reasoning about in-memory data structures using relational models.]

[For example, a doubly-linked list can be represented in the relational model as a pair of relations: $successor$ and $predecessor$, tied together by a couple of integrity constraints $successor(x,y) \Rightarrow predecessor(y,x)$ and its converse (modulo boundary cases). In more interesting examples, we would have tons of relations and constraints. The question I am wondering about is whether the relational database theory can help us get handle on how to build good data structures, modularise them appropriately and provide some structure to the constraints (or "invariants") so that it is easier to verify them or to ensure correctness by construction.]

  • $\begingroup$ I assume you're interested in semantics, rather than complexity ? $\endgroup$ May 6 '12 at 17:47
  • $\begingroup$ Well, I am primarily interested in program correctness issues, which was in fact the major driving force of Codd's programme. But, for a start, I would be happy to look at any application of relational models in modelling data structures (even if it was done for the purposes of complexity analysis). $\endgroup$
    – Uday Reddy
    May 6 '12 at 20:10
  • $\begingroup$ Gavin Bierman at MSRC mentioned to me that he was doing something like this. I don't think he's published anything yet, but it might be worth getting in touch. $\endgroup$ May 7 '12 at 9:00
  • $\begingroup$ In addition to relational databases, it also occurs to me that knowledge representation systems, in particular things like "truth maintenance systems", might be even more relevant to the data structure problems. They presumably model dependencies between relations whereas relational databases only model dependencies between attributes. SAT solvers like Alloy work with relations a lot too. (Thanks for the tip about Gavin Bierman.) $\endgroup$
    – Uday Reddy
    May 7 '12 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.