article

Free access

Equivalences Among Relational Expressions with the Union and Difference Operators

Authors:

Yehoshua Sagiv,

Mihalis YannakakisAuthors Info & Claims

Journal of the ACM (JACM), Volume 27, Issue 4

Pages 633 - 655

https://doi.org/10.1145/322217.322221

Published: 01 October 1980 Publication History

PDF eReader

References

[1]

AHO, A V, BEERI, C, AND ULLMAN, J D The theory of joins m relational databases A CM Trans Database Syst 4, 3 (Sept 1979), 297-314

Crossref

Google Scholar

[2]

AHO A,V, HOPCROFT, J.E, AND ULLMAN, J D The Destgn and Analysts of Computer Algorahms Addison- Wesley, Reading, Mass, 1974

Crossref

Google Scholar

[3]

AHO, A V, SAGIV, Y, SZVMANSKI, T G, AND ULI MAN, J D inferring a tree from lowest common ancestors with an apphcatlon to the optimlzatmn of relatmnal expressions Proc 16th Ann Allerton Conf on Commumcauon, Control and Computing, Monticello, I11,85Oct 1978, pp 54-63

Google Scholar

[4]

AHO, A V, SAGIV, Y, AND ULLMAN, J D Equivalences among relational expressions SlAM J Comput 8, 2 (1979), 218-246

Google Scholar

[5]

AHO, A V, SAOW, Y, ANt) ULLMAN, J D Efficient optimization of a class of relational expressions A CM Trans Database Syst 4, 4 (Dec 1979), 435-454

Crossref

Google Scholar

[6]

Aao, A V, SETHI, R, AND ULLMAN, J.D Code opumtzation and finite Church-Rosser systems In Design and Opnmlzatwn of Compders, R Rustm, Ed, Prentice Hall, Englewood Cliffs, N J, 1972, pp 89-105

Google Scholar

[7]

ARMSTRONG, W W Dependency structures of data base relationship Proc IFIP 74, North Holland, New York, 1974, pp 580-583

Google Scholar

[8]

BEERI, C, FAGIN, R, AND HOWARD, J H A complete axlomaUzaUon for functional and multwalued dependencies. Proc ACM-SIGMOD Intern. Conf on the Management of Data, Toronto, Ontario, Canada, August 1977, pp 47-61.

Crossref

Google Scholar

[9]

CHANDRA, A K, AND MERLIN, P M Optimal implementation of conjunctive queries in relational data bases Proc 9th Ann ACM Syrup on Theory of Computing, Boulder, Colo, May 1977, pp 77-90

Crossref

Google Scholar

[10]

CODD, E F A relational model of data for large shared data banks, Commun A CM 13, 6 (June 1970), 377- 387

Crossref

Google Scholar

[11]

CODD, E F Relational completeness of data base sublanguages. In Data Base Systems, R Rustm, Ed, Prentice Hall, Englewood Cliffs, N J, 1972, pp 65-98

Google Scholar

[12]

EVEN, S,ITAI, A, AND SHAMIR, A On the complexRy of timetable and mulucommodlty flow problems SIA M J Comput 5, 4 (1976), pp 691-703

Google Scholar

[13]

GARE~, M R, AND JOHNSON, D S Computers and lntractabdtty A Grade to the Theory of NP-Completeness Freeman, San Francisco, 1978

Crossref

Google Scholar

[14]

GAVRIL,F Testing for equahty between maximum matching and minimum node covenng, Inform Proc Left 6, 6 (1977), 199-202

Google Scholar

[15]

HALL, PAV Optimization of a single relational expression m a relauonal database system IBM J Res Dev 20, 3 (1976), 244-257

Google Scholar

[16]

KARP, R M Reduobdtty among combinatorial problems in Complexity of Computer Computatwns, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103

Google Scholar

[17]

MINKER, J Performing inferences over relational databases Pro~. ACM-SIGMOD Intern Conf on the Management of Data, San Jose, Cahf, May 1975, pp 79-91

Crossref

Google Scholar

[18]

PALERMO, FP A database search problem In lnformatwn Systems COINS IV, J T Tou, Ed, Plenum Press, New York, 1974

Google Scholar

[19]

PECHERER, R M Efficient evaluation of expressions m a relational algebra Proc. ACM Pacific Conf, San Francisco, Cahf, Aprd 1975, pp 44--49

Google Scholar

[20]

SAGIV, Y Optimization of queries m relauonal databases Ph D Thes~s, Dept of Electrical Engineering and Computer Science, Prmceton Umvers~ty, Princeton. N J, August 1978

Crossref

Google Scholar

[21]

SMITH, J M, AND CHANG, P Y-T OpUmtzmg the performance of a relational algebra database interface Commun ACM 18, 10 (Oct 1975), 568-579

Crossref

Google Scholar

[22]

STOCKMEYFR, L J The polynomlal-ttme hierarchy Theor Comput Sct 3, I (1976), 1-22

Google Scholar

[23]

WONG, E, AND YOUSSEFI, K Decomposmon--a strategy for query processing A CM Trans Database Syst 1, 3 (Sept 1976), 223-241

Crossref

Google Scholar

[24]

WRATHALL, C Complete sets and the polynomial-time hierarchy Theor Comp Sct 3, i (1976), 23-33

Google Scholar

[25]

YANNAKAKIS, M Unpubhshed manuscript

Google Scholar

Cited By

View all

Hu YGilad AStephens-Martinez KRoy SYang J(2024)Qr-Hint: Actionable Hints Towards Correcting Wrong SQL QueriesProceedings of the ACM on Management of Data10.1145/36549952:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654995
Marcinkowski JOrda M(2024)Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.Proceedings of the ACM on Management of Data10.1145/36516042:2(1-24)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651604
Cima GConsole MLenzerini MPoggi A(2023)A review of data abstractionFrontiers in Artificial Intelligence10.3389/frai.2023.10857546Online publication date: 23-Jun-2023
https://doi.org/10.3389/frai.2023.1085754
Show More Cited By

Index Terms

Equivalences Among Relational Expressions with the Union and Difference Operators
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Relational database model
    2. Query languages
      1. Relational database query languages
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

Equivalence among relational expressions with the union and difference operation
VLDB '78: Proceedings of the fourth international conference on Very Large Data Bases - Volume 4

A generalization of tableaux as a method for representing queries in relational databases, called sets of tableaux, is proposed. Every relational expression with the operators select, project, join and union can be represented by a set of tableaux. This ...
Equivalences among Relational Expressions

Many database queries can be formulated in terms of expressions whose operands represent tables of information (relations) and whose operators are the relational operations select, project, and join. This paper studies the equivalence problem for these ...
Difference operators on fuzzy sets
Abstract
Based on the properties of the difference operator on crisp sets, a fuzzy difference operator in fuzzy logic is defined as a continuous binary operator on the closed unit interval with some boundary conditions. In this paper, the structures and ...
Highlights
- The difference operator in the Boolean logic is extended to the fuzzy setting.
- Using the axiomatic and model theoretic approaches, the generalizations of classical tautologies are obtained.
- The relationship between the fuzzy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 27, Issue 4

Oct. 1980

251 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322217

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1980

Published in JACM Volume 27, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

336
Total Citations
View Citations
1,892
Total Downloads

Downloads (Last 12 months)269
Downloads (Last 6 weeks)45

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hu YGilad AStephens-Martinez KRoy SYang J(2024)Qr-Hint: Actionable Hints Towards Correcting Wrong SQL QueriesProceedings of the ACM on Management of Data10.1145/36549952:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654995
Marcinkowski JOrda M(2024)Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.Proceedings of the ACM on Management of Data10.1145/36516042:2(1-24)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651604
Cima GConsole MLenzerini MPoggi A(2023)A review of data abstractionFrontiers in Artificial Intelligence10.3389/frai.2023.10857546Online publication date: 23-Jun-2023
https://doi.org/10.3389/frai.2023.1085754
Ding HWang ZYang YZhang DXu ZChen HPiskac RLi J(2023)Proving Query Equivalence Using Linear Integer ArithmeticProceedings of the ACM on Management of Data10.1145/36267681:4(1-26)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626768
Bonchi FDi Giorgio ASantamaria A(2023)Deconstructing the Calculus of Relations with Tape DiagramsProceedings of the ACM on Programming Languages10.1145/35712577:POPL(1864-1894)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571257
Zhu DFan SZeng XXi RHou M(2023)Graph-Attention-Network-Based Cost Estimation Model in Materialized View Environment2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00198(1388-1396)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00198
Spasić MVujošević Janičić M(2023)Solving the SPARQL query containment problem with SpeCSWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2022.10077076:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.websem.2022.100770
Cima GPoggi ALenzerini M(2023)The notion of Abstraction in Ontology-based Data ManagementArtificial Intelligence10.1016/j.artint.2023.103976323(103976)Online publication date: Oct-2023
https://doi.org/10.1016/j.artint.2023.103976
Ioannidis Y(2023)A time bound on the materialization of some recursively defined viewsAlgorithmica10.1007/BF018404521:1-4(361-385)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840452
Salas JHogan A(2022)Semantics and canonicalisation of SPARQL 1.1Semantic Web10.3233/SW-21287113:5(829-893)Online publication date: 18-Aug-2022
https://doi.org/10.3233/SW-212871
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Equivalence among relational expressions with the union and difference operation