Ordered functional dependencies in relational databases

We extend the relational data model to incorporate linear orderings into da ta domains, which we call the ordered relational model. The conventional Fu nctional Dependencies (FDs) are examined in the context of ordered relation al databases by using the notion of System Ordering Independence (SOI), whi ch refers to the desirable scenario that the ordering of tuples in a relati on is independent of the implementation of the underlying DBMS. We also ext end Armstrong's axiom system for FDs to object relations, which are a subcl ass of ordered relations that allow us to view tuples as objects. We formal ly define Ordered Functional Dependencies (OFDs) for the extended model by means of two possible extensions of domains, pointwise-orderings and lexico graphical orderings. We first present a sound and complete axiom system for OFDs in the case of pointwise-orderings and then establish a sound and com plete set of chase rules for OFDs in the case of lexicographical orderings. Our main result shows that the implication problems for both cases of OFDs are decidable, and that it is linear time for the case of pointwise-orderi ngs. (C) 1999 Elsevier Science Ltd. All rights reserved.