Checkpointing of operations on data may be provided by partitioning the data into temporal segments. Operations may be performed on the temporal segments and checkpoints may be established by storing a persistent indication of the segment being processed. The entire processing state need not be saved. If a failure occurs, processing can be restarted using the saved indication of the segment to be processed. Such data partitioning and checkpointing may be applied to relational databases, databases with dataflow operation and/or parallelism and other database types with or without parallel operation.