본문 바로가기
KERD
논문KCI 등재

분산 데이타베이스에서의 질의실행시간 최소화를 위한 유전자알고리즘: 총 시간 대 반응시간

A Genetic Algorithm for Minimizing Query Processing Time in Distributed Database Design: Total Time Versus Response Time

송석규
한국정보처리학회|2009.06|정보처리학회논문지D (The KIPS Transactions : Part D)|제16권 제3호|pp. 295-306

0

조회

0

다운로드

0

인용

0

참고문헌

키워드

유전자알고리즘Genetic AlgorithmsQuery Optimization분산 데이타베이스질의최적화하부질의 할당질의실행계획Distributed DatabasesSub-Query AllocationQuery Execution Plans
주제분류공학

초록

질의실행시간최소화는 분산 데이타베이스 설계에 있어 가장 중요한 목적중의 하나이다. 총시간최소화는 온라인거래처리시스템의 목적인 반면, 반응시간최소화는 의사결정지원 질의시스템의 목적이다. 본 논문에서는 질의실행시간최소화를 달성하기 위해 질의를 세분화하여 최적의 데이터베이스 사이트에 할당하는 분석모델을 개발하였으며, 문제해결방법으로 유전자알고리즘을 채택하였다. 총시간최소화 관점에서의 질의실행계획은 반응시간최소화 관점의 질의실행계획에는 적합하지 않다는 것을 증명하였으며, 그 반대의 경우도 증명하였다. 최대 20개의 조인이 포함되는 질의를 설계하여 시뮬레이션 실험을 통해 테스트를 수행하였고, 유전자알고리즘과 완전한 전수조사와의 결과를 비교함으로써 모든 경우에 유전자알고리즘을 채택한 해결책이 최적의 결과를 도출하였음을 증명하였다.

Abstract

Query execution time minimization is an important objective in distributed database design. While total time minimization is an objective for On Line Transaction Processing (OLTP), response time minimization is for Decision Support queries. We formulate the sub-query allocation problem using analytical models and solve with genetic algorithm (GA). We show that query execution plans with total time minimization objective are inefficient from response time perspective and vice versa. The procedure is tested with simulation experiments for queries of up to 20 joins. Comparison with exhaustive enumeration indicates that GA produced optimal solutions in all cases in much less time.

참고문헌 (36)

  1. P.M.G Apers, "Data Allocation in Distributed Database Systems", ACM Trans. on Database Systems, 13(3), pp.263~304 (1988)
  2. J. Arcangeli, "Mobile Agent Based Self-Adaptive Join for Wide-Area Distributed Query Processing", Journal of Database Management, 15(4), pp.25~44 (2004)
  3. J. Atkin, "Total Area Networking: ATM, Frame Relay and SMDS Explained" (1995), John Wiley & Son
  4. F. Baiao, "A Distribution Design Methodology for Object DBMS", Journal of Distributed and Parallel Databases, 16(1), pp.45~90 (2004)
  5. B. Bergsten, "Overview of Parallel Architectures for Database", The Computer Journal, 36, pp.734~740 (1993)
  6. C-H Cheng, "A Genetic Algorithm- Based Clustering Approach for Database Partitioning", IEEE Transactions on Systems, Man, and Cybernetics, 32(3), pp.215~230 (2002)
  7. D.W. Cornell, "On Optimal Site Assignment for Relations in the Distributed Database Environment", IEEE Transactions on Software Engineering, 15(8), pp.1004~1009 (1989)
  8. J. Cuadrado, "Optimize Database Queries", pp.57~63 (1995), Byte
  9. L. Davis, "Handbook of Genetic Algorithms" (1991), Van Nostrand Reinhold
  10. J. Du, "Genetic Algorithms Based Approach to Database Vertical Partitioning", Journal of Intelligent Information Systems, 26(2), pp.167~183 (2006)
  11. W. Du, "Reducing Multidatabase Query Response Time by Tree Balancing", Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, pp.293~303 (1995)
  12. R. Florin, "Sketches for Size of Join Estimation", ACM Transactions on Database Systems, 33(3), pp.1~46 (2008)
  13. O. Frieder, "Site and Query Scheduling Policies in Multicomputer Database Systems", IEEE Transactions on Knowledge and Data Engineering, 6(4), pp.609~619 (1994)
  14. D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning" (1989), Addison-Wesley Publishing
  15. N. Gorla, "An Object-Oriented Database Design for Improved Performance", Data and Knowledge Engineering, 37, pp.117~138 (2001)
  16. G. Graefe, "Query Evaluation Techniques for Large Databases", ACM Computing Surveys, 25, pp.73~90 (1993)
  17. X. Gu, "Practically Realizable Efficient Data Allocation and Replication Strategies for Distributed Databases with Buffer Constraints", IEEE Transactions on Parallel & Distributed Systems, 17(9), pp.1001~1013 (2006)
  18. J. M. Johansson, "Modeling Network Latency and Parallel Processing in Distributed Database Design", Decision Sciences, 34(4), pp.677~706 (2003)
  19. D. Kossmann, "The State of the Art in Distributed Query Processing", ACM Computing Surveys, 32(4), pp.422~469 (2000)
  20. U R. Kulkarni, "Interaction Between Concurrent Transactions in the Design of Distributed Databases", Decision Sciences, 24(2), pp.253~277 (1993)
  21. A. Kumar, "Genetic Algorithm Based Approach for File Allocation on Distributed Systems", Computers & Operations Research, 22(1), pp.41~55 (1995)
  22. B. Li, "A novel stochastic optimization algorithm", IEEE Trans. on Systems, Man, and Cybernetics, Part B, 30(1) (2000)
  23. S-J. Lim, "Vertical Fragmentation and Allocation in Distributed Deductive Database Systems", Information Systems, 22(1), pp.1~24 (1997)
  24. S.T. March, "Allocating Data and Operations to Nodes in Distributed Database Design", IEEE Trans. on Knowledge and Data Engineering, 7(2) (1995)
  25. T. Martin, "An Evaluation of Site Selection Algorithms for Distributed Query Processing", The Computer Journal, 33(1), pp.61~70 (1990)
  26. Z. Michalewicz, "How to Solve It: Modern Heuristics, 2nd edition" (2004), Springer
  27. M. Ozsu, "Principles of Distributed Database Systems" (1991), Prentice-Hall Inc
  28. S. Seshadri, "Routing Queries through a Peer-to-Peer InfoBeacons Network Using Information Retrieval Techniques", IEEE Transactions on Parallel & Distributed Systems, 18(12), pp.1754~1765 (2007)
  29. S.K. Song, "A Genetic Algorithm for Vertical Fragmentation and Access Path Selection", The Computer Journal, 43(1), pp.81~93 (2000)
  30. J. D. Schaffer, "A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization", Proceedings of the Third International Conference on Genetic Algorithms, pp.51~60 (1989)
  31. J. Srivastava, "Optimizing Multi-Join Queries in Parallel Relational Databases", Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, pp.84~92 (1993)
  32. M. Syam, "Allocating Fragments in Distributed Databases", IEEE Transactions on Parallel & Distributed Systems, 16(7), pp.577~585 (2005)
  33. A.M. Tamhankar, "Database Fragmentation and Allocation: An Integrated Methodology and Case Study", IEEE Trans. on Systems, Man, and Cybernetics, 28(3), pp.288~305 (1998)
  34. L. The, "Distributing Data Without Choking the Net", Datamation, 40, pp.35~36 (1994)
  35. C. T. Yu, "Query Processing in a Fragmented Relational Distributed System: Mermaid", IEEE Transactions on Software Engineering, 11, pp.795~809 (1985)
  36. M. Ziane, "Parallel Query Processing in DBS 3", Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, pp.93~102 (1993)

관련 논문AI추천

분산 개체지향 데이타베이스에서 분산 설계 및 구현하얀, 박혜숙, 이순미한국정보처리학회 · 정보처리학회 논문지2004 · 제11권 제5호데이터웨어하우스에서 유전자 알고리즘을 이용한 구체화된 뷰 선택 기법이민수한국정보처리학회 · 정보처리학회논문지D2004 · 제11권 제2호관계형 데이터베이스에서 응답시간에 제약이 있는 경우 최적 역정규화 방법장영관한국산업경영시스템학회 · 한국산업경영시스템학회지2003 · 제26권 제3호이질형 분산 시스템에서 유전자 알고리즘을 이용한 동적 부하 균등 기법이동우, 이성훈, 황종선한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2003 · 제10권 제1호분산 유전 알고리즘에서 자동 마이그레이션 조절방법나용찬, 양지훈, 이현정한국정보처리학회 · 정보처리학회 논문지2010 · 제17권 제2호분산 환경에서 클러스터 노드 할당 시스템을 위한 유전자 기반 최적화 모델박경모한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2003 · 제10권 제1호

이 간행물의 다른 논문 (15건)

GIS-AMR 시스템에서 시공간 데이터마이닝 기법을이용한 전력 소비 패턴의 분석 및 예측류근호, 이헌규, 박진형, 신진호pp. 307-316도로 네트워크 환경을 위한 궤적 클러스터링백지행, 김상욱, 원정임pp. 317-326유전자 발현 데이터에 적용한 거시적인 바이클러스터링 기법안재균, 박상현, 윤영미pp. 327-338공간 프로세스 대수를 이용한 정형 명세와 분석에서의 시간속성의 시각화최정란, 이문근, 온진호pp. 339-352컴포넌트 소프트웨어의 유지보수를 위한 비용 측정지표 및 비용 추정 모델류성열, 조주연pp. 353-360
원문 보기