Article

Free access

Can we use the universal instance assumption without using nulls?

Author:

Yehoshua SagivAuthors Info & Claims

SIGMOD '81: Proceedings of the 1981 ACM SIGMOD international conference on Management of data

Pages 108 - 120

https://doi.org/10.1145/582318.582336

Published: 29 April 1981 Publication History

Abstract

We claim that the representative instance of [Ho1, Va3] is a correct representation of the data stored in a database even when the relations of the database are not the projections of a single universal instance. If no constraint (other than functional and join dependencies) is imposed on the data, then projections of the representative instance cannot always be computed by lossless joins. We show that if the database satisfies a modified foreign-key constraint, then projections of the representative instance can be computed by performing the union of several lossless joins. A class of relation schemes for which no constraint is necessary is characterized, and we show how to compute projections of the representative instance for databases that belong to this class.

References

[1]

{ABU} Aho, A. V., C. Beeri, and J. D. Ullman, "The Theory of Joins in Relational Databases," ACM Trans. on Database Systems, Vol. 4, No. 3 (Sept. 1979), pp. 297--314.

Digital Library

[2]

{ASU1} Aho, A. V., Y. Sagiv, and J. D. Ullman, "Equivalences Among Relational Expressions," SIAM J. Computing, Vol. 8, No. 2 (May 1979), pp. 218--246.

Digital Library

[3]

{ASU2} Aho, A. V., Y. Sagiv, and J. D. Ullman, "Efficient Optimization of a Class of Relational Expressions," ACM Trans. on Database Systems, Vol. 4, No. 4 (Dec. 1979), pp. 435--454.

Digital Library

[4]

{Arm} Armstrong, W. W., "Dependency Structures of Database Relationships," Proc. IFIP 74, North Holland, 1974, pp. 580--583.

[5]

{BB} Beeri, C. and P. A. Bernstein, "Computational Problems Related to the Design of Normal Form Relational Schemas," ACM Trans. on Database Systems, Vol. 4, No. 1 (March 1979), pp. 30--59.

Digital Library

[6]

{Ber} Bernstein, P. A., "Synthesizing Third Normal Form Relations from Functional Dependencies," ACM Trans. on Database Systems, Vol. 1, No. 4 (Dec. 1976), pp. 277--298.

Digital Library

[7]

{BFH} Beeri, C., R. Fagin, and J. H. Howard, "A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations," Proc. ACM-SIGMOD Int. Conf. on Management of Data, Toronto, Aug. 1977, pp. 47--61.

Digital Library

[8]

{BMSU} Beeri, C., A. O. Mendelzon, Y. Sagiv, and J. D. Ullman, "Equivalence of Relational Database Schemes," Proc. 11th Annual ACM Symp. on Theory of Computing, pp. 319--329, 1979.

Digital Library

[9]

{BG} Bernstein, P. A., and N. Goodman, "What Does Boyce-Codd Normal Form Do?," Proc. Int. Conf. on Very Large Data Bases, 1980, pp. 245--259.

[10]

{BDB} Biskup, J., U. Dayal, and P. A. Bernstein, "Synthesizing Independent Database Schemas," Proc. ACM-SIGMOD Int. Conf. on Management of Data, 1979, pp. 143--151.

Digital Library

[11]

{C1} Codd, E. F., "A Relational Model for Large Shared Data Banks," Comm. ACM, Vol. 13, No. 6 (June 1970), pp. 377--387.

Digital Library

[12]

{C2} Codd, E. F., "Extending the Database Relational Model to Capture More Meaning," ACM Trans. on Database Systems, Vol. 4, No. 4 (Dec. 1979), pp. 397--434.

Digital Library

[13]

{Fag} Fagin, R., "Multivalued Dependencies and a New Normal Form for Relational Databases," ACM Trans. on Database Systems, Vol. 2, No. 3 (Sept. 1977), pp. 262--278.

Digital Library

[14]

{FMU} Fagin, R., A. O. Mendelzon, and J. D. Ullman, "A Simplified Universal Relation Assumption and Its Properties," IBM research report, RJ2900, Nov., 1980.

[15]

{Ho1} Honeyman, P., "Testing Satisfaction of Functional Dependencies," Proc. XP1 Conf., Stonybrook, N. Y., June, 1980.

[16]

{Ho2} Honeyman, P., "Extension Joins," Proc. Int. Conf. on Very Large Data Bases, 1980, pp. 239--244.

[17]

{HLY} Honeyman, P., R. E. Ladner, and M. Yannakakis, "Testing the Universal Instance Assumption," Information Processing Letters, Vol. 10, No. 1 (Feb. 1980), pp. 14--19.

[18]

{Ko} Korth, H. F., "A Proposal for the SYSTEM/U Query Language," unpublished memorandum, Stanford University, Stanford, CA, 1980.

[19]

{KU} Korth, H. F. and J. D. Ullman, "System/U: a Database System Based on the Universal Relation Assumption," Proc. XP1 Conf., Stonybrook, N. Y., June, 1980.

[20]

{KS} Kuck, S. M., and Y. Sagiv, "A Universal Relation Interface for Network Schemas," in preparation.

[21]

{Li} Lien, Y. E., "Multivalued Dependencies With Null Values in Relational Databases," Proc. Int. Conf. on Very Large Data Bases, 1979.

[22]

{Ma} Maier, D., "Discarding the Universal Instance Assumption: Preliminary Results," Proc. XP1 Conf., Stonybrook, N. Y., June, 1980.

[23]

{MMS} Maier D., A. O. Mendelzon, and Y. Sagiv, "Testing Implications of Data Dependencies," ACM Trans. on Database Systems, Vol. 4, No. 4 (Dec. 1979), pp. 455--469.

Digital Library

[24]

{Ris} Rissanen, J., "Theory of Relations for Databases --- A Tutorial Survey," Proc. 7th Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 64, Springer-Verlag, 1978, pp. 536--551.

[25]

{Sag} Sagiv, Y., manuscript in preparation.

[26]

{Sc} Sciore, E., "The Universal Instance and Database Design," TR 271, Dept. of Elec. Eng. and Comp. Sci., Princeton University, Princeton, N. J., June, 1980.

Digital Library

[27]

{SmS} Smith, J. M. and C. P. smith, "Database Abstractions: Aggregation," CACM, Vol. 20, No. 6 (Jun. 1979), pp. 405--413.

Digital Library

[28]

{Va1} Vassiliou, Y., "Functional Dependencies and Incomplete Information," Proc. Int. Conf. on Very Large Data Bases, 1980, pp. 260--269.

[29]

{Va2} Vassiliou, Y. and F. H. Lochovsky, "DBMS Transaction Translation," Proc. COMPSAC 80, Oct., 1980.

[30]

{Va3} Vassiliou, Y., "A Formal Treatment of Imperfect Information in Database Management," Technical Report CSRG-123, University of Toronto, Nov., 1980.

[31]

{Za1} Zaniolo, C., "Analysis and Design of Relational Schemata for Database Systems," Tech. Rep. UCLA-ENG-7669, Dept. of Comp. Sci., UCLA, July 1976.

[32]

{Za2} Zaniolo, C., "Design of Relational Views Over Network Schemas," Proc. ACM-SIGMOD Int. Conf. on Management of Data, 1979, pp. 179--190.

Digital Library

Cited By

Sagiv Y(2013)A personal perspective on keyword search over data graphsProceedings of the 16th International Conference on Database Theory10.1145/2448496.2448500(21-32)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2448496.2448500
Niinimäki MNiemi T(2009)An ETL process for OLAP using RDF/OWL ontologiesJournal on Data Semantics XIII10.5555/2172259.2172263(97-119)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/2172259.2172263
Niinimäki MNiemi T(2009)An ETL Process for OLAP Using RDF/OWL OntologiesJournal on Data Semantics XIII10.1007/978-3-642-03098-7_4(97-119)Online publication date: 2009
https://doi.org/10.1007/978-3-642-03098-7_4
Show More Cited By

Can we use the universal instance assumption without using nulls?
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Query languages

Recommendations

On the Codd semantics of SQL nulls
Abstract
Theoretical models used in database research often have subtle differences with those occurring in practice. One particular mismatch that is usually neglected concerns the use of marked nulls to represent missing values in theoretical ...
Highlights
- SQL nulls are commonly interpreted as non-repeating marked nulls, but even simple queries may produce answers that break this interpretation.
A Formalization of SQL with Nulls
Abstract
SQL is the world’s most popular declarative language, forming the basis of the multi-billion-dollar database industry. Although SQL has been standardized, the full standard is based on ambiguous natural language rather than formal specification. ...
On lossless tranformation of databases schemes not necessarily satisfying universal instance assumption
PODS '84: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems

Given a multirelational database scheme and a relational mapping f transforming it, an important question is whether the resulting scheme is equivalent to the original one. This question was addressed in the literature with respect to those relational ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '81: Proceedings of the 1981 ACM SIGMOD international conference on Management of data

April 1981

237 pages

ISBN:0897910400

DOI:10.1145/582318

Conference Chair:
Toby J. Teorey
University of Michigan
,
Program Chair:
Y. Edmund Lien
Bell Laboratories

Copyright © 1981 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 April 1981

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
310
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)5

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sagiv Y(2013)A personal perspective on keyword search over data graphsProceedings of the 16th International Conference on Database Theory10.1145/2448496.2448500(21-32)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2448496.2448500
Niinimäki MNiemi T(2009)An ETL process for OLAP using RDF/OWL ontologiesJournal on Data Semantics XIII10.5555/2172259.2172263(97-119)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/2172259.2172263
Niinimäki MNiemi T(2009)An ETL Process for OLAP Using RDF/OWL OntologiesJournal on Data Semantics XIII10.1007/978-3-642-03098-7_4(97-119)Online publication date: 2009
https://doi.org/10.1007/978-3-642-03098-7_4
Tré GCaluwe RPrade H(2008)Null values in fuzzy databasesJournal of Intelligent Information Systems10.1007/s10844-006-0021-030:2(93-114)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1007/s10844-006-0021-0
Ito MKasami T(2007)Optimizing universal queries in relational databasesSystems and Computers in Japan10.1002/scj.469022030322:3(19-30)Online publication date: 21-Mar-2007
https://doi.org/10.1002/scj.4690220303
Chan EHernández H(2005)On the desirability of γ-acyclic BCNF database schemesICDT '8610.1007/3-540-17187-8_32(105-122)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-17187-8_32
Jajodia S(2005)Universal and representative instances using unmarked nullsFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-13883-8_83(367-378)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-13883-8_83
Fagin RVardi M(2005)The theory of data dependencies — An overviewAutomata, Languages and Programming10.1007/3-540-13345-3_1(1-22)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-13345-3_1
Cohen SKanza YSagiv Y(2002)Select-Project Queries over XML DocumentsNext Generation Information Technologies and Systems10.1007/3-540-45431-4_2(2-13)Online publication date: 21-Jun-2002
https://doi.org/10.1007/3-540-45431-4_2
Dyreson C(1997)A Bibliography on Uncertainty Management in Information SystemsUncertainty Management in Information Systems10.1007/978-1-4615-6245-0_15(413-458)Online publication date: 1997
https://doi.org/10.1007/978-1-4615-6245-0_15
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents