데이터베이스 3: 이상, 함수적 종속과 정규화

21 Jul 2024     #cs

이상 (Anomaly)

DB 내 데이터가 불필요하게 중복되어 릴레이션 조작 시 예기치 않게 발생하는 곤란한 현상.

• 삽입 이상 (Insertion Anomaly): 데이터 삽입 시 의도치 않은 값들로 인해 삽입할 수 없게 되는 현상.
• 삭제 이상 (Deletion Anomaly): 튜플 삭제 시 의도치 않은 값들도 삭제되는 현상 (연쇄 삭제).
• 갱신 이상 (Update Anomaly): 튜플의 속성값을 갱신할 때 일부 튜플의 정보만 갱신되는 현상. 불일치성(Inconsistency) 발생.

함수적 종속 (Functional Dependency)

테이블 $R$의 속성 집합의 부분 집합 $X$와 $Y$에 대해, $X$의 값 각각에 대해 항상 $Y$의 값이 오직 하나만 연관되어 있을 때 ‘$Y$는 $X$에 함수적 종속’ 또는 ‘$X$가 $Y$를 함수적으로 결정한다’고 표현함.

• 기호: $X\rightarrow Y$

• 완전 함수적 종속 (Full Functional Dependency): $Y$가 $X$에 대해 함수적 종속이면서 $X$의 어떤 진부분 집합 $Z (X \sup Z)$에도 함수적 종속이 아닐 때 ‘$Y$는 $X$에 완전 함수적 종속’이라고 함.
• 부분 함수적 종속 (Partial Functional Dependency): $Y$가 $X$에 대해 함수적 종속이면서 $X$의 임의의 진부분 집합 $Z$에 대해 함수적 종속일 때 ‘$Y$는 $X$에 부분 함수적 종속’이라고 함.
• 이행적 함수적 종속 (Transitive Functional Dependency): $X\rightarrow Y$이고 $Y\rightarrow Z$일 때 $X\rightarrow Z$인 관계.

정규화 (Normalization)

테이블을 무손실 분해하는 과정. 속성들이 상호 종속적인 관계를 갖는 특성을 이용.

• 목적: 중복을 가능한 제거하여 삽입, 삭제, 갱신 이상의 발생 가능성을 줄이는 것.
• 정규형: 제 1정규형(1NF) → 제 2정규형(2NF) → 제 3정규형(3NF) → BCNF → 제 4정규형(4NF) → 제 5정규형(5NF)

정규화 과정

반정규화 (Denormalization)

정규화된 데이터 모델을 의도적으로 통합, 중복, 분리하여 정규화 원칙을 위배하는 행위.

• 시스템의 성능 향상, 개발 및 운영의 편의성 등을 향상시킬 수 있음.
• 과도한 반정규화는 오히려 성능을 저하시킴.

중복 테이블 추가

작업의 효율성을 위해 테이블을 추가하는 것.

• 집계 테이블 추가: 집계 데이터를 위한 테이블 생성, 원본 테이블에 트리거를 설정하여 사용.
• 진행 테이블 추가: 이력 관리 등의 목적으로 테이블 추가.
• 특정부분만을 포함하는 테이블 추가: 데이터가 많은 테이블에서 특정 부분만을 사용하는 경우 해당 부분으로 새로운 테이블 형성.

데이터베이스 2: 릴레이션과 키, 관계 대수

21 Jul 2024     #cs

관계형 데이터베이스와 릴레이션

관계형 데이터베이스 (Relational DataBase)

데이터를 테이블 형태로 저장하고 관리하는 DB 시스템.

• 각 테이블은 데이터 구조와 데이터 저장 방식에 대해 정의된 고정된 스키마를 따름.
• SQL(Structured Query Language)을 사용하여 데이터의 삽입, 수정, 삭제, 조회 등의 작업을 수행.

릴레이션 (Relation)

관계형 데이터베이스에서 사용하는 기본 구조로, 흔히 테이블(table)이라고 함.

• 행과 열로 구성되며, 각 행은 하나의 데이터 항목(tuple, record)을, 각 열은 데이터 속성(attribute, field)을 나타냄.
• 수학적 개념의 관계(relation)에서 유래하며, 집합론에서의 관계와 비슷한 개념.

릴레이션의 구조

• 릴레이션 스키마 (Relation Schema): 릴레이션의 구조.
• 릴레이션 인스턴스 (Relation Instance): 속성의 데이터 타입에 맞게 구체적인 데이터 값을 가진 데이터 개체.
• 튜플 (Tuple): 릴레이션을 구성하는 각각의 행. 속성의 모임.
  • 카디널리티 (Cardinality; 기수, 대응수): 튜플의 수.
• 속성 (Attribute): DB를 구성하는 가장 작은 논리적 단위. 개체의 특성을 기술.
  • 데이터 항목 또는 데이터 필드에 해당함.
  • 디그리 (Degree; 차수): 속성의 수.
• 도메인 (Domain): 하나의 속성이 취할 수 있는 같은 타입의 원자값들의 집합.
  • 시스템이 속성값의 합법 여부를 검사하는 데 사용. (e.g. ‘Gender’의 도메인은 ‘Male’, ‘Female’로 그 외 값은 입력할 수 없다.)

키 (Key)

DB에서 조건에 맞는 튜플을 찾거나 정렬할 때 기준이 되는 속성.

유일성과 최소성

• 유일성 (Unique): 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있는 성질.
• 최소성 (Minimality): 튜플을 식별하는 데 필요한 최소한의 속성으로 구성된 것.

키의 종류

• 후보키 (Candidate Key): 속성 중 튜플을 유일하게 식별하기 위해 사용되는 속성의 집합.
  • 기본키의 후보가 되는 속성.
  • 조건: 유일성과 최소성을 모두 만족함.
• 기본키 (Primary Key; 주키 (Main Key)): 후보키 중 특별히 선정된 키.
  • 한 릴레이션에서 특정 튜플을 유일하게 구별할 수 있는 속성.
  • 조건: 중복된 값을 가질 수 없음, NULL값을 가질 수 없음.
  • 외래키로 참조될 수 있음.
• 대체키 (Alternate Key; 보조키): 기본키를 제외한 나머지 후보키.
• 슈퍼키 (Super Key): 속성의 집합으로 구성된 키.
  • 릴레이션 내 모든 튜플 중 슈퍼키로 구성된 속성의 집합과 동일한 값은 나타나지 않음.
  • 조건: 유일성은 만족, 최소성은 만족하지 않음.
• 외래키 (Foreign Key): 다른 릴레이션으 기본키를 참조하는 속성 또는 속성의 집합.
  • 조건: 참조 릴레이션의 기본키에 없는 값은 외래키가 될 수 없음.

무결성 (Integrity)

DB에 저장된 데이터 값과 현실 세계의 실제 값이 일치하는 정확성.

• 개체 무결성: 기본키를 구성하는 어떤 속성도 NULL이나 중복값을 가질 수 없다는 규정.
• 참조 무결성: 릴레이션은 참조할 수 없는 외래키 값을 가질 수 없다는 규정. 외래키의 값은 NULL이거나 참조 릴레이션의 기본키 값과 동일해야 함.

인덱스 (Index)

데이터 레코드(튜플)에 빠르게 접근하기 위해 <키, 포인터> 쌍으로 구성된 데이터 구조.

• 레코드가 저장된 물리적 구조에 접근하는 방법을 제공. 빠른 액세스 가능.
• 기본키 인덱스: 기본키를 위한 인덱스. 대부분의 관계형 DBMS에서는 모든 기본키에 대해 기본키 인덱스를 자동 생성함.
• 트리 기반, 함수 기반, 비트맵, 비트맵 조인 인덱스 등이 있음.

관계 대수와 관계 해석

관계 대수 (Relational Algebra)

관계형 DB에서 원하는 정보와 그것을 어떻게 유도하는지를 기술하는 절차적 언어. 릴레이션 조작을 위한 연산의 집합.

• 릴레이션 처리를 위한 연산자와 연산 규칙을 제공. 피연산자와 연산 결과가 모두 릴레이션.
• 해를 구하기 위한 연산의 순서를 명시.

순수 관계 연산자

• Select: 튜플 중 선택 조건을 만족하는 튜플의 부분집합을 구해 새로운 릴레이션을 만드는 연산.
  • 튜플을 구하는 것이므로 ‘수평 연산자’라고도 함.
  • 기호: $\sigma$
• Project: 속성 리스트(Attribute list)에 제시된 속성만을 추출해 새로운 릴레이션을 만드는 연산.
  • 속성을 추출하는 것이므로 ‘수직 연산자’라고도 함.
  • 기호: $\pi$
• Join: 공통 속성을 중심으로 두 릴레이션을 합쳐 새로운 릴레이션을 만드는 연산.
  • Cartesian Product(교차곱) → Select 수행과 결과가 같음.
  • 기호: $\Join$
• Division: $X\supset Y$인 두 릴레이션 $R(X)$와 $S(Y)$가 있을 때, S의 속성값을 모두 가진 R의 속성에서 S의 속성을 제외한 속성만 반환하는 연산.
  • 기호: $\div$

  

일반 집합 연산자

• Union: 두 릴레이션 내 튜플의 합집함을 구하되, 중복되는 튜플은 제거하는 연산.
  • 합집합의 카디널리티는 두 릴레이션의 카디널리티 합보다 작거나 같다.
  • 기호: $\cup$
• Intersection: 두 릴레이션 내 튜플의 교집합을 구하는 연산.
  • 교집합의 카디널리티는 두 릴레이션의 카디널리티 중 작은 값보다 크지 않다.
  • 기호: $\cap$
• Difference: 두 릴레이션 내 튜플의 차집합을 구하는 연산 ($R-S$).
  • 차집합의 카디널리티는 $R$의 카디널리티보다 크지 않다.
  • 기호: $-$
• Cartesian Product: 두 릴레이션 내 튜플의 순서쌍을 구하는 연산.
  • 교차곱의 디그리는 두 릴레이션의 디그리를 더한 것과 같다.
  • 교차곱의 카디널리티는 두 릴레이션의 카디널리티를 곱한 것과 같다.
  • 기호: $\time$

관계 해석 (Relational Calculus)

관계 데이터의 연산을 표현하는 방법. 관계 데이터 모델을 제안한 E. F. Codd가 수학의 술어 해석(Predicate Caculus)에 기반을 두고 관계 DB를 위해 제안함.

• 원하는 정보가 무엇이라는 것만 정의하는 비절차적 특성을 가지며, 원하는 정보를 정의할 때는 수식을 사용함.
• 튜플 관계 해석과 도메인 관계 해석으로 구분됨.

데이터베이스 1: 데이터베이스 설계

21 Jul 2024     #cs

DBMS와 스키마

DBMS (DataBase Management System)

사용자와 데이터베이스(DB) 사이에서 사용자의 요구에 따라 정보를 생성하고 DB를 관리하는 소프트웨어.

• DBMS 관련 요구사항 식별 시 고려사항: 가용성, 성능, 기술지원, 상호호환성, 구축비용

DBMS 필수 기능

• 정의 (Definition): 데이터 형(type)과 구조 정의. 이용 방식, 제약 조건 명시.
• 조작 (Manipulation): 데이터 검색, 갱신, 삽입, 삭제 등을 위해 인터페이스 제공.
• 제어 (Control): 데이터의 무결성/보안/권한 검사, 병행 제어 제공.

스키마 (Schema)

DB의 구조와 제약 조건에 고간한 명세를 기술한 것

스키마의 종류

• 외부 스키마: 사용자나 응용 프로그래머 등 각 개인의 입장에서 필요한 DB의 논리적 구조.
• 개념 스키마: DB 전체의 논리적 구조. 모든 사용자나 응용 프로그램이 필요로 하는 데이터 조직 전체의 DB로 하나만 존재함.
• 내부 스키마: 저장장치 입장에서의 DB 구조. 실제 저장될 레코드의 형식, 표현, 물리적 순서 등을 나타냄.

데이터 모델

현실 세계의 정보를 컴퓨터에 표현하기 위해 단순화/추상화하여 체계적으로 표현한 개념적 모형.

데이터 모델의 요소

• 구조 (Structure): 논리적으로 표현된 개체 타입 간 관계. 데이터 구조 및 정적 성질 표현.
• 연산 (Operation): 실제 데이터를 처리하는 작업에 대한 명세. DB를 조작하는 기본 도구.
• 제약 조건 (Constraint): 데이터가 DB에 저장되기 위한 논리적인 제약 조건.

시스템 카탈로그 (System Catalog)

시스템과 관련된 다양한 객체에 관한 정보를 포함하는 시스템 DB.

• 시스템 카탈로그 내 각 테이블은 사용자를 포함하여 DBMS에서 지원하는 모든 데이터 객체에 대한 정의나 명세 정보를 유지 관리하는 시스템 테이블.
• 데이터 사전 (Data Dictionary)에 카탈로그가 저장되므로, 좁은 의미로는 카탈로그를 데이터 사전이라고도 함.

데이터베이스 설계 순서

1. 요구 조건 분석:
   • 요구 조건 명세서 작성
2. 개념적 설계 (정보 모델링, 개념화): 현실 세계를 추상적 개념으로 표현하는 과정.
   • 개념 스키마 모델링 및 트랜잭션 모델링을 병행 수행.
   • 요구 조건 명세를 DBMS에 독립적인 E-R 다이어그램으로 작성.
3. 논리적 설계 (데이터 모델링): 현실 세계의 자료를 특정 DBMS가 지원하는 논리적 자료 구조로 변환(mapping)하는 과정.
   • 개념적 데이터를 논리적 데이터로 모델링: 데이터 타입(필드)과 데이터 타입 간 관계로 표현.
   • 개념 스키마를 정제하여 DBMS에 따라 다른 논리적 스키마를 설계.
4. 물리적 설계 (데이터 구조화): 논리적 구조의 데이터를 특정 DBMS가 지원하는 물리적 구조의 데이터로 변환하는 과정.
   • 다양한 DB에 응용 가능하도록 DB 파일의 저장 구조 및 액세스 경로를 결정.
   • 저장 레코드의 형식, 순서, 접근 경로, 조회 집중 레코드 등의 정보를 사용해 데이터가 저장되는 방법을 묘사.
5. 구현: 목표 DBMS의 DDL로 DB 생성 및 트랜잭션 작성.

E-R 다이어그램 (Entity-Relationship Diagram)

데이터베이스의 논리적 구조를 시각적으로 표현하여 개체 (Entity), 엔티티 간의 관계 (Relationship), 속성 (Attribute)을 나타내는 다이어그램.

[정처기 요점정리] 응용 소프트웨어 기술 1

21 Jul 2024     #cs

운영체제 (OS; Operating System)

컴퓨터 시스템의 자원을 효율적으로 관리하고, 컴퓨터 사용을 편리하고 효과적으로 사용할 수 있는 환경을 제공하는 프로그램의 모임

• 컴퓨터 사용자와 하드웨어 간 인터페이스로 동작하는 시스템 소프트웨어의 일종
• 컴퓨터 자원 관리: 프로세서, 기억장치 , 입출력장치, 파일, 정보 등
• 운영체제의 목적:
  • 처리 능력 (Throughput): 일정 시간 내 처리하는 일의 양
  • 반환 시간 (Turn Around Time): 작업 의뢰부터 처리 완료까지 걸린 시간
  • 사용 가능도 (Availability): 필요할 때 즉시 사용 가능한 정도
  • 신뢰도 (Reliability): 문제를 정확하게 해결하는 정도

UNIX

1960년대, AT&T 벨 연구소, MIT, General Eletric이 공동 개발한 운영체제

• 시분할 시스템 (Time sharing system)을 위해 설계됨. 대화식 운영체제
• 대부분 C로 작성: 이식성 및 장치/프로세스 간 호환성 높음
• 트리 구조의 파일 시스템
• 시스템 구성:
  • 커널 (Kernel): 핵심 부분. 하드웨어 보호 및 프로그램과 하드웨어 간 인터페이스 역할.
    • 여러가지 기능 수행: CPU 스케줄링, 기억장치, 파일, 입출력 등 관리 및 프로세스 간 통신, 데이터 전송
  • 쉘 (Shell): 명령어 해석기. 사용자 명령을 인식하고 수행. 시스템과 사용자 간 인터페이스 역할.

LINUX

1991년 리누스 토발즈 (Linus Torvalds)가 UNIX를 기반으로 개발한 운영체제

• 소스 코드가 무료로 공개됨
• 대부분의 특징이 UNIX와 동일

Andriod

구글에서 개발한 LINUX 커널 기반의 개방형 모바일 운영체제

• 모든 코드가 공개된 개방형 소프트웨어
• Java와 Cotlin으로 애플리케이션 작성

기억장치 관리

반입 (Fetch)

보조기억장치에 보관 중인 프로그램/데이터를 언제 주기억장치로 적재할 것인지를 결정하는 전략

• 요구 반입 (Demand fetch): 실행 중인 프로그램이 특정 프로그램/데이터의 참조를 요구할 때 적재하는 방법
• 예상 반입 (Anticipatory fetch): 실행 중인 프로그램에 의해 참조될 프로그램/데이터를 예상하여 적재하는 방법

배치 (Placement)

새로 반입되는 프로그램/데이터를 주기억장치의 어디에 위치시킬 것인지를 결정하는 전략

• 최초 적합 (First fit): 적합한 크기의 빈 영역 중 첫 번째 분할 영역에 배치하는 방법
• 최적 적합 (Best fit): 적합한 크기의 빈 영역 중 단편화를 가장 작게 남기는 분할 영역에 배치하는 방법
• 최악 적합 (Worst fit): 적합한 크기의 빈 영역 중 단편화를 가장 많이 남기는 분할 영역에 배치하는 방법

가상기억장치 (Virtual Memory)

보조기억장치의 일부를 주기억장치처럼 사용하는 것. 주기억장치는 용량이 작은데, 마치 큰 용량인 것처럼 사용하는 기법.

• 원리: 프로그램을 블록으로 나누어서 가상기억장치에 보관, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리함.

구현 방법

• 페이징 (Paging): 가상기억장치 내 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 주기억장치에 적재시키는 방법
  • 페이지 (Page): 프로그램을 일정한 크기로 나눈 단위
  • 페이지 프레임 (Page frame): 페이지 크기로 일정하게 나눠진 주기억장치의 단위
• 세그멘테이션 (Segmentation): 가상기억장치 내 프로그램을 다양한 크기의 논리적 단위로 나눈 후 주기억장치에 적재시키는 방법
  • 세그먼트 (Segment): 프로그램을 논리적 크기 (배열, 함수 등)로 나눈 단위. 각 세그먼트는 고유한 이름과 크기를 가짐.

페이지 교체 알고리즘

페이지 부재 (Page fault) 발생 시 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 기법: 페이지 부재가 발생하면 가상기억장치에서 필요한 페이지를 찾아 주기억장치에 적재해야 하는데, 주기억장치의 모든 페이지 프레임이 사용 중인 경우가 있다.

• OPTimal replacment (OPT; 최적 교체): 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법.
  • Belady가 제안했음. 페이지 부재가 가장 적게 발생하는 효율적 방법.
• FIFO (First In First Out): 가장 오래 있었던 페이지를 교체하는 기법.
  • 각 페이지가 주기억장치에 적재된 시각을 기억해야 함.
• LRU (Least Recently Used): 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법.
• LFU (Least Frequently Used): 사용빈도가 가장 적은 페이지를 교체하는 기법.

구역성 (Locality)

프로세스가 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론. 스레싱 (Thrashing) 방지를 위한 워킹 셋 (Working set) 이론의 기반이 되었음.

• 시간 구역성 (Temporla locality): 프로세스가 한 페이지를 일정 시간 동안 집중적으로 액세스하는 현상.
• 공간 구역성 (Spatial locality): 프로세스가 일정 위치의 페이지를 집중적으로 액세스하는 현상.

워킹 셋 (Working Set)

프로세스가 일정 시간 동안 자주 참조하는 페이지의 집합. 자주 참조되는 워킹 셋을 주기억장치에 상주시키면 페이지 부재 및 페이지 교체 수가 줄어들어 프로세스의 기억장치 사용이 안정됨.

스래싱 (Thrashing)

프로세스 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상.

• 다중 프로그래밍 시스템이나 가상기억장치 사용 시스템에서 프로세스 하나를 수행하는 중 페이지 부재가 자주 발생함. 이것으로 시스템 성능이 저하됨.

프로세스 (Process)

“실행 중인 프로그램”. 다양한 정의:

• 프로시저가 활동 중인 것.
• 프로세서에 의해 처리되는 프로그램. 프로세서가 할당되는 실체. 디스패치(dispatch)가 가능한 단위.
• 실기억장치에 저장된 프로그램.
• 비동기적 행위를 일으키는 주체.
• 운영체제가 관리하는 실행 단위. PCB를 가진 프로그램.
  • PCB (Process control block; 프로세스 제어 블록): 운영체제가 프로세스에 대한 중요한 정보를 저장해 놓는 곳
  • PCB에 저장된 정보: 프로세스의 현 상태, 포인터, 프로세스 고유 식별자, CPU 레지스터 정보, 주기억장치 관리 정보, 입출력 상태, 계정 정보

프로세스 상태 전이

프로세스가 시스템 내 존재하는 동안 상태가 변하는 것.

• 디스패치 (Dispatch): 준비 (Ready) 상태인 프로세스가 프로세서를 할당받아 실행 (Run) 상태로 전이되는 과정 (Ready → Run)
• Wake Up: 입출력이 완료되어 대기 (Wait/Block) 상태인 프로세스가 준비 (Ready) 상태로 전이되는 과정 (Wait/Block → Ready)
• 스풀링 (Spooling): 입출력할 데이터를 직접 입출력 장치에 보내지 않고 이후 한 번에 입출력하기 위해 디스크에 저장하는 과정
  • 효과: 입출력장치 공유, 입출력 속도 보완, 다중 프로그래밍 시스템 성능 향상

스레드 (Thread)

시스템의 여러 자원을 할당받아 실행하는 프로그램의 단위. 프로세스 내에서의 작업 단위. 프로세스의 일부 특성을 갖고 있어 경량 프로세스 (Light weight process)라고도 함.

스케줄링 (Scheduling)

프로세스가 생성되어 실행될 때 필요한 시스템의 자원을 해당 프로세스에 할당하는 작업.

비선점 (Non-preemptive) 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 뺏을 수 없는 스케줄링 기법. 일괄 처리 방식에 적합.

• FCFS (First Come First Service; 선입 선출=FIFO): 준비 상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법.
• SJF (Shortest Job First; 단기 작업 우선): 준비 상태 큐 내 프로세스 중 실행시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 기법.
  • 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘.
• HRN (Highest Response-ratio Next): 대기 시간과 서비스(실행) 시간을 통해 우선순위를 계산하여, 우선순위가 높은 것부터 스케줄링하는 기법.
  • 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간

선점 (Preemptive) 스케줄링

우선순위가 높은 프로세스가 이미 할당된 CPU를 빼앗아 사용할 수 있는 스케줄링 기법. 빠른 응답시간이 요구되는 대화식 시분할 시스템에 적합.

• 종류: RR, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등
• RR (Round Robin): 각 프로세스를 시간 할당량 (time slice, quantum) 동안만 실행한 후, 실행이 완료되지 않으면 다음 프로세스에 CPU를 넘겨주는 기법.
  • 시분할 시스템 (time sharing system)을 위해 고안된 방식. 할당 시간이 작으면 작은 프로세스에게 유리.
  • 할당 시간이 큰 경우 FCFS와 같아지고, 할당 시간이 작으면 문맥 교환 및 오버헤드가 자주 발생하여 신속한 작업 처리가 불가함.
• SRT (Shortest Remaining Time): 현재 실행 중인 프로세스의 남은 시간과 준비 상태 큐에 새로 도착한 프로세스의 실행 시간을 ㅣㅂ교하여, 가장 짧은 시간을 요구하는 프로세스에게 CPU를 넘기는 기법.
  • (+) 시분할 시스템에 유용. (-) 준비 상태 큐 내 프로세스의 실행 시간을 추적 보유해야 하므로 오버헤드가 증가함.

환경 변수와 OS 명령어

환경 변수 (Environment Variable)

시스템 소프트웨어의 동작에 영향을 미치는 동적인 값의 모임. 변수명과 값으로 구성됨.

• Windows의 set, UNIX/LINUX의 set, env, printenv, setenv 를 입력하면 모든 환경변수와 값을 출력함.

Windows 기본 명령어

• dir 현재 디렉터리 파일 목록 표시 / cd 동일 드라이브 내에서 디렉터리의 위치를 변경 / md 디렉터리 생성
• copy 파일 복사 / del 파일 삭제 / ren 파일 이름 변경 / type 파일 내용 표시 / move 파일 이동
• cls 화면 내용 삭제
• attrib 파일 속성 변경 / find 파일에서 문자열을 찾음
• chkdsk 디스크 상태 점검 / format 디스크 표면을 트랙과 섹터로 나누어 초기화

UNIX/LINUX 기본 명령어

• cat 파일 내용 표시

파일 내용 표시

cat

type

Summaries of papers on MRI Quality Assessment and Control

14 Jun 2024     #brainImaging #mri

I summarized four papers related to MRI quality assessment and control. Below are the summaries:

Paper list

• Liao, Lufan, et al. “Joint image quality assessment and brain extraction of fetal MRI using deep learning.” Medical Image Computing and Computer Assisted Intervention–MICCAI 2020: 23rd International Conference, Lima, Peru, October 4–8, 2020, Proceedings, Part VI 23. Springer International Publishing, 2020.
• Giganti, Francesco, et al. “Prostate Imaging Quality (PI-QUAL): a new quality control scoring system for multiparametric magnetic resonance imaging of the prostate from the PRECISION trial.” European urology oncology 3.5 (2020): 615-619.
• Esses, Steven J., et al. “Automated image quality evaluation of T2‐weighted liver MRI utilizing deep learning architecture.” Journal of Magnetic Resonance Imaging 47.3 (2018): 723-728.
• Monereo-Sánchez, Jennifer, et al. “Quality control strategies for brain MRI segmentation and parcellation: Practical approaches and recommendations-insights from the Maastricht study.” Neuroimage 237 (2021): 118174.

Joint Image Quality Assessment and Brain Extraction of Fetal MRI Using Deep Learning (2020)

Background

• Quality Assessment (QA): Evaluates MRI image quality for analysis suitability.
• Brain Extraction (BE): Identifies and isolates the brain region from the MRI image.

Traditionally handled separately, this paper proposes a joint deep learning model for simultaneous QA and BE, enhancing performance and efficiency, since both tasks focus on the brain region. Besides, dealing with fetal brain images are difficult, in that they can appear in different positions and angles within the MRI scans. And their shapes and appearances change as fetuses grow. To solve this difficulty, the study leverages deformable convolution method.

Main Contributions

1. Joint Optimization: Combining QA and BE, allowing the network to learn shared features and reducing the risk of overfitting.

2. Multi-Stage Deep Learning Model:

   • Brain Detector: Locates the brain region within the MRI scan. This helps in focusing the subsequent analysis on the relevant part of the image.
   • Deformable Convolution: Adapts the receptive field to the varying shapes and sizes of fetal brains. This is crucial because fetal brain shapes change significantly across different gestational ages.
   • Task-Specific Module: Simultaneously performs QA and BE.

3. Multi-Step Training Strategy: Progressive training enhances model learning.

Evaluation

• Datasets: Fetal MRI images, focusing on 2D slice quality.
• Metrics:
  • Dice Similarity Coefficient (DSC): The primary metric for evaluating the accuracy of brain extraction, measuring the overlap between the predicted and true brain regions.
  • Quality Scores: For image quality assessment, the model was trained to classify images into different quality levels.
• Results:
  • The model achieved a DSC score of 0.89, which is comparable to or better than existing methods, indicating high accuracy in brain extraction.
  • The image quality assessment module successfully classified image slices into quality categories, with 85% accuracy in distinguishing between high and low-quality images.

Conclusion

The study introduces a DL model for simultaneous QA and BE in fetal MRI scans, using deformable convolutions to handle variability in brain images. The multi-step training and diverse dataset validation demonstrate its effectiveness, making it a promising tool for fetal MRI analysis.

Prostate Imaging Quality (PI-QUAL): A New Quality Control Scoring System for Multiparametric Magnetic Resonance Imaging of the Prostate from the PRECISION trial (2020)

Background

The PRECISION trial was a multicenter randomized study that demonstrated multiparametric magnetic resonance imaging (mpMRI)-targeted biopsy is superior to standard transrectal ultrasound-guided biopsy for detecting prostate cancer. The success of mpMRI-targeted biopsies relies heavily on the quality of the mpMRI scans, but there was no existing scoring system to evaluate this quality.

Prostate Imaging Quality (PI-QUAL)

To address this gap, the researchers introduced a novel scoring system called the Prostate Imaging Quality (PI-QUAL) score. PI-QUAL is a Likert scale from 1 to 5:

• 1: No mpMRI sequences are of diagnostic quality.
• 5: Each sequence is independently of optimal diagnostic quality.

Method

1. Selection of MRI scans: From the PRECISION trial, 58 out of 252 mpMRI scans (23%) were randomly selected for evaluation. These scans were taken from 22 different centers involved in the trial.
2. Radiologist assessment: Two experienced radiologists from the coordinating trial center independently assessed the selected MRI scans. The radiologists were blinded to the pathology results to ensure unbiased evaluation.
3. Scoring system: The scans were scored using the newly developed PI-QUAL system.
4. Quality Metrics
   • Overall quality: The overall diagnostic quality of the scans was evaluated.
   • Specific sequence quality: The quality of individual sequences such as T2-weighted imaging (T2WI), diffusion-weighted imaging (DWI), and dynamic contrast-enhanced imaging (DCE) was assessed separately.
5. Statistical Analysis
   • The percentage of scans with sufficient diagnostic quality (PI-QUAL score ≥3) was calculated.
   • The percentage of scans with good or optimal diagnostic quality (PI-QUAL score ≥4) was determined.
   • The diagnostic quality of the specific imaging sequences (T2WI, DWI, DCE) was also analyzed.

Results

• Overall Diagnostic Quality:
  • 55 out of 58 scans (95%) had sufficient diagnostic quality (PI-QUAL score ≥3).
  • 35 out of 58 scans (60%) had good or optimal diagnostic quality (PI-QUAL score ≥4).
• Sequence-Specific Quality: 95% of T2WI scans, 79% of DWI scans, and 66% of DCE scans were of diagnostic quality.

Conclusion

The introduction of the PI-QUAL score provides a standardized method to assess the quality of mpMRI scans. Further validation of this scoring system is recommended to ensure its effectiveness in various clinical settings.

Automated image quality evaluation of T2-weighted liver MRI utilizing deep learning architecture (2018)

Background

Accurate screening of T2-weighted (T2WI) liver MRI scans is essential for effective diagnosis, but manual evaluation by radiologists is time-consuming and subject to variability. Automated methods, specifically using deep learning (DL) approaches like Convolutional Neural Networks (CNNs), offer a promising solution for consistent and efficient image quality assessment. This study aimed to develop and evaluate a CNN for automated screening to identify non-diagnostic images and compare its performance to radiologists’ evaluations.

Method

• Data Collection: The study utilized 522 liver MRI exams performed at 1.5T and 3T between November 2014 and May 2016 for training and validation of the CNN.
• CNN Architecture: The CNN consisted of several layers, including an input layer, convolutional layer, fully connected layer, and output layer.
• Training Data: 351 T2WI images were anonymized and labeled as diagnostic or non-diagnostic based on their ability to detect lesions and assess liver morphology. These were used to train CNN.
• Validation Data: An independent set of 171 T2WI images was used for blind testing. Two radiologists independently evaluated these images, labeling them as diagnostic or non-diagnostic.
• Comparison: The image quality (IQ) output from the CNN was compared to the evaluations made by the two radiologists.

Results

• The agreement between the CNN and the radiologists was: 79% with Reader 1, and 73% with Reader 2
• Sensitivity and Specificity of the CNN in identifying non-diagnostic images:
  • Sensitivity: 67% with respect to Reader 1 and 47% with respect to Reader 2
  • Specificity: 81% with respect to Reader 1 and 80% with respect to Reader 2
• Negative predictive value: 94% with respect to Reader 1 and 86% with respect to Reader 2

Conclusion

This research shows the potential of using deep learning, specifically a CNN, for automated quality evaluation of T2-weighted liver MRI images. The CNN’s performance was compared to radiologists’ assessments, showing a high negative predictive value, which indicates its reliability in identifying diagnostic images. This automated approach could be assist radiologists in clinical settings by quickly and accurately determining the quality of MRI scans.

Quality control strategies for brain MRI segmentation and parcellation: Practical approaches and recommendations - insights from the Maastricht study (2021)

Background

Quality control (QC) in brain MRI segmentation is crucial for ensuring accurate data. Manual QC, although considered the gold standard, is impractical for large datasets due to its time-consuming nature. Automated methods offer faster and reproducible alternatives but lack a consensus on the best approach. This study aims to highlight the impact of manual edits on brain segmentation accuracy and compare various QC strategies to reduce measurement errors effectively.

Method

• Data: Structural brain MRI from 259 participants of The Maastricht Study.
• Segmentation Tool: FreeSurfer 6.0 was used to automatically extract morphological estimates.
• Manual Editing: Segmentations with inaccuracies were manually edited, and the differences in morphological estimates before and after editing were compared.
• Quality Control Strategies:
  • Manual Strategies: Visual inspection to exclude or manually edit images.
  • Automated strategies: Exclusion of outliers using MRIQC and Qoala-T, and metrics such as morphological global measures, Euler numbers, and Contrast-to-Noise ratio.
  • Semi-Automated Strategies: Visual inspection and manual editing of outliers detected by tools and metrics without excluding them.
• Evaluation: Measuring the proportion of unexplained variance relative to the total variance after applying each strategy.

Results

• Manual Editing: Significant changes in subcortical brain volumes and moderate changes in cortical surface area, thickness, and hippocampal volumes.
• Strategy Performance: Depended on the morphological measure of interest.
  • Manual Strategies: Provided the largest reduction in unexplained variance.
  • Automated Alternatives: Based on Euler numbers and MRIQC scores.
  • Global Morphological Measures: Excluding outliers increased unexplained variance.

Conclusion

The study underscores the importance of QC in brain MRI segmentation, advocating for manual methods as the most reliable, though impractical for large datasets. Automated methods, especially those using Euler numbers and MRIQC, provide effective alternatives. Excluding outliers based on global measures may increase errors, guiding practical QC recommendations for neuroimaging research to ensure data accuracy and reliability.