Abstract
Database schema design is seen as to decide on formats for time-varying instances, on rules for supporting inferences and on semantic constraints. Schema design aims at both faithful formalization of the application and optimization at design time. It is guided by four heuristics: Separation of Aspects, Separation of Specializations, Inferential Completeness and Unique Flavor. A theory of schema design is to investigate these heuristics and to provide insight into how syntactic properties of schemas are related to worthwhile semantic properties, how desirable syntactic properties can be decided or achieved algorithmically, and how the syntactic properties determine costs of storage, queries and updates. Some well-known achievements of design theory for relational databases are reviewed: normal forms, view support, deciding implications of semantic constraints, acyclicity, design algorithms removing forbidden substructures.
Preview
Unable to display preview. Download preview PDF.
References
P. Atzeni, G. Ausiello, C. Batini, and M. Moscarini. Inclusion and equivalence between relational database schemata. Theoretical Computer Science, 19:267–285, 1982.
P. Atzeni and V. De Antonellis.Relational Database Theory. Benjamin/Cummings, Redwood City, CA, 1993.
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, Reading, MA, 1995.
P. Atzeni and N. M. Morfuni. Functional dependencies and constraints on null values in database relations. Information and Control, 70(1):1–31, 1986.
W. W. Armstrong. Dependency structures of data base relationships. In J. L. Rosenfeld, editor, Proceedings of IFIP Congress 1971, pages 580–583. North-Holland, Amsterdam, 1974.
C. Beeri and P.A. Bernstein.Computational problems related to the design of normal form relational schemas. ACM Transactions on Database Systems, 4(1):30–59, 1979.
J. Biskup and H. H. Briiggemann. Universal relation views: A pragmatic approach. In Proceedings of the 9th International Conference on Very Large Data Bases, pages 172–185, 1983.
C. Beeri, P. A. Bernstein, and N. Goodman. A sophisticated introduction to database normalization theory. In Proceedings of the 4th International Conference on Very Large Data Bases, Berlin, pages 113–124, September 1978.
C. Beeri, P. A. Bernstein, and N. Goodman. A sophisticated introduction to database normalization theory. In Proceedings of the 4th International Conference on Very Large Data Bases, Berlin, pages 113–124, September 1978.
J. Biskup, H. H. Brüggemann, L. Schnetgöke, and M. Kramer. One flavor assumption and γ-acyclicity for universal relation views. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 148–159, 1986.
J. Biskup and B. Convent. A formal view integration method. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington, pages 398–407, 1986.
J. Biskup and B. Convent. Towards a schema design methodology for deductive databases. In J. Demetrovics and B. Thalheim, editors, Proceedings of the Symposium on Mathematical Fundamentals of Database Systems (MFDBS '89), number 364 in Lecture Notes in Computer Science, pages 37–52. Springer, 1989.
J. Biskup and B. Convent. Relational chase procedures interpreted as resolution with paramodulation. Fundamenta Informatique, XV(2):123–138, 1991.
J. Biskup and P. Dublish. Objects in relational database schemes with functional, inclusion and exclusion dependencies. Informatique theorique et Applications / Theoretical Informatics and Applications, 27(3):183–219, 1993.
J. Biskup, U. Dayal, and P. A. Bernstein. Synthesizing independent database schemas. In P. A. Bernstein, editor, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD '79), Boston, pages 143–151, New York, NY, 1979. ACM.
J. Biskup, J. Demetrovics, L. O. Libkin, and I. B. Muchnik. On relational database schemes having unique minimal key. Journal of Information Processing and Cybernetics EIK, 27(4):217–225, 1991.
P. A. Bernstein. Synthesizing third normal form relations from functional dependencies. ACM Transactions on Database Systems, 1(4):272–298, December 1976.
C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. Journal of the ACM, 30:479–513, 1983.
P. A. Bernstein and N. Goodman. What does Boyce-Codd normal form do? In Proceedings of the 6th International Conference on Very Large Data Bases, pages 245–259, 1980.
J. Biskup. Inferences of multivalued dependencies in fixed and undetermined universes. Theoretical Computer Science, 10:93–105, 1980.
J. Biskup. Entwurf von Datenbankschemas durch schrittweises Umwandeln verbotener Teilstrukturen. In Tagungsband GI-EMISA-Fachgespräch Entwurf von Informationssystemen — Methoden und Modelle, Tutzing, pages 130–148, 1985.
J. Biskup. Boyce-Codd normal form and object normal forms. Information Processing Letters, 32(1):29–33, 1989.
J. Biskup.Impacts of creating, implementing and using formal languages. In K. Duncan and K. Krueger, editors, Proceedings of the 13th World Corrupter Congress 94, volume 3, pages 402–407. Elsevier (North-Holland), Amsterdam etc., 1994.
J. Biskup. Database schema design theory: achievements and challenges. In Proceedings of the 6th International Conference on Information Systems and Management of Data (CISMOD '95), number 1006 in Lecture Notes in Computer Science, pages 14–44, Bombay, 1995. Springer, Berlin etc.
J. Biskup. Grundlagen von Informationssystemen. Vieweg, Braunschweig-Wiesbaden, 1995.
C. Beeri and M. Kifer. An integrated approach to logical design of relational database schemes. ACM Transactions on Database Systems, 11(2):134–158, 1986.
J. Biskup and R. Meyer. Design of relational database schemes by deleting attributes in the canonical decomposition. Journal of Computer and System Sciences, 35(1):1–22, 1987.
J. Biskup and U. Räsch. The equivalence problem for relational database schemes. In Proceedings of the 1st Symposium on Mathematical Fundamentals of Database Systems, number 305 in Lecture Notes in Computer Science, pages 42–70. Springer-Verlag, Berlin etc., 1988.
F. Bancilhon and N. Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557–575, 1981.
C. Beeri and M. Y. Vardi. Formal systems for tuple and equality generating dependencies. SIAM Journal on Computing, 13(1):76–98, 1984.
C. Beeri and M. Y. Vardi.A proof procedure for data dependencies. Journal of the ACM, 31(4):718–741, October 1984.
V. Brosda and G. Vossen. Update and retrieval in a relational database through a universal schema interface. ACM Transactions on Database Systems, 13(1988):449–485, 1988.
M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. Journal of Computer and System Sciences, 28(1):29–59, 1984.
E. P. F. Chan. A design theory for solving the anomalies problem. SIAM Journal on Computing, 18(3):429–448, June 1989.
P. P.-S. Chen. The entity-relationship-model-towards a unified view of data. ACM Transactions on Database Systems, 1(1):9–36, March 1976.
E. P. F. Chan and A. O. Mendelzon. Independent and separable database schemes. SIAM Journal on Computing, 16(5):841–851, 1987.
E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377–387, June 1970.
E. F. Codd. Further normalization of the database relational model. In R. Rustin, editor, Database Systems, number 6 in Courant Institute Computer Science Symposia Series, pages 33–64. Prentice Hall, Englewood Cliffs, NJ, 1972.
A. K. Chandra and M. Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM Journal on Computing, 14(3):671–677, 1985.
U. Dayal and P. A. Bernstein. On the correct translation of update operations on relational views. ACM Transactions on Database Systems, 8(3):381–416, 1982.
C. Delobel. Normalization and hierarchical dependencies in the relational data model. ACM Transactions on Database Systems, 3:201–222, 1978.
C. J. Date and R. Fagin. Simple conditions for guaranteeing higher normal forms in relational databases. ACM Transactions on Database Systems, 17:465–476, 1992.
J. Demetrovics, G. O. H. Katona, D. Miklos, O. Seleznjew, and B. Thalheim. The average length of key and functional dependencies in (random) databases. In G. Gottlob and M. Y. Vardi, editors, Database Theory-ICDT '95, pages 266–279. Springer-Verlag, Berlin etc., 1995.
J. Demetrovics, L. Libkin, and I.B. Muchnik. Functional dependencies in relational databases: a lattice point of view. Discrete Applied Mathematics, 40:155–185, 1992.
A. D'Atri and M. Moscarini. Recognition algorithms and design methodologies for acyclic database. In P. C. Kanellakis and F. Preparata, editors, Advances in Computing Research, volume 3, pages 164–185. JAI Press, Inc., Greenwich, CT, 1986.
P. DeBra and J. Paredaens. Horizontal decompositions for handling exceptions to functional dependencies. In H. Gallaire, J. Minker, and J. M. Nicolas, editors, Advances in Database Theory, volume 2. Plenum, New, York-London, 1984.
R. Fagin. Multivalued dependencies and a new normal form for relay tional databases. ACM Transactions on Database Systems, 2(3):262–278, September 1977.
R. Fagin. A normal form for relational databases that is based on domains and keys. ACM Transactions on Database Systems, 6(3):387–415, 1981.
R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM, 30(3):514–550, July 1983.
A. L. Furtado and M. A. Casanova. Updating relational views. In W. Kim, D. S. Reiner, and D. S. Batory, editors, Query Processing in Database Systems. Springer-Verlag, Berlin, 1985.
R. Fagin and M. Y. Vardi. The theory of data dependencies — an overview. In Proceedings of the 11th International Colloquium on Automata, Languages and Programming, number 172 in Lecture Notes in Computer Science, pages 1–22. Springer-Verlag, Berlin etc., 1984.
J. Grant, J. Horty, J. Lobo, and J. Minker. View Updates in Stratified Disjunctive Databases. Journal of Automated Reasoning, 11:249–267, 1993.
M. H. Graham, A. O. Mendelzon, and M. Y. Vardi. Notions of dependency satisfaction. Journal of the ACM, 33(1):105–129, 1986.
M. H. Graham. On the universal relation. Systems research group report, University of Toronto, 1979. [Gra84] G. Grahne. Dependency satisfaction in databases with incomplete information. In U. Dayal, editor, Proceedings of the 10th International Conference on Very Large Data Bases, pages 37–45, Singapore, 1984.
H. J. Hernández and E. P. F. Chan. Constant-time-maintainable BCNF database schemes. ACM Transactions on Database Systems, 16(4):5710–599, December 1991.
S. J. Hegner. Unique complements and decompositions of database schemata. Journal of Computer and System Sciences, 48:9–57, 1994.
C. Herrmann. On the undecidability of implications between embedded multivalued dependencies. Information and Computation, 122:221–235, 1995.
P. Honeyman. Testing satisfaction of functional dependencies. Journal of the ACM, 29(3):668–677, 1982.
R. Hull.Relative information capacity of simple relational database schemata. SIAM Journal on Computing, 15(3):856–886, 1986.
J. H. Jou and P. C. Fischer. The complexity of recognizing 3NF relation schemes. Information Processing Letters, 14(4):187–190, 1982.
G. O. H. Katona. Combinatorial and algebraic results for database relations. In Database Theory-ICDT '92, number 646 in Lectures Notes in Computer Science, pages 1–20. Springer-Verlag, Berlin etc., 1992.
P. C. Kanellakis, S. S. Cosmadakis, and M. Y. Vardi. Unary inclusion dependencies have polynomial time inference problems. In Proceedings of the 15th Symposium on Theory of Computing, Boston, pages 246–277, 1983.
A. M. Keller. The role of semantics in translating view updates. IEEE Computer, 19(1):63–73, January 1986.
W. Kent. A simple guide to five normal forms in relational databases. Communications of the ACM, 26(2):120–125, 1983.
H. F. Korth, G. M. Kuper, J. Feigenbaum, A. VanGeldern, and J. D. Ullman. A database system based on the universal relation assumption. ACM Transactions on Database Systems, 9(1984):331–347, 1984.
P. Kandzia and M. Mangelmann. On covering Boyce-Codd normal forms. Information Processing Letters, 11:218–223, 1980.
M. Levene. The Nested Universal Relation Database Model. Lecture Notes in Computer Science 595. Springer, Berlin etc., 1992.
Y. E. Lien. Multivalued dependencies with nulls in relational databases. In Proceedings of the 5th International Conference on Very Large Data Bases, pages 61–66, 1979.
M. Levene and G. Loizou. The nested universal relation model. Journal of Computer and System Sciences, 49:683–717, 1994.
C. L. Lucchesi and S. L. Osborn. Candidate keys for relations. Journal of Computer and System Sciences, 17(2):270–279, 1978.
T. W. Ling, F. W. Tompa, and T. Kameda. An improved third normal form for relational databases. ACM Transactions on Database Systems, 6(2):329–346, 1981.
D. Maier. The Theory of Relational Databases. Computer Science Press, Rockville, MD, 1983.
A. O. Mendelzon. On axiomatizing multivalued dependencies in relational databases. Journal of the ACM, 26(1):37–44, 1979.
J. C. Mitchell. The implication problem for functional and inclusion dependencies. Information and Control, 56(3):154–173, 1983.
H. Mannila and K. J. Rädhä. On the relationship of minimum and optimum covers for a set of functional dependencies. Acta Informatioa, 20:143–158, 1983.
H. Mannila and K.-J. Räihä. Inclusion dependencies in database design. In Proceedings of the Second International Conference on Data Engineering, pages 713–718, Washington, DC, 1986. IEEE Computer Society Press.
H. Mannila and K.-J. Räihä. The Design of Relational Databases. Addison-Wesley, Wokingham, England, 1992.
D. Maier, J. D. Ullman, and M. Y. Vardi. On the foundations of the universal relation model. ACM Transactions on Database Systems, 9(2):283–308, June 1984.
S. L. Osborn. Normal Forms for Relational Data Bases. PhD thesis, Department of Computer Science, University of Waterloo, 1978.
J. Paredaens, P. DeBra, M. Gyssens, and D. van Gucht. The Structure of the Relational Database Model. Number 17 in EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1989.
J. Rissanen. Independent components of relations. ACM Transactions on Database Systems, 2(4):317–325, 1977.
J. Rissanen. On equivalence of database schemes. In Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 23–26, 1982.
Y. Sagiv. A characterization of globally consistent databases and their correct access paths. ACM Transactions on Database Systems, 8(2):266–286, 1983.
D. Seipel and D. Ruland. Designing gamma-acyclic database schemes using decomposition and augmentation techniques. In Proc. 1st Symposium on Mathematical Fundamentals of Database Systems, number 305 in Lec ture Notes in Computer Science, pages 197–209. Springer-Verlag, Berlin etc., 1988.
B. Thalheim. Dependencies in relational databases. Teubner, Stuttgart-Leipzig, 1991.
P. Thanisch, G. Loizou, and G. Jones. Succint database schemes. International Journal of Computer Mathematics, 33:55–69, 1990.
R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectivity reduce acyclic hypergraphs. SIAM Journal on Computing, 13:566–579, 1984.
J. D. Ullman. Principles of Database and Knowledge-Base Systems (Volume I). Computer Science Press, Rockville, MD, 1988.
J. D. Ullman. Principles of Database and Knowledge-Base Systems (Volume IL The New Technologies). Computer Science Press, Rockville, MD, 1989.
M. Y. Vardi. On decomposition of relational databases. In Proc. 23rd Symposium on Foundations of Computer Science, pages 176–185, 1982.
M. Y. Vardi. The implication and finite implication problem for typed template dependencies. Journal of Computer and System Sciences, 28:328, 1984.
M. Y. Vardi. Fundamentals of dependency theory. In E. Börger, editor, Trends in Theoretical Computer Science, pages 171–224. Computer Science Press, Rockville, 1988.
M. Y. Vardi. The universal-relation data model for logical independence. IEEE Software, 5(1988):80–85, 1988.
Y. Vassiliou.Null values in database management, a denotational semantics approach. In Proc. ACM SIGMOD Symp. on the Management of Data, pages 162–169, 1979.
G. Vossen. A new characterization of FD implication with an application to update anomalies. Information Processing Letters, 29(3):131–135, 1988.
G. Vossen. Data Models, Database Languages and Database Management Systems. Addison-Wesley, Wokingham, England, 1991.
M. W. Vincent and B. Srinivasan. A note on relation schemes which are in 3NF but not in BCNF. Information Processing Letters, 48:281–283, 1993.
M. W. Vincent and B. Srinivasan. Redundancy and the justification for fourth normal form in relational databases. International Journal of Foundations of Computer Science, 4:355–365, 1993.
C. T. Yu and Z. M. Özsoyoĝlu. An algorithm for tree-query membership of a distributed query. In Proceedings of the 3rd IEEE COMPSAC, Chicago, pages 306–312, 1979.
L.-Y. Yuan and Z. M. Özsoyoĝlu. Design of desirable relational database schemes. Journal of Computer and System Sciences, 45:435–470, 1992.
L.-Y. Yuan and Z. M. Özsoyoĝlu. Unifying functional and multivalued dependencies for relational database design. Information Science, 59:185–211, 1992.
C. Zaniolo. Analysis and design of relational schemata for database systems. PhD thesis, University of California Los Angeles, Computer Science Department, 1976. Technical Report UCLA-ENG-7669, July 1976.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Biskup, J. (1998). Achievements of relational database schema design theory revisited. In: Thalheim, B., Libkin, L. (eds) Semantics in Databases. SiD 1995. Lecture Notes in Computer Science, vol 1358. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035004
Download citation
DOI: https://doi.org/10.1007/BFb0035004
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64199-5
Online ISBN: 978-3-540-69700-8
eBook Packages: Springer Book Archive