셀렉션(Selection) 연산

• 파일 스캔
  셀렉션 조건을 만족하는 레코드들을 찾아서 검색하는 탐색 알고리즘
  • 선형 탐색(Linear Search)
    • 각각의 파일 블록을 스캔하고 모든 레코드들에 대해 셀렉션 조건을 만족하는지를 검사
    • 속도가 가장 느림
  • 이진 탐색(Binary Search)
    • 파일이 순서화되어 있는 속성에 대해 셀렉션이 동등(Equality) 비교일 경우 적용 가능
    • 순서적으로 정렬된 파일에서, 파일의 중간 레코드의 키와 조건 키와의 비교를 반복하면서 탐색하는 방법
       
• 인덱스 스캔
  인덱스를 사용하는 탐색 알고리즘
  • 후보키에 대한 기본 인덱스, 동등
    대응하는 동등 조건을 만족하는 단일 레코드 검색
  • 비(非) 키(Non-key)에 대한 기본 인덱스, 동등
    다중 레코드 검색
  • 탐색키에 대한 보조 인덱스, 동등
    탐색키가 후보키인 경우는 단일 레코드를 검색하고, 후보키가 아닌 경우에는 다중 레코드를 검색
  •    
• 비교를 포함하는 셀렉션
  릴레이션이 속성 A에 대해 정렬되어 있는 경우
  • 기본 인덱스, 비교
    • σ_￢A≥v(r)
      인덱스를 사용하여 A값≥V인 첫 번째 튜플을 찾고, 거기에서부터 릴레이션을 순차적으로 스캔
    • σ_￢A≤v(r)
      A값 > V인 최종 튜플을 찾을 때가지 릴레이션을 순차적으로 스캔(인덱스 사용 안함)
  • 보조 인덱스, 비교
    • σ_A≥v(r)
      인덱스를 사용하여 A값≥V인 첫 번째 인덱스 항목을 찾고, 거기서부터 레코드들에 대한 포인터들을 찾기 위해 순차적으로 인덱스를 스캔
    • σ_￢A≤v(r)
      A값 > V인 첫 번째 인덱스 항목을 만날 때까지 레코드들에 대한 포인터를 찾기 위해 인덱스의 리프 페이지들을 스캔
    •    
• 부정을 포함한 셀렉션 : σ_￢θ(r)
  • 파일에 대한 순차 스캔 사용
  • 매우 작은 레코드가 ￢θ를 만족하고 인덱스가 θ에 대해서 적용 가능하면, 인덱스를 사용하여 만족하는 레코드들을 찾아서 파일로부터 읽어냄