Computational Complexity of Sorting and Joining Relations with Duplicates.

@article{DBLP:journals/tkde/AbdelguerfiS91,
  author    = {Mahdi Abdelguerfi and
               Arun K. Sood},
  title     = {Computational Complexity of Sorting and Joining Relations with
               Duplicates},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {3},
  number    = {4},
  year      = {1991},
  pages     = {496-503},
  ee        = {db/journals/tkde/AbdelguerfiS91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1991 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Mahdi Abdelguerfi: Special Function Unit for Statistical Aggregation Functions. IWDM 1989: 187-201 BibTeX

[2]

Mahdi Abdelguerfi, Arun K. Sood: A Bus Connected Cellular Array Processing Unit for relational Database Machines. IWDM 1987: 188-201 BibTeX

[3]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX

[4]

Morton M. Astrahan, Mario Schkolnick, Kyu-Young Whang: Approximating the number of unique values of an attribute without sorting. Inf. Syst. 12(1): 11-15(1987) BibTeX

[5]

Dina Bitton, David J. DeWitt: Duplicate Record Elimination in Large Data Files. ACM Trans. Database Syst. 8(2): 255-265(1983) BibTeX

[6]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[7]

David P. Dobkin, J. Ian Munro: Determining the Mode. Theor. Comput. Sci. 12: 255-263(1980) BibTeX

[8]

Margaret H. Eich: Main Memory Database Research Directions. IWDM 1989: 251-268 BibTeX

[9]

Philippe Flajolet, G. Nigel Martin: Probabilistic Counting Algorithms for Data Base Applications. J. Comput. Syst. Sci. 31(2): 182-209(1985) BibTeX

[10]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[11]

Ming-Yee Lai, Tony T. Lee: Protocol Verification Using Relational Database Systems. ICDE 1987: 347-354 BibTeX

[12]

Tony T. Lee, Ming-Yee Lai: A Relational Algebraic Approach to Protocol Verification. IEEE Trans. Software Eng. 14(2): 184-193(1988) BibTeX

[13]

Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250 BibTeX

[14]

H. T. Kung, Philip L. Lehman: Systolic (VLSI) Arrays for Relational Database Operations. SIGMOD Conference 1980: 105-116 BibTeX

[15]

...

[16]

Koheil Noshita: Predicting the Number of Distinct Elements in a Multiset. SIAM J. Comput. 11(4): 611-619(1982) BibTeX

[17]

...

[18]

Larry J. Stockmeyer, C. K. Wong: On the Number of Comparisons to Find the Intersection of Two Relations. SIAM J. Comput. 8(3): 388-404(1979) BibTeX