Serge Abiteboul
Abstract
An algebraic foundation of database schema design is presented. A new database operator, namely, disaggregation, is introduced. Beginning with “free” families, repeated applications of disaggregation and three other operators (matching function, Cartesian product, and selection) yield families of increasingly elaborate structure. In particular, families defined by one join dependency and several “embedded” functional dependencies can be obtained in this manner.
- 1 ABITEBOUL, S.Matching functions and disaggregations in databases. Ph.D. Dissertation, June 1982. Google Scholar
- 2 ARMSTRONG, W. W.Dependency structures of database relationships. In Proceedings IFIP 74, North Holland, Amsterdam, 1974, pp. 580-583.Google Scholar
- 3 BEERI, C., BERNSTEIN, P. A., AND GOODMAN, N.A sophisticate's introduction to database normalization theory. In Proceedings of the 4th International Conference on Very Large Databases, (1978), pp. 113-124.Google Scholar
- 4 CHANDRA, A. K., AND HAREL, D.Structure and complexity of relational queries. In Conference Record of the 21st IEEE Symposium on the Foundation of Computer Science (Syracuse, N.Y., Oct.). IEEE, New York, 1980, pp. 333-347.Google Scholar
- 5 CHANDRA, A. K., AND MERLIN, P. M.Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th Annual A CM Symposium on Theory of Computing (Boulder, Colo., May). ACM, New York, 1977, pp. 77-90. Google Scholar
- 6 CODD, E. F. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387. Google Scholar
- 7 CODD, E.F.Extending the database relational model to capture more meaning. ACM Trans. Database Syst. 4, 4 (Dec. 1980), 397-434. Google Scholar
- 8 FAGIN, R.Horn clauses and database dependencies. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (Los Angeles, Calif., May). ACM, New York, 1980, pp. 123- 134. Google Scholar
- 9 FAGIN, R., MENDELZON, A. O., AND ULLMAN, J. D.A simplified universal relation assumption and its properties. Tech. Rep. RJ 2900, IBM Research Lab., San Jose, Calif., 1980.Google Scholar
- 10 GINSBURG, S., AND ZAIDAN, S. M.Properties of functional dependency families. J. ACM 29, 3 (July 1982), 678-698. Google Scholar
- 11 HULL, R.lmplicational dependency and finite specification. Tech. Rep., Univ. of Southern California, Los Angeles, Calif., 1981.Google Scholar
- 12 JANSSENS, W. H., AND PAREDAENS, J.General dependencies. Workshop on Formal Bases for Data Bases (Toulouse, France, Dec. 1979).Google Scholar
- 13 MAIER, D., MENDELZON, A. O., AND SAGIV, Y.Testing implications of data dependencies. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 455-469. Google Scholar
- 14 SMITH, J. M., AND SMITH, D. C. P.Database abstraction, aggregation, and generalization. A CM Trans. Database Syst. 2, 2 (June 1977), 105-133. Google Scholar
- 15 YANNAKAKIS, M., AND PAPADIMITRIOU, C.Algebraic dependencies. In Conference Record of the 21st IEEE Symposium on Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE, New York, 1980, pp. 328-332.Google Scholar
Index Terms
- Disaggregations in databases
Recommendations
An Extended Algebra for Constraint Databases
Constraint relational databases use constraints to both model and query data. A constraint relation contains a finite set of generalized tuples. Each generalized tuple is represented by a conjunction of constraints on a given logical theory and, ...
Semantic sampling of existing databases through informative Armstrong databases
Functional dependencies (FDs) and inclusion dependencies (INDs) convey most of data semantics in relational databases and are very useful in practice since they generalize keys and foreign keys. Nevertheless, FDs and INDs are often not available, ...
Reviews
Robert J. Tufts
The primary purpose of this moderately sized paper is to show that an algebraic approach can be used to study extensions to the relational database model and to database schema design. To do this, the paper presents a rigorous treatment of relational algebra fundamentals and then extends these into aggregations, disaggregations, matching functions, partition mappings, and constraint-free schemas. The paper concludes with a strong discussion of a bottom-up approach to schema design. The paper itself is well written and highly mathematical. It has a minimum of typographical errors (I found two), and they do not detract from the discussion. The references are few but include some classical papers on relational algebra theory. The authors do succeed in presenting a theoretic foundation for a constructive database design. The main drawback of the paper is a result of its technical rigor: It is not easily understood by the casual reader. In fact, even seasoned database professionals are advised to brush up on relational database design algorithms before tackling it (one possible reference is shown below [1]). As such, I would recommend the paper only to those pursuing theoretical algebraic extensions to the relational model.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments