The paper explores the serializability of concurrent database updates, showing that determining whether a sequence of transactions is serializable is an NP-complete problem. It introduces several efficiently recognizable subclasses of serializable histories, including DSR and Q, which are based on different serializability principles. The paper also proposes two new principles, DSR and Q, that generalize existing ones. It demonstrates that certain classes of histories can be efficiently scheduled, while others cannot. The results are extended to more general transaction models, including those with interpreted functions and distributed databases. The paper concludes that efficient schedulers for serializable histories exist only if the class of histories is efficiently recognizable and satisfies certain regularity conditions. The complexity of recognizing serializable histories is shown to be closely related to the practical question of whether efficient schedulers exist for a given class of histories. The paper also discusses the implications of these results for the design of concurrent database systems and the development of efficient concurrency control mechanisms.The paper explores the serializability of concurrent database updates, showing that determining whether a sequence of transactions is serializable is an NP-complete problem. It introduces several efficiently recognizable subclasses of serializable histories, including DSR and Q, which are based on different serializability principles. The paper also proposes two new principles, DSR and Q, that generalize existing ones. It demonstrates that certain classes of histories can be efficiently scheduled, while others cannot. The results are extended to more general transaction models, including those with interpreted functions and distributed databases. The paper concludes that efficient schedulers for serializable histories exist only if the class of histories is efficiently recognizable and satisfies certain regularity conditions. The complexity of recognizing serializable histories is shown to be closely related to the practical question of whether efficient schedulers exist for a given class of histories. The paper also discusses the implications of these results for the design of concurrent database systems and the development of efficient concurrency control mechanisms.