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.
, a krawędź 
oznacza, że 
i 
pochodzące 
i 
, gdzie 
, to taka historia nie jest poprawna oraz graf szeregowalności jest acyklicznym (niepoprawnym).