Tuple sequences and lexicographic indexes

ABSTRACT

The concept of a tuple sequence is introduced in order to investigate structure connected with relational model implementation. Analogs are presented for the relational operations of projection, join, and selection, and the decomposition problem for tuple sequences is considered. The lexicographical ordering of tuple sequences is studied via the notion of (lexicographic) index. A sound and complete set of inference rules for indexes is exhibited, and two algorithmic questions related to indexes examined. Finally, indexes and functional dependencies in combination are studied.

REFERENCES

• 1: ARMSTRONG, W.W. Dependency structures of database relationships. In Proceedings oflFIP 74. North Holland, New York, 1974, pp. 580-583.
• 2: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 3: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 4: Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588132]
• 5: FAGIN, R. Functional dependencies in a relational database and propositional logic. IBM J. Res. Dev. 21 (1977), 534-544.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 8: KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Applications, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 1972, pp. 85-104.
• 9: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 10: Michael Stonebraker , Joseph Kalash, TIMBER: A Sophisticated Relation Browser (Invited Paper), Proceedings of the 8th International Conference on Very Large Data Bases, p.1-10, September 08-10, 1982
• 11: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 12: YANNAKAKIS, M., AND PAPADIMITRIOU, C.H. Algebraic dependencies. J Comput. Syst. Sci. 25 (1982), 2-41.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Design, Management, Performance, Theory, Verification