The real-world knowledge management applications require features such as versioning and fine-grained access control. Each of them raises the issue of tracking the changes in a knowledge base. Important part of the research presented is the definition of a formal model for tracking changes in graph-based data models. It was used in the ontology middleware module developed under the On-To-Knowledge project as an extension of the Sesame RDF(S) repository. This paper is further development of the results reported in [5].