Szeregowalność jest poprawna, kiedy rezultat operacji je historii jest taki samy jako rezultat operacji historii sekwencyjną, a graf szeregowalności jest grafem acyklicznym.
Zgodnie z powyższą definicją, sekwencję operacji jest wyznaczona na podstawie kolejności konfliktowych operacji występujących w historii przetwarzania H. Do badania poprawności historii przetwarzania wykorzystuje się analizę grafów szeregowalności.