A procedure for detecting a reordering requirement in a directed record stream during query execution in a relational database processing system. The query compiler component of a relational database processing system includes procedures for building query execution plans (QEPs) for evaluation preparatory to selecting an optimal plan for execution. These plans are constructed from the bottom up using an internal graphical representation for the user query that has a number of relation nodes interconnected by directed record streams (data flows). A relational operation within each node imposes an "order requirement" on the outflow stream represented by an order requirement vector O.sub.R. The records within each directed record stream have an "order property" represented by an order property vector O.sub.P. Order detection occurs when these two vectors are compared to determine whether the order property satisfies the order requirement. Order detection by normalization (ODN) according to this invention first normalizes the two order specification vectors to remove all attributes made redundant by the effects of predicates and functional dependencies. Query execution plans constructed using ODN are found to execute an order of magnitude faster than those constructed using order detection without normalization.