본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

데이터웨어하우스에서 유전자 알고리즘을 이용한 구체화된 뷰 선택 기법
A Genetic Algorithm for Materialized View Selection in Data Warehouses

이민수   (이화여자대학교 컴퓨터학과UU0001056  );
  • 초록

    데이터 웨어하우스는 복잡한 질의 및 분석을 위해서 다양한 종류의 여러 정보 출처들로부터 정보를 모아서 저장한다. 일반적으로 웨어하우스에는 자주 실행되는 질의들을 미리 계산해서 구체화된 뷰의 형태로 저장한다. 웨어하우스를 설계할 때 가장 중요한 일들 중의 하나는 웨어하우스에서 유지될 구체화된 뷰의 선택이다. 이것은 뷰들의 유지를 위해 제한된 시간이 주어졌을 때, 모든 질의들에 대한 총 질의 응답 시간을 최소화하는 방법으로 일련의 뷰들을 선택하는 것이다(유지-비용 뷰 선택 문제). 본 논문에서는 최적에 가까운 일련의 뷰들을 계산하기 위해 유전자 알고리즘을 사용하여 유지-비용 뷰 선택 문제에 대한 효율적인 해결책을 제안한다. 특히 OR 뷰 그래프들의 관점에서의 유지-비용 뷰 선택 문제를 다룬다. 본 논문의 접근방식은 휴리스틱 방법을 사용한 기존의 탐색-기반 접근 방식들에 비해서, 시간 복잡도에서 큰 향상을 보여준다. 본 논문의 알고리즘은 최적의 질의 비용에 비해 10%이내의 추가비용만을 갖는 해결책을 제시하면서도 실행시간 측면에서는 매우 향상된 선형 증가만을 보인다. 본 논문의 알고리즘에 대한 프로토타입을 구현하였으며 이것을 사용하여 논문에서 제안하는 접근방식의 분석을 수행하였다.


    A data warehouse stores information that is collected from multiple, heterogeneous information sources for the purpose of complex querying and analysis. Information in the warehouse is typically stored In the form of materialized views, which represent pre-computed portions of frequently asked queries. One of the most important tasks of designing a warehouse is the selection of materialized views to be maintained in the warehouse. The goal is to select a set of views so that the total query response time over all queries can be minimized while a limited amount of time for maintaining the views is given(maintenance-cost view selection problem). In this paper, we propose an efficient solution to the maintenance-cost view selection problem using a genetic algorithm for computing a near-optimal set of views. Specifically, we explore the maintenance-cost view selection problem in the context of OR view graphs. We show that our approach represents a dramatic improvement in terms of time complexity over existing search-based approaches that use heuristics. Our analysis shows that the algorithm consistently yields a solution that only has an additional 10% of query cost of over the optimal query cost while at the same time exhibits an impressive performance of only a linear increase in execution time. We have implemented a prototype version of our algorithm that is used to evaluate our approach.


  • 주제어

    데이터웨어하우스 .   유전자 알고리즘 .   뷰 유지 .   뷰 구체화 .   뷰 선택 .   웨어하우스 구성.  

  • 참고문헌 (21)

    1. P. J. M. v. Laarhoven and E. H. L. Aarts, Simulated Annealing : Theory and Applications, Kluwer, Dordrecht, Holland, 1987 
    2. MIT Technology Lab, GAlib : A C++ Library of Genetic Algorithm Components, URL, http://lancet.mit.edu/ga/ 
    3. M. R. Garey and D. S. Johnson, Computers and Intractability-A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 
    4. E. H. L. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines, John Wiley, Chichester, UK, 1989 
    5. S. A. Cook, The Complexity of Theorem Proving Procedure, Annual ACM SIGACT Symposium on Theory of Computing, Vol.3, pp.151-158, 1971 
    6. S. Augier, G. Venturini and Y. Kodratoff, Learning First Order Logic Rules with a Genetic Algorithm, in Proceedings of the First International Conference on Knowledge Discovery and Data Mining(KDD-95), Montreal, Canada, pp.21-26, 1995 
    7. I. W. Flockhart and N. J. Radcliffe, A Genetic Algorithm-based Approach to Data Mining, in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining(KDD-96), Portland, Oregon, pp.299-302, 1997 
    8. H. Gupta and I. Mumick, Selection of Views to Materialize Under a Maintenance Cost Constraint, in Proceedings of the International Conference on Management of Data, Jerusalem, Israel, pp.453-470, 1999 
    9. A. Swami, Optimization of large join queries : combining heuristics and combinational techniques, SIGMOD Record, Vol.18, No.2, pp.367-76, 1989 
    10. K. A. Ross, D. Srivastava, and S. Sudarshan, Materialized view maintenance and integrity constraint checking : Tradingspace for time, SIGMOD Record (ACM Special Interest Group on Management of Data), Vol.25, No.2, pp.447-458, 1996 
    11. W. Labio, D. Quass and B. Adelberg, Physical Database Design for Data Warehouses, in Proceedings of the International Conference on Database Engineering, Birmingham, England, pp.277-288, 1997 
    12. D. Theodoratos and T. K. Sellis, Data Warehouse Configuration, in Proceedings of the Twenty-third International Conference on Very Large Databases, Athens, Greece, pp.126-135, 1997 
    13. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, Mass, 1989 
    14. Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Sringer-Verlag, New York, NY., 1994 
    15. N. Roussopoulos, View Indexing in relational Databases, ACM Transactions on Database Systems Vol.7, No.2, pp.258-290, 1982 
    16. H. Gupta, Selection of Views to Materialize in a Data Warehouse, in Proceedings of the International Conference on Database Theory, Delphi, Greece, pp. 98-112, 1997 
    17. Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom, View Maintenance in a Warehousing Environment, SIGMOD Record(ACM Special Interest Group on Management of Data) Vol.24, No.2, 316-27, 1995 
    18. A. Gupta and I. S. Mumick, Maintenance of Materialized Views : Problems, Techniques, and Applications, Data Engineering Bulletin, Special Issue on Materialized Views and Data Warehousing, Vol.18, No.2, pp.3-18, 1995 
    19. N. Roussopoulos, Materialized Views and Data Warehouses, in Proceedings of the Workshop on Knowledge Representation meets Databases(KRDB), 12.1-12.6, Athens, Greece, 1997 
    20. W. H. Inmon and C. Kelley, Rdb/VMS : Developing the Data Warehouse, QED Publishing Group, Boston, London, Toronto, 1993 
    21. J. Widom, Research Problems in Data Warehousing, in Proceedings of the Fourth International Conference on Information and Knowledge Management, Baltimore, Maryland, pp.25-30, 1995 

 저자의 다른 논문

  • 이민수 (16)

    1. 2002 "웹 기반의 OLAP 메타데이터 교환 시스템의 설계 및 구현" 정보처리학회논문지. The KIPS transactions. Part D. Part D d9 (6): 971~980    
    2. 2003 "샤모아: 컴포넌트 기반의 지식공학 프레임워크" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 21 (10): 45~53    
    3. 2004 "바이오패스웨이를 위한 지식 표현 시스템" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 31 (3): 343~352    
    4. 2005 "무선 인터넷 컨텐츠의 자동 생성을 위한 WML 변환기와 WML 편집기의 설계 및 구현" 정보처리학회논문지. The KIPS transactions. Part D. Part D d12 (2): 309~318    
    5. 2006 "Prediction Model for the Cellular Immortalization and Transformation Potentials of Cell Substrates" Genomics & informatics 4 (4): 161~166    
    6. 2006 "특징 추출과 분석 기법에 기반한 단백질 상호작용 데이터 신뢰도 향상 시스템" 정보처리학회논문지. The KIPS transactions. Part B. Part B b13 (7): 679~688    
    7. 2006 "Prediction of Exposure to 1763MHz Radiofrequency Radiation Using Support Vector Machine Algorithm in Jurkat Cell Model System" Genomics & informatics 4 (2): 71~76    
    8. 2006 "XQuery에서의 XML 데이터 특성을 고려한 group by 지원을 위한 질의 표현 기법에 대한 연구" 정보처리학회논문지. The KIPS transactions. Part D. Part D d13 (4): 501~512    
    9. 2010 "교통이력 데이터의 품질 개선과 What-If 분석을 위한 자료처리 기법의 구현" 정보처리학회논문지. The KIPS transactions. Part D. Part D d17 (2): 87~102    
    10. 2011 "Implementation of a Particle Swarm Optimization-based Classification Algorithm for Analyzing DNA Chip Data" Genomics & informatics 9 (3): 134~135    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기