Order dependency in the relational model (Q1069711)

Most relational theory ignores the structure of the domains over which attributes range. In this study, the authors consider partial and total orders on domains and then analyze the data dependencies that are then expressible, which are called order dependencies. Order dependencies formalize properties of data such as ''check numbers increase with time'' or ''if student 1 does better than student 2 on the final exam, and all other scores are equal, then student 1's grade is no lower than that of student 2.'' The first section concentrates on satisfaction of order dependencies by pairs of tuples and by relations, and characterizes when a set of order dependencies can be satisfied by a non-empty relation. Section 2 introduces comparators, similar to agreements for functional dependency, that abstract the essential properties of a pair of tuples as regards a particular order dependency. The collection of comparators for a set of order dependencies \(\Gamma\), denoted \({\mathcal C}(\Gamma)\), captures all the information about satisfaction of \(\Gamma\), while being unaffected by changes to \(\Gamma\) that preserve logical equivalence. Comparators are used to show the existence of a set of dependencies \(\Gamma\) that has no Armstrong relation (a relation satisfying \(\Gamma\) and all implied dependencies, but no others) and to give sufficient conditions for an Armstrong relation to exist. Section 3 casts order dependencies as order formulas, which resemble propositional formulas. Converting an order formula for a set of dependencies \(\Gamma\) to a normal form, and adjoining information about attribute orders yields an order formula \(\Omega\) in disjunctive normal form. \(\Omega\) provides a syntactic characterization of \({\mathcal C}(\Gamma)\), which is used in an exponential-time algorithm to compute implication of order dependencies. Complexity results in section 5 show the problem is co-NP-complete, so the complexity of the algorithm is probably optimal. The authors give a polynomial-time version of the algorithm for a restricted class of order dependencies. Section 4 presents a sound and complete collection of inference rules for order dependencies. The proof of completeness is rather creative, although complex. The proof links deductions using the inference rules with derivations in a particular context-free grammar. The language generates a terminal string whenever a logical implication holds, and the existence of the string shows the implication is derivable with the inference rules.