Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
2012 Technical Reports

The Complexity of Order Dependency Inference

Jaroslaw Szlichta, Parke Godfrey, Jarek Gryz and Calisto Zuzarte

Technical Report CSE-2012-05

York University

August 27 2012


Dependencies play an important role in database theory. We studyorder dependencies (ODs), and unidirectional order dependencies(UODs), sub-class of ODs, which describe the relationships amonglexicographical orderings of sets of tuples. We investigate theinference problem for order dependencies. We establish the following:(i) a sound and complete chase procedure for ODs for testing logicalimplication demonstrating its decidability, but prove the undecidabilityof the inference problem for ODs with inclusion dependencies; (ii)a proof of co-NP-completeness for the inference problem for thesubclass of UODs; (iii) a proof of co-NP-completeness for theinference problem of functional dependencies (FDs) from ODs ingeneral, but demonstrate linear time complexity for the inferenceof FDs from UODs; and (iv) a sound and complete inference algorithmfor sets of UODs over a natural domain.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.