해쉬 함수 구현 (hash function implementation) 링크 정리

이것도 한 3-4년전에 정리했다가 가끔 업데이트 한 것 같은데… 나름 괜찮은 링크가 몇 개 있어 공유한다. 이것도 앞으로는 이 페이지에서 업데이트를 하겠다. 오래 지나다보니 인터넷에 있는 정보라도 링크가 깨진 것들이 많아 지웠는데 아쉽다. 다행히 이 페이지는 web archive에서 찾을 수 있어 다행이다 싶다.


General

SW-based Implementations

HW-based Implementations


데이터베이스 시스템의 주제별 기초 논문들

데이터베이스 시스템 이라는 큰 주제 아래 각 세부 주제에 대한 기초 논문 목록 들이다. 한참 학교에서 공부하던 시절에 정리하고 틈틈히 업데이트 했던 것 같다. 추후에 data processing이나 column store에 대한 논문들도 공유하도록 하겠다.

데이터베이스 분야는 일반적으로 순수한 알고리즘이나 자료구조 부터 다양한 응용 문제나 이론까지 아주 광범히 하다. 말 자체는 ‘데이터베이스’라서 약간은 고리타분해 보이기도 하지만 데이터에 대해 일반화 가능한 모든 연구라고 봐도 무방할 만큼 해당 학계에서 다양한 연구를 다룬다. 최근 큰 인기를 얻고 있는 하둡이나 분산 데이터처리 역시 데이터베이스 분야에서 활발히 다루어지고 있다. 마이닝의 많은 연구들 또한 이 분야에서 다루어진다. 제목에서 언급한 ‘데이터베이스 시스템’이라고 하면 일반적으로 시스템 구현기술과 이론에 해당되는 내용을 말한다.

개인적으로 해당 분야나 문제를 접할 때 그 문제에 대한 가장 초기 논문들은 꼭 읽어보려고 노력한다. 그 이유는 그 논문들이 그 문제에 대해 가장 깊은 통찰력과 고민들을 많이 담고 있기 때문이며 후대의 논문들 일수록 초기 논문들이 한 고민이나 통찰은 기본적인 전제로 사용되고 문제 풀이 아이디어 위주로 기술되기 때문이다. 그래서 아래 리스트는 각 분야의 초기 논문들 및 전체를 정리하는 논문들 위주로 리스팅이 되어 있다.

주제별로 중요한 논문을 다 담긴 것은 아니다. 주로 내가 관심 있었던 것들 위주이다. 또한 See Also에는 대학들의 좋은 커리큘럼이나 읽어볼만한 주제별 논문에 대해 정리한 리스트의 링크를 담고 있다. 그리고 그 동안은 개인적인 위키에 업데이트를 했었는데 앞으로는 이곳에서 업데이트를 하도록 하겠다.


History

  • M. Stonebraker and J. M. Hellerstein, “What Goes Around, Comes Around,” in Readings in Database Systems, 2005, pp. 2-41.
  • J. M. Hellerstein and M. Stonebraker, “Anatomy of a Database System,” in Readings in Database Systems, 2005, pp. 42-95.
  • Thomas Haigh, Fifty Years of DatabasesACM SIGMOD Blog, 2012.

Architecture

  • M. M. ASTRAHAN et al., System R: relational approach to database management, ACM TODS, 1976.
  • Donald D. Chamberlin et al., A History and Evaluation of System R, Communications of the ACM, 1981.
  • Michael Stonebraker et al., The Design and Implementation of Ingres, ACM TODS, 1976.
  • Joseph M. Hellerstein, Michael Stonebraker, and James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, 2007.

Query Processing

Access Method

  • P. Griffiths Selinger et al., Access Path Selection in a Relational Database Management System, ACM SIGMOD, 1979.
  • Jim Gray et al., The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb, ACM SIGMOD Record, 1997.

Transaction Management

Logging

  • C. Mohan et al., ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-ahead Logging, ACM TODS, 1987.
  • C. Mohan, Repeating History Beyond ARIES, VLDB Conf, 1999.
  • Russel Sears et al,, Segment-Based Recovery: Write-ahead logging revisited, PVLDB, 2009.
  • Philip L. Lehman et al., Efficient Locking for Concurrent Operations on B-Trees, ACM TODS, 1981.

Concurrency Control

  • Jim Gray et al., Granularity of Locks and Degrees of Consistency in a Shared Data Base, Readings in database systems, 1976.
  • Concurrency Control in Database Systems, ACM Computing Survey, 1981.
  • H. T. Kung, On optimistic methods for concurrency control, ACM TODS, 1981.
  • Rakesh Agrawal et al., Concurrency Control Performance Modeling: Alternatives and Implications, ACM TODS, 1987.
  • C. Mohan et al., Transaction Management in the R* Distributed Database Management System, ACM TODS, 1986.
    • Two Phase Commit

Data Warehouse

  • Surajit Chaudhuri and Umeshwar Dayal., An Overview of Data Warehousing and OLAP Technology, ACM SIGMOD Record, 1997.
  • Patrick O’Neil and Dallan Quass, Improved Query Performance with Variant Indexes, ACM SIGMOD, 1997.
  • Jim Gray et al., Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals, Data Mining and Knowledge Discovery, 1997.
  • Yihong Zhao et al., An Array-Based Algorithm for Simultaneous Multidimensional Aggregates, ACM SIGMOD, 1997.
  • C. Mohan and Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, ACM SIGMOD, 1992.

See Also


글쓰기 자동 공유 해제

가만 보니 워드프레스에 글을 쓰다말아 Draft로 표시된 글만 50여개이다. 초반에 글을 잘 쓰다가 다듬는 중에 나 스스로도 만족 못해서 완성을 못한 글들이 50여개 인데… 내 성격을 보여주는 단면인 것 같아서 씁쓸하기도 하다. 글 쓰긴 뿐만 아니라 다른 것들에서도 눈만 높은데 반해 내 실력이 막상 따라주지 못해 만족하지 못해 내놓지 못한 일들이 많다. 사실 Tajo 같은 경우도 어쩌다 보니 공유해달라는 요청을 받아 공유했다가 여기까지 오게된 케이스 인데 그 당시에도 부끄러움에 공유를 망설였던 기억이 있다.

그런데 글을 꾸준히 쓰고 싶은 의욕은 항상 있어왔다. 혼자 정리한 내용도 꽤 많고 지금도 꾸준히 뭔가를 배우거나 개발을 하는 중이라 공유하고 싶은 것도 많다. 순간순간 느끼는 교훈이나 배운 것들은 나중에 내가 다시 보기 위해 기록하고 싶다. 일단은 그 부담을 줄여보고자 기본적으로 트위터나 페이스북을 통해 공유되는 기능을 꺼보았다. 아무래도 SNS를 통해 지인들에게 공유되는 것 보다는 필요에 따라 검색으로 들어오는 분들만 본다면 부담이 덜할 것 같다는 생각이다.

그럼에도 불구하고 잘 모르겠다. 꾸준히 기록해 나갈 수 있을지는.. 한번 노력해볼란다.


아파치 타조 (Apache Tajo) 한글 문서 프로젝트 리소스 및 진행 공유

지난 블로그 포스트 Tajo 한글 프로젝트 프로젝트를 시작에 대해 공유를 했습니다. 이 포스트에서는 짧았지만 몇 일간의 진행과 프로젝트 리소스 정보들을 공유합니다.

프로젝트 리소스 정보는 아래와 같습니다.

현재까지 번역된 페이지는 아래와 같습니다.

또한 현재 SQL 섹션을 남윤민 님이 님이 번역 진행 중이십니다.

사실 Tajo 문서의 양이 그렇게 많지가 않습니다. 그리고 주요 Tajo 개발자들이 한국인이다 보니 아무래도 영문 작성 보다는 한글 작성이 더 쉬운 면이 있습니다. 그래서 문서 추가를 우선 한글로 하고 한글에서 영문으로 번역하는 작업도 고민하고 있습니다. 꾸준히 진행되면 영문과 한글 문서 모두 풍성해지라 기대합니다.

Update

  • 1월 1일 오후 5시에 번역된 페이지 목록 수정

아파치 타조 (Apache Tajo)의 한글 문서화 프로젝트를 시작합니다.

Tajo를 더 보급해보려는 노력으로 Apache Tajo의 한글 문서화 프로젝트를 시작하려고 합니다. 자세한 내용은 아래 링크를 참고 하세요.

https://github.com/hyunsik/tajo-doc-kr

일단은 번역으로 시작하지만 잘 작성된 내용은 upstream에 반영하려고 합니다.

막 github 저장소를 만들고 아직 번역된 내용은 없습니다만 꾸준히 해보려고 합니다. 관심 있으신 분들은 메일이나 메시지를 주시구요.


float과 long 타입의 implicit casting

4 byte 짜리 float이 8 byte 짜리 long보다 widen 더 넓은 범위를 표현하는 type 이었다. 지금까지 Tajo에서 float 과 long의 산술 연산에서 둘다 double로 casting 하고 처리했었는데 사실은 long을 float으로 casting 한 후 해야 IEEE 754에 기반한 결과가 나오는 것이었음.

(4월 28일 Updated ) precision은 당연히 64bit인 long이 더 높다. 하지만 수의 표현 범위만 봤을 때는 float이 더 넓다. 따라서 float과 long의 산술 연산은 long이 float으로 implicit conversion 되어진 후 계산된다.

  • float.MaxValue ~= 3.402823+e38
  • long.MaxValue ~= 9.223372+e18

(4월 28일 Update 2) 정밀도(precision)의 차이가 낮기 때문에 int, long에서 float 또는 long에서 double로 변환될 때 값이 손실 될 수 가 있다. 그러나 항상은 아님.

A widening conversion of an int or a long value to float, or of a long value to double, may result in loss of precision – that is, the result may lose some of the least significant bits of the value. In this case, the resulting floating-point value will be a correctly rounded version of the integer value, using IEEE 754 round-to-nearest mode (§4.2.4).


Jira의 Affect Version과 Fix Version의 차이

Jira를 쓰면서 어렴풋 하게 알고 있었는데 과연 잘 쓰고 있나 궁금하여 정의를 찾아보았다.

https://answers.atlassian.com/questions/27953/difference-between-fix-version-and-affects-version

몇 가지 Q&A를 찾아 보았는데 모두 비슷하게 다음과 같은 의미를 가지고 있는 것 같다.

Affect Version는 해당 이슈가 영향을 미치는 버전들을 가리킨다. 프로젝트를 아주 깊게 알지 못하면 이 것을 추측하기 어려우므로 어느 버전에서 발견했는가 정도가 직관적일 것 같다.

Fix Version은 어느 버전에서 해결 할 것 인가를 가리킨다. 만약 비어 있다면 ‘아직 계획 없음’으로 간주될 수 있다고 한다.


Follow

Get every new post delivered to your Inbox.