We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 4 Issue 2
April  1989
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Beng C. Ooi, B. Srinivasan. Properties of Semijoin Sequences[J]. Journal of Computer Science and Technology, 1989, 4(2): 106-115.
Citation: Beng C. Ooi, B. Srinivasan. Properties of Semijoin Sequences[J]. Journal of Computer Science and Technology, 1989, 4(2): 106-115.
shu

Properties of Semijoin Sequences

  • Department of Computer Science, Monash University, Clayton, Australia

More Information
  • Received Date: July 28, 1987
  • Revised Date: August 09, 1988
    Abstract
  • The problem of finding optimum semijoin sequence for an arbitrary query under linear cost function for the transmission cost is NP-hard. Hence heuristic algorithms with desirable properties are explored. In this paper four properties of semijoin programs for distributed query processing are identified. The use of these properties in constructing semijoin sequence is justified. An existing algorithm is modified incorporating these properties. Empirical comparison with existing algorithms shows the superiority of the proposed algorithm.
    • FullText(HTML)
    • References (16)
  • [1]
    Apers, P.M.G., Hevner, A.R. and Yao, S.B., Optimization algorithm for distributed queries, IEEE Trans. on Software Eng.,28:1 (1983), 57-68.
    [2]
    Bernstein, P.A. and Chiu, D.M., Using semijoin to solve relational queries, J. ACM,28:1 (1981), 25-40.
    [3]
    Black, P.A. and Luk, W.S., A New Heuristic for Generating Semijoin Programs for Distributed Query Processing, IEEE COMPSAC, 1982, 581-588.
    [4]
    Chung, C. W. and Irani, K.B., A Semijoin Strategy for Distributed Query Optimization, IEEE Int. Conf. on Distributed Computing System, 1984.
    [5]
    Codd, E.F., A relational model of data for large shared data banks, CACM,13:6 (1970), 377-389.
    [6]
    Hevner, A.R., Optimization of Query Processing in Distributed Databases, PhD Dissertation, Purdue University, Lafayette, Indiana, Sept., 1979.
    [7]
    Hevner, A.R. and Yao, S.B., Query Processing on a Distributed Database, Procs. 3rd Berkeley Workshop on Distributed Data Management and Comp. Networks, August, 1978.
    [8]
    Hevner, A.R. and Yao, S.B., Query processing in distributed database system, IEEE Trans on Soft. Eng., SE-5:3 (1979), 177-187.
    [9]
    Goodman, N. et al., Query Processing in SDD-1:A system for Distributed Databases, Tech. Rep. CCA-79-06. Computer Corporation of America, 1979.
    [10]
    Bernstein, P.A., Goodman, N., Wong, E., Reeve, C.L. and Rothnie, Jr. J.B., Query processing in a system for distributed databases (SDD-1), ACM TODS,6:4 (1981), 602-625.
    [11]
    Srinivasan, B., and Ooi, B.C., Optimal Properties of Semijoin Sequences for Distributed Query Processing, Technical Report, National University of Singapore, July, 1987.
    [12]
    Wong, E., Retrieving Dispersed Data from SDD-1:A System for Distributed Databases, Proc. 2nd Berkeley Workshop on Distributed Management and Computer Networks, May, 1977, 217-235.
    [13]
    Yao, S.B., Approximating block access in database organisation, CACM,20:4 (1977), 260-261.
    [14]
    Yu, C.T. and Chang, C.C., Distributed query processing, ACM Computing Surveys,16:4 (1984), 399-433.
    [15]
    Yu, C.T. and Chang, C.C., On the Design of a Query Processing Strategy in a Distributed Database Environment, Proc. ACM SIGMOD, 1983, 30-39.
    [16]
    Yu, C.T. and Ozsoyoglu, M.E., An Algorithm for Tree Query Membership of a Distributed Query, IEEE COMPSAC, 1979, 306-312.
    • Relative Articles

  • Related Articles

    [1]WANG Guoren, YU Ge. Performance Evaluation of a Parallel Cascade Semijoin Algorithm for Computing Path Expressions in Object Database Systems[J]. Journal of Computer Science and Technology, 2002, 17(2).
    [2]LIU Tian. Some Structural Properties of SAT[J]. Journal of Computer Science and Technology, 2000, 15(5): 439-444.
    [3]ZHAO Jianhua. Checking Timed Automata for Linear Duration Properties[J]. Journal of Computer Science and Technology, 2000, 15(5): 423-429.
    [4]GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most5[J]. Journal of Computer Science and Technology, 2000, 15(5): 416-422.
    [5]LIU Tian. Some Structural Properties of SAT[J]. Journal of Computer Science and Technology, 2000, 15(5).
    [6]FU maxi. Relative Properties of Frame Language[J]. Journal of Computer Science and Technology, 1999, 14(4): 320-327.
    [7]Colin Stirling. Playing Games and Proving Properties ofConcurrent Systems[J]. Journal of Computer Science and Technology, 1998, 13(6): 482.
    [8]Hu Shimin, Wang Guojin, Sun Jiaguang. A Type of Triangular Ball Surface and its Properties[J]. Journal of Computer Science and Technology, 1998, 13(1): 63-72.
    [9]Sun Jigui, Cheng Xiaochun, Liu Xuhua. The Global Properties of Valid Formulas in Modal Logic K[J]. Journal of Computer Science and Technology, 1996, 11(6): 615-621.
    [10]Zhu Hong. Some Mathematical Properties of the Functional Programming Language FP[J]. Journal of Computer Science and Technology, 1987, 2(3): 202-216.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (13) PDF downloads (1) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return