The book constitutes the joint refereed proceedings of the 9th International Conference on Relational Methods in Computer Science, RelMiCS 2006, and the 4th International Workshop on Applications of Kleene Algebras, AKA 2006, held in Manchester, UK in August/September 2006.The 25 revised full papers presented together with 2 invited papers and the abstract of an invited talk were carefully reviewed and selected from 44 submissions. The papers are devoted to the theory of relation algebras, Kleene algebras, and related formalisms as well as to their diverse applications in software engineering, databases, and artificial intelligence; a special focus is on formal methods, logics of programs, and links to neighbouring disciplines.