Archive for the ‘database theory’ Category

on CAP

January 19, 2016

The “CAP theorem” is often presented as something deep and hard to understand, and then discussed in confusing terms, to make sure it is hard to understand.  Really, it’s almost common sense – eg, if you have a partition, you have to give up availability or consistency.  Anyone familiar with, eg, drbd/split-brain/STONITH knows all about this.

I was reading a bit about it (again), and I use the sneer quotes on “theorem” because I think that the “proof” is really just adding some mathematical terms to the mix and restating it – QED.  (If this is considered the proof – “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services” .)  “Conjecture” doesn’t seem right either.  Maybe CAP observation?

It’s refreshing to find an update written by Eric Brewer (the originator) in 2012, “CAP Twelve Years Later: How the “Rules” Have Changed“.  It’s very readable (down-to-earth), interesting, and informative.  I recommend it to anyone interested in the subject who hasn’t already read it.

 

Tarski and Codd

November 25, 2015

Wikipedia says that “Relational calculus is essentially equivalent to first-order logic, and indeed, Codd’s Theorem had been known to logicians since the late 1940s.”  I couldn’t find the cited sources online, but did find these interesting papers:

Applications of Alfred Tarski’s Ideas in Database Theory

and

Tarski’s influence on computer science.” (see the section starting “The final thing I want to tell something about is the connection of Tarski’s ideas and work with database theory.”)

If you’ve studied mathematical logic (or math, eg, topology), you are probably familiar with Tarski’s name.  The historical development of mathematical logic and relational database theory is an interesting topic I’d like to understand better.    Codd’s 1970 paper is fairly readable, and this 1972 paper is related to the correspondences between the different approaches taken.