준똘똘의 IT세상

4.1 표준형과 용어

• minimize f₀(x) subject to fᵢ(x) ≤ 0, hᵢ(x) = 0
• Feasible: 정의역 안에 있고 모든 제약을 만족하는 점
• 최적값 p★ = inf { f₀(x) | x feasible }
  • p★ = +∞: infeasible (feasible 점이 없음)
  • p★ = −∞: unbounded below
• Optimal: feasible이고 f₀(x) = p★ 인 점. 여러 개일 수 있다.
• Locally optimal: R > 0 이 있어서, ‖z − x‖₂ ≤ R 인 feasible z들 중에서 x가 최적

4.2 1차원 예 (슬라이드 4.5)

• f₀ = 1/x (x > 0): p★ = 0, 최적점 없음
• f₀ = −log x (x > 0): p★ = −∞
• f₀ = x log x (x > 0): p★ = −1/e, x = 1/e 에서 최적
• f₀ = x³ − 3x: p★ = −∞, x = 1 은 local optimal

4.3 Implicit / explicit 제약, feasibility problem

• Implicit 제약: x는 모든 fᵢ, hᵢ의 정의역의 교집합 D 안에 있어야 한다.
  • 예: −Σ log(bᵢ − aᵢᵀx) 는 제약이 없어 보여도 aᵢᵀx < bᵢ 가 숨어 있다.
• ⭐ 2·3장을 배운 이유: 제약이 명시적으로 안 써져 있어도 convex인지 알아내려고
• Feasibility problem = f₀ = 0 인 특수 경우
  • feasible이면 p★ = 0, 아니면 ∞

4.4 Convex 문제의 표준형

• 조건: f₀, …, fₘ 이 convex, 등식은 Ax = b (affine)
• Feasible set = 정의역 ∩ sublevel set들 ∩ affine 집합 → convex
• Optimal set도 convex
• 예 (슬라이드 4.9)
  • minimize x₁² + x₂² subject to x₁/(1 + x₂²) ≤ 0, (x₁ + x₂)² = 0
  • Feasible set 자체는 convex지만, 식이 규칙을 어겨서 convex 문제가 아니다.
  • x₁ ≤ 0, x₁ + x₂ = 0 으로 바꾸면 동치인 convex 문제가 된다.
• Quasiconvex 문제: f₀ 만 quasiconvex이고 나머지 조건은 같다.

4.5 Local = global

1. 가정: x는 local optimal인데, f₀(y) < f₀(x) 인 feasible y가 있다.
2. z = θy + (1−θ)x, θ = R / (2‖y − x‖₂) 로 둔다.
3. ‖y − x‖₂ > R 이므로 0 < θ < 1/2
4. z는 feasible 점들의 볼록 조합이므로 feasible이고, ‖z − x‖₂ = R/2
5. f₀(z) ≤ θf₀(y) + (1−θ)f₀(x) < f₀(x) → x가 local optimal이라는 가정과 모순

4.6 미분 가능한 f₀ 의 최적성 조건

• x가 최적 ⟺ x가 feasible이고 모든 feasible y에 대해 ∇f₀(x)ᵀ(y − x) ≥ 0
  • ∇f₀(x) ≠ 0 이면 −∇f₀(x)가 feasible set의 supporting hyperplane을 정의한다.
• 특수 경우
  • 제약 없음: ∇f₀(x) = 0
  • 등식 Ax = b: ∇f₀(x) + Aᵀν = 0 인 ν가 존재
  • ℝ₊ⁿ 위: xᵢ = 0 이면 ∇f₀(x)ᵢ ≥ 0, xᵢ > 0 이면 ∇f₀(x)ᵢ = 0
• (KKT 조건 예고)

4.7 LP

• minimize cᵀx + d subject to Gx ⪯ h, Ax = b
• Feasible set은 polyhedron
• 식단 문제: minimize cᵀx subject to Ax ⪰ b, x ⪰ 0
• Piecewise-linear 최소화: min maxᵢ(aᵢᵀx + bᵢ)
  • minimize t subject to aᵢᵀx + bᵢ ≤ t 로 바꾸면 LP (epigraph)
• Chebyshev center: maximize r subject to aᵢᵀxc + r‖aᵢ‖₂ ≤ bᵢ
  • 근거: sup_{‖u‖₂ ≤ r} aᵢᵀu = r‖aᵢ‖₂

4.8 QP

• minimize (1/2)xᵀPx + qᵀx + r subject to Gx ⪯ h, Ax = b, P ⪰ 0
• Least squares
  • 해: x★ = A†b (A†는 pseudo-inverse)
  • 제약 추가 가능: x ⪰ 0, x₁ ≤ … ≤ xₙ
• Random cost LP: minimize c̄ᵀx + γxᵀΣx → QP (γ는 위험회피 계수)

4.9 QCQP, SOCP

• QCQP: 목적과 제약이 모두 convex 이차식
  • Pᵢ ≻ 0 이면 feasible set은 타원체들의 교집합 ∩ affine 집합
• SOCP: minimize fᵀx subject to ‖Aᵢx + bᵢ‖₂ ≤ cᵢᵀx + dᵢ, Fx = g
  • nᵢ = 0 이면 LP, cᵢ = 0 이면 QCQP로 줄어든다.

4.10 Robust LP

• 최악 경우 접근: aᵢ ∈ { āᵢ + Pᵢu | ‖u‖₂ ≤ 1 }
  • 제약이 āᵢᵀx + ‖Pᵢᵀx‖₂ ≤ bᵢ 가 되어 SOCP
• 확률적 접근: aᵢ ~ N(āᵢ, Σᵢ)
  • 제약이 āᵢᵀx + Φ⁻¹(η)‖Σᵢ^(1/2)x‖₂ ≤ bᵢ
  • η ≥ 1/2 이면 SOCP

4.11 Conic form, SDP

• Conic form: minimize cᵀx subject to Fx + g ⪯ₖ 0, Ax = b
  • LP는 K = ℝ₊ᵐ 인 경우
• SDP: 제약 x₁F₁ + … + xₙFₙ + G ⪯ 0 (LMI)
  • LMI 여러 개는 블록대각으로 하나로 합칠 수 있다.
• 행렬 norm 최소화 ‖A(x)‖₂ → 제약 [tI A(x); A(x)ᵀ tI] ⪰ 0 (Schur)
• 포함 관계: LP ⊂ QP ⊂ QCQP ⊂ SOCP ⊂ SDP

4.12 문제 변환 

• 변수 치환 x = φ(z)
  • 예: x = e^z 로 바꾸면 nonconvex 문제가 convex가 되기도 한다.
• 목적·제약에 단조함수 적용
  • 예: ‖Ax − b‖ 최소화 ⟺ ‖Ax − b‖² 최소화
  • 최대화는 최소화로 바꾼다.
• 등식 제거(x = Fz + x₀)·등식 도입
• Slack 변수: aᵢᵀx + sᵢ = bᵢ, sᵢ ≥ 0
• Epigraph form: minimize t subject to f₀(x) − t ≤ 0
• 일부 변수에 대한 최소화 (3.12와 연결)
• Convex relaxation: 원래 문제의 하한을 준다.
  • 예: Boolean LP에서 z ∈ {0, 1} 을 z ∈ [0, 1] 로 완화

4.13 DCP, CVXPY

• 목적: convex 최소화 또는 concave 최대화
• 제약: convex ≤ concave, affine == affine
• CVXPY의 동작: 원래 문제를 LP·QP·SOCP·SDP 표준형까지 동치 변환 → 솔버로 풂 → 역변환

4.14 Geometric programming

• Monomial: c·x₁^a₁ ⋯ xₙ^aₙ (c > 0)
• Posynomial: monomial의 합
• GP: 부등식 제약은 posynomial ≤ 1, 등식 제약은 monomial = 1
• yᵢ = log xᵢ 로 바꾸고 로그를 취하면 log-sum-exp 꼴의 convex 문제가 된다.
• 예: ‖DMD⁻¹‖_F² 를 최소화하는 대각 스케일링

4.15 Quasiconvex optimization

• Local optimal이 global이 아닐 수 있다.
• Linear-fractional program
  • y = x / (eᵀx + f), z = 1 / (eᵀx + f) 로 바꾸면 LP
• f₀(x) ≤ t ⟺ φₜ(x) ≤ 0 (φₜ는 convex)
  • 예: p/q 이면 φₜ = p − tq
• Bisection
  • t = (l + u)/2 에서 convex feasibility 문제를 푼다.
  • feasible이면 u = t, 아니면 l = t
  • 반복 횟수: ⌈log₂((u − l)/ε)⌉

4.16 다중목적 최적화

• Pareto optimal: 다른 feasible 점에게 지배당하지 않는 점
  • 목적이 2개면 trade-off curve를 이룬다.
• Scalarization: λ ≻ 0 으로 λᵀf₀(x) 를 최소화하면 Pareto optimal 점을 얻는다.
  • convex 문제면 λ를 바꿔 가며 거의 모든 Pareto 점을 얻을 수 있다.
• 예
  • ‖Ax − b‖₂² + γ‖x‖₂²
  • 포트폴리오: −p̄ᵀx + γxᵀΣx

3.1 정의

• dom f가 convex이고 f(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y), θ ∈ [0, 1]
  • 두 점을 이은 현(chord)이 그래프 위에 있다.
• Concave: −f가 convex
• Strictly convex: x ≠ y, 0 < θ < 1 에서 부등식이 strict
• ⭐ 직선(affine)은 convex이면서 concave다. 하지만 strictly convex는 아니다.

3.2 예 ✍️

• ℝ 위 convex: ax + b, e^(ax), x^α (x > 0이고 α ≥ 1 또는 α ≤ 0), |x|^p (p ≥ 1), max{0, x}
• ℝ 위 concave: ax + b, x^α (0 ≤ α ≤ 1), log x, −x log x, min{0, x}
• ℝⁿ 위 convex: affine, 모든 norm, ‖x‖₂², max xᵢ, log-sum-exp
• 판서(max 증명)
  • 보조부등식: max{a + c, b + d} ≤ max{a, b} + max{c, d}
  • 이걸로 max(θx + (1−θ)y) ≤ θ·max x + (1−θ)·max y
  • 좌변이 아니라 “max는 각 원소 이상”이라는 우변 쪽 성질에서 출발한다.
• 행렬 함수
  • tr(AᵀX) + b = Σ Aᵢⱼ Xᵢⱼ + b 는 affine
  • Spectral norm ‖X‖₂ = σmax(X) 는 norm이라 convex. ⭐ 최대 singular value로 이해하면 된다.
  • log det X (X ≻ 0) 는 concave (3.3)

3.3 Extended value, 직선 제한 ✍️

• Extended value: 정의역 밖을 +∞로 둔 함수. 표기를 단순하게 하려는 장치다.
• f가 convex ⟺ 모든 x, v에 대해 g(t) = f(x + tv) 가 convex
  • 다변수 문제를 1변수로 줄인다.
• 판서: g(t) = log det(X + tV) = log det X + Σᵢ log(1 + tλᵢ)
  • λᵢ는 X^(−1/2) V X^(−1/2) 의 고유값
  • 각 항이 t에 대해 concave이므로 log det는 concave

3.4 1차 조건

• 열린 convex 정의역에서 미분 가능할 때: convex ⟺ f(y) ≥ f(x) + ∇f(x)ᵀ(y − x)
• 접선(1차 Taylor 근사)이 전역 하한이다.

3.5 2차 조건 ✍️

• 두 번 미분 가능할 때: convex ⟺ ∇²f(x) ⪰ 0
• ∇²f(x) ≻ 0 이면 strictly convex. 역은 거짓 (반례: x⁴)
• 이차함수 (1/2)xᵀPx + qᵀx + r
  • ∇f = Px + q, ∇²f = P
  • P ⪰ 0 이면 convex
• Least squares ‖Ax − b‖₂²: ∇²f = 2AᵀA ⪰ 0 이므로 항상 convex
• x²/y (y > 0): ∇²f = (2/y³)·wwᵀ ⪰ 0, w = (y, −x)
• Log-sum-exp (zₖ = e^(xₖ))
  • vᵀ∇²f v = [ (Σ zₖvₖ²)(Σ zₖ) − (Σ vₖzₖ)² ] / (Σ zₖ)² ≥ 0
  • 분자가 0 이상인 근거는 Cauchy–Schwarz
• 기하평균 (Π xₖ)^(1/n) 은 concave (같은 방식, 슬라이드만)

3.6 Sublevel set, epigraph

• Sublevel set Cα = { x | f(x) ≤ α }
  • f가 convex이면 Cα는 convex. 역은 거짓
• Epigraph epi f = { (x, t) | f(x) ≤ t }
  • f가 convex ⟺ epi f가 convex set

3.7 Jensen

• f(E z) ≤ E f(z)
• 두 점 정의는 확률이 θ, 1−θ인 특수한 경우다.
• 예: X ~ N(μ, σ²) 이면 e^μ ≤ E[e^X] = e^(μ + σ²/2)

3.8 함수가 convex임을 보이는 3가지 방법

1. 정의 대입 (직선 제한 포함)
2. Hessian ⪰ 0
3. 보존 연산으로 조립

⭐ 교수님: "주로 2, 3번을 활용해서 보인다."

3.9 비음 가중합, 적분, affine 합성

• αf (α ≥ 0), f₁ + f₂, 무한합, ∫ f(x, α) dα 는 convex를 유지한다.
• f(Ax + b) 는 convex
  • 예: log barrier −Σ log(bᵢ − aᵢᵀx), norm 근사오차 ‖Ax − b‖

3.10 Pointwise max ✍️ ⭐

• max{f₁, …, fₘ} 는 convex
• 판서
  • 각 i에 대해 fᵢ(θx + (1−θ)y) ≤ θf(x) + (1−θ)f(y)
  • 모든 i에서 성립하므로 max에서도 성립
• 예
  • Piecewise-linear 함수 maxᵢ(aᵢᵀx + bᵢ)
  • 큰 순서로 r개 성분의 합 = nCr개 선형합의 max
• ⭐ 교수님: "자명해 보이진 않지만 보여야 되는 문제"

3.11 Pointwise supremum

• g(x) = sup_{y ∈ A} f(x, y)
  • 각 y에서 x에 대해 convex이면 g는 convex. y 쪽 조건은 없다.
• 예
  • 가장 먼 점까지의 거리 sup_{y ∈ C} ‖x − y‖
  • Support function sup_{y ∈ C} yᵀx
• λmax(X) = sup_{‖y‖₂ = 1} yᵀXy
  • y를 고정하면 X의 선형식이므로 convex
  • ⭐ "첨자 2는 절대로 빠지면 안 된다."

3.12 Partial minimization ✍️ ⭐

• g(x) = inf_{y ∈ C} f(x, y)
  • f가 (x, y)에 대해 jointly convex이고 C가 convex일 때 convex
• 판서
  • f = xᵀAx + 2xᵀBy + yᵀCy, 블록행렬 [A B; Bᵀ C] ⪰ 0, C ≻ 0
  • y로 미분해서 0 → y = −C⁻¹Bᵀx
  • g = xᵀ(A − BC⁻¹Bᵀ)x 가 convex
  • 따라서 Schur complement A − BC⁻¹Bᵀ ⪰ 0
• ⭐ Schur complement는 "은근히 쓰일 때가 있다."
• 집합까지의 거리 inf_{y ∈ S} ‖x − y‖ 는 S가 convex일 때 convex

3.13 합성 규칙 ⭐

• 스칼라 합성 f = h(g(x)) 가 convex인 두 경우
  • ① g convex, h convex, h̃ 비감소
  • ② g concave, h convex, h̃ 비증가
• 근거: f″ = h″(g)·(g′)² + h′(g)·g″
• 예
  • e^(g(x)): g가 convex이면 convex
  • 1/g(x): g가 concave이고 양수이면 convex
• 일반형 h(g₁, …, gₖ): h가 convex이고, 각 i마다 다음 중 하나가 성립하면 convex
  • gᵢ convex이고 h̃가 i번째 인자에 대해 비감소
  • gᵢ concave이고 h̃가 i번째 인자에 대해 비증가
  • gᵢ affine
• 예
  • log Σ e^(gᵢ): gᵢ가 convex이면 convex
  • p²/q: p가 비음·convex이고 q가 양수·concave이면 convex
• ⭐ "강의 내내 쓰니 외우라"

3.14 구성적 분석, DCP

• 식을 파스 트리로 그린 뒤, 잎(변수·상수)부터 합성 규칙으로 convex / concave / affine을 태그한다.
• 예: (x − y)² / (1 − max(x, y))
  • u²/v 꼴: convex이고 v에 대해 감소
  • u = x − y 는 affine, v = 1 − max(x, y) 는 concave
  • 따라서 convex
• 이 방법은 충분조건일 뿐이다.
  • 예: √(1 + x²) 를 sqrt(1 + square(x)) 로 쓰면 DCP가 거부하지만, norm2([1, x]) 로 쓰면 통과한다.

3.15 함수의 perspective ✍️

• g(x, t) = t·f(x/t), t > 0
• f가 convex이면 g도 convex
• 예: xᵀx/t, 상대 엔트로피 t log t − t log x

3.16 Conjugate

• f*(y) = sup_x ( yᵀx − f(x) )
• f가 convex가 아니어도 f*는 항상 convex (affine 함수들의 sup이므로)
• 예
  • f = −log x: y < 0 이면 f*(y) = −1 − log(−y), 그 외에는 ∞
  • f = (1/2)xᵀQx (Q ≻ 0): f*(y) = (1/2)yᵀQ⁻¹y
• 쓰임: 5장 쌍대(duality)

3.17 Quasiconvex (녹취 불명확)

• 모든 sublevel set이 convex인 함수
  • Quasiconcave: −f가 quasiconvex
  • Quasilinear: 둘 다인 함수
• 예 (슬라이드만)
  • √|x|: quasiconvex
  • ceil(x), log x, linear-fractional: quasilinear
  • x₁x₂ (ℝ₊₊² 위), IRR: quasiconcave
• 수정 Jensen: f(θx + (1−θ)y) ≤ max{f(x), f(y)}
• 1차 조건: f(y) ≤ f(x) 이면 ∇f(x)ᵀ(y − x) ≤ 0
• Quasiconvex 함수의 합은 quasiconvex가 아닐 수 있다.

2.1 Affine set ✍️

• Line: x = θx₁ + (1−θ)x₂, θ ∈ ℝ (내분·외분 모두)
• Affine set: 집합 안 두 점을 지나는 직선 전체가 다시 집합 안에 있는 집합
• 예: { x | Ax = b }
  • 판서: Ax₁ = Ax₂ = b 이면 A(θx₁ + (1−θ)x₂) = θb + (1−θ)b = b
• Linear subspace는 0을 지나야 하지만, affine set은 그럴 필요가 없다.

2.2 Convex set

• Line segment: θ ∈ [0, 1]
• 정의: x₁, x₂ ∈ C 이고 0 ≤ θ ≤ 1 이면 θx₁ + (1−θ)x₂ ∈ C
• 예: 육각형은 convex. 오목한 도형, 경계 일부가 빠진 사각형은 convex가 아니다.

2.3 Convex combination, convex hull

• Convex combination: Σ θᵢxᵢ (θᵢ ≥ 0, Σ θᵢ = 1)
• conv S: S의 모든 convex combination의 집합 = S를 포함하는 가장 작은 convex set
• S가 convex이면 conv S = S

2.4 Convex cone ✍️

• Conic combination: θᵢ ≥ 0 만 요구한다. 합이 1이라는 조건은 없다.
• Convex cone: conic combination이 다시 집합 안에 있는 집합
• 판서: αy₁ + (1−α)y₂ 의 계수 αθᵢ + (1−α)θᵢ′ ≥ 0 이므로 convex이기도 하다.

2.5 Hyperplane, halfspace ✍️ ⭐

• Hyperplane: { x | aᵀx = b }, a ≠ 0 (a는 법선벡터). aᵀ(x − x₀) = 0 으로도 쓴다.
• Halfspace: { x | aᵀx ≤ b }
• Hyperplane: aᵀ(θx₁ + (1−θ)x₂) = θb + (1−θ)b = b
  • θ ∈ ℝ 에서도 성립하므로 affine이면서 convex
• Halfspace: θaᵀx₁ + (1−θ)aᵀx₂ ≤ b
  • θ ≥ 0, 1−θ ≥ 0 일 때만 성립하므로 convex이지만 affine은 아니다.
• ⭐ 교수님이 이 증명 직전에 "연습 시험에 쓸 수도"라고 언급

2.6 Ball, ellipsoid ✍️

• Ball: { x | ‖x − xc‖₂ ≤ r } = { xc + ru | ‖u‖₂ ≤ 1 } (xc는 중심)
• 임의의 norm ball도 convex:
  • ‖θx₁ + (1−θ)x₂ − xc‖ ≤ θ‖x₁ − xc‖ + (1−θ)‖x₂ − xc‖ ≤ r
  • 중심 xc를 θxc + (1−θ)xc 로 쪼갠 뒤 triangle → homogeneity 순서로 쓴다.
  • θ ≥ 0 이라 절댓값을 쓸 필요가 없다.
• 1-norm ball은 다이아몬드, ∞-norm ball은 정사각형
• Ellipsoid: { x | (x − xc)ᵀ P⁻¹ (x − xc) ≤ 1 }, P는 대칭 양정치(S₊₊ⁿ)
  • 또는 { xc + Au | ‖u‖₂ ≤ 1 }
  • 판서: P = AAᵀ, u = A⁻¹(x − xc) 로 두면 두 표현이 같다.

2.7 Norm, norm cone

• Norm 조건
  • ‖x‖ ≥ 0, x = 0 일 때만 0
  • ‖tx‖ = |t|‖x‖
  • ‖x + y‖ ≤ ‖x‖ + ‖y‖
• Norm cone: { (x, t) | ‖x‖ ≤ t }
  • 2-norm이면 second-order cone(아이스크림 콘)
  • t를 고정한 단면이 반지름 t인 원

2.8 Polyhedron

• { x | Ax ⪯ b, Cx = d } = 유한 개 halfspace와 hyperplane의 교집합 → convex (2.11)

2.9 PSD cone ✍️

• Sⁿ: 대칭행렬, S₊ⁿ: PSD (zᵀXz ≥ 0), S₊₊ⁿ: PD (z ≠ 0 이면 zᵀXz > 0)
• 판서: zᵀ(θ₁X₁ + θ₂X₂)z = θ₁zᵀX₁z + θ₂zᵀX₂z ≥ 0 → convex cone
• 행렬도 점처럼 볼록성을 따질 수 있다.

2.10 집합이 convex임을 보이는 3가지 방법

1. 정의 대입 (아주 단순한 집합에만)
2. convex function 이용 (sublevel set, 3장)
3. 단순한 convex set에 보존 연산 적용 ← 주로 이 방법

2.11 교집합 ✍️

• 임의 개수의 convex set의 교집합은 convex
  • 두 점이 교집합 안 → 각 Cᵢ 안 → 선분도 각 Cᵢ 안 → 교집합 안
• 예: { x | |p(t)| ≤ 1, |t| ≤ π/3 }, p(t) = Σₖ xₖ cos kt
  • t를 고정하면 slab(halfspace 2개)
  • 모든 t에 대한 slab의 교집합이므로 convex

2.12 Affine mapping ✍️ ⭐

• f(x) = Ax + b 이면 상 f(S)와 역상 f⁻¹(C) 모두 convex를 유지한다.
• 판서:
  • yᵢ = f(xᵢ) 인 xᵢ ∈ S 가 존재
  • θy₁ + (1−θ)y₂ = f(θx₁ + (1−θ)x₂)
  • 괄호 안의 점이 S 안에 있다.
• ⭐ 교수님: "그 점이 S에 속하는 것까지 써야 명확하다."
• 예: scaling·translation, 좌표 projection. cᵀS = { cᵀx | x ∈ S } 는 구간
• LMI 해집합 { x | x₁A₁ + … + xₘAₘ ⪯ B }
  • 사상 x ↦ B − Σ xᵢAᵢ 에 대한 PSD cone의 역상
• Hyperbolic cone { x | xᵀPx ≤ (cᵀx)², cᵀx ≥ 0 }
  • 사상 x ↦ (P^(1/2)x, cᵀx) 에 대한 second-order cone의 역상
  • 교수님은 교집합으로 설명했지만, y ≤ (cᵀx)² 쪽 집합이 convex가 아니다. 답안은 역상 논리로 쓰는 게 안전하다.

2.13 Perspective, linear-fractional

• Perspective: P(x, t) = x/t, t > 0
  • 한 점(카메라)에서 본 그림자처럼, 같은 반직선 위의 점이 한 점으로 모인다.
• Linear-fractional: f(x) = (Ax + b)/(cᵀx + d), 분모 > 0
• 둘 다 convex set의 상과 역상이 convex다.

2.14 Proper cone, generalized inequality ✍️

• Proper cone = convex cone + closed + solid(내부가 비지 않음) + pointed(직선을 포함하지 않음)
• 예
  • ℝ₊ⁿ
  • S₊ⁿ
  • [0, 1] 위 비음 다항식의 계수 집합. 판서: θ₁p₁(t) + θ₂p₂(t) ≥ 0
• x ⪯ₖ y ⟺ y − x ∈ K, strict는 y − x ∈ int K
  • ℝ₊ⁿ 이면 성분별 부등식, S₊ⁿ 이면 행렬 부등식. 이 두 경우는 첨자 K를 생략한다.
• 실수 부등식과 비슷한 성질: x ⪯ₖ y, u ⪯ₖ v 이면 x + u ⪯ₖ y + v

2.15 Separating, supporting hyperplane (개론)

• Separating: C, D가 nonempty·disjoint·convex이면 a ≠ 0, b가 존재해서
  • C 쪽은 aᵀx ≤ b, D 쪽은 aᵀx ≥ b
  • Strict 분리에는 추가 조건이 필요 (예: C가 closed, D가 한 점)
• Supporting hyperplane: 경계점 x₀ 에서 모든 x ∈ C 에 대해 aᵀx ≤ aᵀx₀
  • C가 convex이면 모든 경계점에서 존재

1.1 표준형 

1.2 x가 나타내는 것

• 행동: 포트폴리오, 항공기 제어면, 스케줄·할당, 자원할당(전력·주파수, AI 토큰 스케줄). 목적은 비용, 목표와의 편차, 위험, 연료.
• 모델 파라미터: 목적 = 예측오차(loss) + 복잡도 정규화. 제약으로 넣을 수도 있다.
• 최악 경우 분석: 파라미터를 상대가 고른다고 보고 -f_0 를 최소화. 최악값이 견딜 만하면 안전. 통신에서 오류율 상한 보장이 예.
• 최적화 기반 모델: 개인의 효용 최대화, 생물의 번식 성공, 세포 성장, 회로 전력 최소. 거친 모델이지만 잘 맞는 경우가 많다.
• ⭐ 최적화 모델은 현장에 그대로 쓰려고 만드는 게 아니라 직관과 경향을 얻으려고 만든다.

1.3 사용 방식 

• x를 어떻게 고를지 쓰지 않는다. 원하는 것을 문제로 쓰고, 알고리즘이 x를 고르게 한다.

1.4 풀 수 있는가 

• 일반 문제는 대부분 정확히 못 푼다 → 근사. 예외가 convex optimization (LP, QP 포함).
• Local 방법: 큰 문제도 가능(신경망 학습), 초기점·튜닝 필요, 얼마나 차선인지 알 수 없음.
• Global 방법: 진짜 최적, 최악 복잡도는 문제 크기에 지수적.

1.5 Convex optimization

1.6 솔버, CVXPY, 역사

• Interior-point: 수만 변수까지. First-order: 더 큰 문제. 초기점·튜닝이 필요 없다.
• 역행렬 계산은 O(n^3) 이라 큰 LP에서는 피한다.
• CVXPY: 변수 정의 → 목적·제약 → Problem(...).solve().
• 솔버는 갖다 쓰면 된다.
• 역사: 이론 1900–1970 → simplex 1947 → interior-point 1980–90년대 → 2000년대 대규모 방법. 응용은 OR → 공학(제어·신호·통신·회로) → ML·통계·금융.

2.1 서론

• ISA(Instruction Set Architecture) = 컴퓨터(정확히는 CPU)가 이해하는 명령어의 집합(레퍼토리). "이번 시험에 냄." 교과서 앞의 그린 카드 = ARM의 ISA.
• ARM = Advanced RISC Machine(ARM Holdings, 영국). RISC = Reduced Instruction Set Computing vs CISC = Complex Instruction Set Computing(Intel x86). Reduced는 CISC 대비 상대적 표현.
• ARMv8 = 64비트, v7까지 32비트. 임베디드 코어 시장 대부분.
• LEGv8 = ARMv8의 부분집합(교육용), LEG = Less Extrinsic Garrulity. 시험에서도 LEGv8 기준.
• word = 32비트(4바이트), doubleword = 64비트(8바이트). byte 1, halfword 2 — 시험에서 안 알려줌.

2.2 하드웨어 연산

• 산술 명령 = 피연산자 3개(소스 2 + 목적지 1): ADD a, b, c → a = b + c.
• 설계 원칙 1: Simplicity favors regularity (규칙성 → 구현 단순 → 저비용 고성능).
• 용어: operation(연산, OP = operation) + operand(피연산자). 연산 종류 = 산술(arithmetic) · 논리(logical) · 조건/분기(branch) · 메모리(load/store).

2.3 피연산자

레지스터 (32 × 64비트)

레지스터 용도

• W0~W30 = X의 하위 32비트. 레지스터 용도 규약(X9~ temporary, X19~ saved)은 시험에서 주어짐. XZR = 11111 = 31은 암기.
• 설계 원칙 2: Smaller is faster (레지스터 수가 적을수록 빠름. 메모리는 수백만 위치).
• 레지스터가 메모리보다 빠르므로 컴파일러는 변수를 최대한 레지스터에.

🆕 예: f = (g + h) − (i + j), f~j = X19~X23

ADD X9,  X20, X21    // t0 = g + h
ADD X10, X22, X23    // t1 = i + j
SUB X19, X9,  X10    // f = t0 - t1

메모리 피연산자

• 배열·구조체·동적 데이터는 메모리. 연산하려면 load → 연산 → store.
• 메모리는 바이트 주소. LEGv8은 명령어와 스택을 제외하면 정렬(alignment)을 요구하지 않음.
• Big endian = 최상위 바이트(MSB 쪽)를 가장 낮은 주소에. Little endian = 최하위 바이트를 가장 낮은 주소에.
• 예: doubleword ABCDEF0123456789를 16번지(16~23)에 저장 → big endian이면 16번지 = AB, little endian이면 16번지 = 89.

예: A[12] = h + A[8], h = X21, A 시작 주소 = X22

LDUR X9, [X22, #64]   // A[8]: 8 × 8바이트 = 64. U = unscaled
ADD  X9, X21, X9
STUR X9, [X22, #96]   // A[12]: 12 × 8 = 96

즉치 피연산자

• ADDI X22, X22, #4. 작은 상수가 흔하므로 load 없이 명령어에 넣음.
• 강의자료의 표기: "Design Principle 3: Make the common case fast". 교과서의 설계 원칙 3은 "좋은 설계는 적당한 절충이 필요하다"(p89, 명령어 형식). 둘 다 알아둘 것.

2.4 부호 있는 수와 부호 없는 수

• Unsigned n비트 범위: 0 ~ 2^n − 1 (32비트: 0 ~ 4,294,967,295).
• 2's complement n비트 범위: −2^(n−1) ~ 2^(n−1) − 1 (32비트: −2,147,483,648 ~ 2,147,483,647). MSB = 부호 비트.
• 특수 값: 0 = 000…0, −1 = 111…1, 최소 = 100…0, 최대 = 011…1. 모두 1인 비트 = unsigned에서는 최댓값("외워요").
• −(−2^(n−1))은 표현 불가. 음이 아닌 수는 signed·unsigned 표현이 같음.
• 부호 반전 = 보수 + 1. 예: +2 = 0…010 → −2 = 1…101 + 1 = 1…110.
• 부호 확장(Sign extension) = 부호 비트를 왼쪽으로 복사. 8→16비트: +2 = 0000 0010 → 0000 0000 0000 0010, −2 = 1111 1110 → 1111 1111 1111 1110.
• LDURSB = 부호 확장해 load, LDURB = 0으로 확장해 load.

2.5 명령어의 컴퓨터 내부 표현

• 명령어 = 32비트 고정 길이 이진 코드(기계어). 형식은 적게, opcode로 구분.
• 16진수 한 자리 = 4비트. 예: eca8 6420 = 1110 1100 1010 1000 0110 0100 0010 0000.

형식 필드 (비트 수) 쓰임새

• Rn = 첫 번째 소스, Rm = 두 번째 소스, Rd = 목적지, shamt = 시프트 양, Rt = load의 목적지/store의 소스.
• opcode : ADD 1112, SUB 1624, ADDI 580, SUBI 836, LDUR 1986, STUR 1984.

인코딩 예

ADD X9, X20, X21
opcode 1112 | Rm 21 | shamt 0 | Rn 20 | Rd 9
10001011000 | 10101 | 000000 | 10100 | 01001
= 1000 1011 0001 0101 0000 0010 1000 1001 = 0x8B150289

• 내장 프로그램: 명령어도 데이터처럼 이진수로 메모리에 저장 → 프로그램이 프로그램을 다룸(컴파일러, 링커). Binary compatibility = 호환성(암기 지시).

2.6 논리 연산 명령어

연산 C LEGv8 쓰임새

• 예: X19 = 9 → LSL X11, X19, #4 → X11 = 0x90 = 144. 시프트는 R 형식의 shamt 사용.

2.7 판단을 위한 명령어

• CBZ reg, L1(reg == 0이면 분기), CBNZ reg, L1(reg ≠ 0이면), B L1(무조건). 슬라이드 제목은 conditional operation이지만 실체는 branch.

if–else: f~j = X19~X23

// if (i == j) f = g + h; else f = g - h;
      SUB  X9, X22, X23    // X9 = i - j
      CBNZ X9, Else        // i != j 이면 Else
      ADD  X19, X20, X21   // f = g + h
      B    Exit
Else: SUB  X19, X20, X21   // f = g - h
Exit:

while: i = X22, k = X24, save 시작 주소 = X25

// while (save[i] == k) i += 1;
Loop: LSL  X10, X22, #3    // X10 = i * 8
      ADD  X10, X10, X25   // X10 = &save[i]
      LDUR X9, [X10, #0]   // X9 = save[i]
      SUB  X11, X9, X24    // save[i] - k
      CBNZ X11, Exit
      ADDI X22, X22, #1    // i = i + 1
      B    Loop
Exit:

• Basic block = 중간에 분기가 없고(끝 제외) 분기 대상도 없는(시작 제외) 명령어 묶음. 컴파일러 최적화 단위.

조건 코드 (NZCV) — S 접미 명령(ADDS, ADDIS, ANDS, ANDIS, SUBS, SUBIS)이 설정

• N(negative): 결과 MSB = 1 / Z(zero): 결과 = 0 / C(carry): MSB에서 올림 / V(overflow): 오버플로.

비교 signed unsigned

// if (a > b) a += 1;   a = X22, b = X23
      SUBS X9, X22, X23
      B.LE Exit
      ADDI X22, X22, #1
Exit:

• X22 = 1111…1111, X23 = 0000…0001 → signed면 −1 < +1, unsigned면 4,294,967,295 > 1.

2.8 하드웨어의 프로시저 지원

호출 6단계

1. 인자를 X0~X7에 넣음(caller)
2. 프로시저로 제어 이동(BL)
3. 프로시저용 저장공간(지역변수) 확보
4. 프로시저 연산 수행
5. 결과를 caller가 읽을 레지스터에(기본 X0)
6. 호출한 곳으로 복귀(X30의 주소)

• Argument(부를 때 넘기는 값, 예 1·2·3·4) vs Parameter(정의에 적힌 이름, 예 g·h·i·j). 교수님이 구분을 강조.
• BL label: 다음 명령어 주소(PC + 4)를 X30(LR)에 넣고 분기. BR LR: LR의 주소를 PC로 복사(switch–case의 계산된 분기에도 사용). LR과 X30은 같은 레지스터.
• B vs BL vs BR: B = 레이블로 그냥 분기, BL = 복귀 주소를 저장하고 분기, BR = 레지스터 안 주소로 분기.

호출하는 쪽 예 : a = leaf_example(1, 2, 3, 4); a = X21, 리턴 = X0

ADDI X0, XZR, #1
ADDI X1, XZR, #2
ADDI X2, XZR, #3
ADDI X3, XZR, #4    // 여기까지 1단계
BL   leaf_example   // 2단계, LR = 다음 줄 주소
ADD  X21, XZR, X0   // 리턴값 받기

• BL에 들어가는 주소는 (목표 주소 − 현재 주소) / 4 만큼의 PC-relative 오프셋.

Leaf procedure — g~j = X0~X3, f = X19, 임시 X9·X10

leaf_example:
    SUBI SP, SP, #24       // 스택 3칸 확보
    STUR X10, [SP, #16]    // X10, X9, X19 저장
    STUR X9,  [SP, #8]
    STUR X19, [SP, #0]
    ADD  X9,  X0, X1       // g + h
    ADD  X10, X2, X3       // i + j
    SUB  X19, X9, X10      // f
    ADD  X0,  X19, XZR     // 리턴값 = f
    LDUR X10, [SP, #16]    // 복원
    LDUR X9,  [SP, #8]
    LDUR X19, [SP, #0]
    ADDI SP, SP, #24       // 스택 반납
    BR   LR

• 규약: X9~X17 temporary = callee가 보존 안 함, X19~X28 saved = 쓰면 callee가 저장·복원. temporary는 C에 없는 임시값, saved는 C 변수.

Non-leaf procedure — 중첩 호출이라 복귀 주소와 호출 후 필요한 인자·임시값을 스택에 저장, 호출 후 복원.

// int64 fact(int64 n) { if (n < 1) return 1; else return n * fact(n - 1); }
// 인자 n = X0, 결과 = X1 (이 예에서는 X1, 시험에서도 알려줌)
fact: SUBI  SP, SP, #16
      STUR  LR, [SP, #8]     // 복귀 주소 저장
      STUR  X0, [SP, #0]     // n 저장
      SUBIS XZR, X0, #1      // n - 1 비교 (교과서 p110 ZXR → XZR)
      B.GE  L1               // n >= 1 이면 L1
      ADDI  X1, XZR, #1      // return 1
      ADDI  SP, SP, #16
      BR    LR
L1:   SUBI  X0, X0, #1       // n - 1
      BL    fact
      LDUR  X0, [SP, #0]     // n 복원
      LDUR  LR, [SP, #8]     // 복귀 주소 복원
      ADDI  SP, SP, #16
      MUL   X1, X0, X1       // n * fact(n-1)
      BR    LR

• 스택 그림은 위가 높은 주소인지 낮은 주소인지 문제마다 확인("거꾸로 그릴 때도 있음").

메모리 배치

• Text(프로그램 코드 = 기계어 명령어, 저주소) → Static data(전역·static 변수, 상수 배열·문자열) → Heap(malloc, Java new, 위로 자람) ↔ Stack(지역변수, 고주소에서 아래로).
• Dynamic data = Heap + Stack.
• 실행 파일에는 명령어 + static data만 있고, 스택·힙은 로딩되어 실행될 때 생김.
• 스택 = 지역변수를 위한 메모리 영역, 함수를 부를 때마다 커지고 끝나면 줄어듦. 메모리에 올라온 프로그램 = 프로세스
• Pitfall: 함수가 끝난 뒤 지역변수(스택) 포인터를 계속 쓰면 무효.

2.9 문자와 문자열 

• ASCII(American Standard Code for Information Interchange) 128자(그래픽 95 + 제어 33), Latin-1 256자, Unicode 32비트(UTF-8·UTF-16 가변 길이).
• LDURB Rt, [Rn, offset](바이트 load), STURB(오른쪽 1바이트만 저장), LDURH/STURH(16비트 하프워드).

2.10 큰 수치와 주소를 위한 주소지정

• 대부분 상수는 12비트로 충분. 큰 상수는 MOVZ(나머지 0) + MOVK(나머지 유지), 시프트 #0·#16·#32·#48.

MOVZ X9, #255, LSL #16   // 0x0000_0000_00FF_0000
MOVK X9, #255, LSL #0    // 0x0000_0000_00FF_00FF

• B-type: B 10000 → opcode 5(6비트) + address 26비트. CB-type: CBNZ X19, Exit → opcode 181(8비트) + address 19비트 + Rt 5비트.
• PC-relative: 목표 주소 = PC + 4 × offset. 명령어가 4바이트(word)라 ×4.
• 주소지정 방식 4가지(그림 2.19 = 강의 L2 p51): ① Immediate ② Register ③ Base(레지스터 + 주소 필드) ④ PC-relative. 🆕 그림 오류: ③ 화살표 출발점은 Address(op 삭제), ④ Memory 안 상자는 Doubleword가 아니라 Word.

기계어 해독

0x8B0F0013 = 1000 1011 0000 1111 0000 0000 0001 0011
= 10001011000 | 01111 | 000000 | 00000 | 10011
= opcode 1112(ADD) | Rm 15 | shamt 0 | Rn 0 | Rd 19
= ADD X19, X0, X15

2.11 병렬성과 명령어: 동기화 🆕

• Data race: 두 프로세서가 메모리를 공유하며 동기화하지 않으면 결과가 접근 순서에 따라 달라짐 → 원자적(atomic) read/write 하드웨어 지원 필요.
• LDXR(Load exclusive register) → STXR(Store exclusive register)를 같은 주소에 쌍으로 사용. 사이에 그 주소가 바뀌면 store 실패. 사이에는 레지스터 명령만.
• STXR의 상태 레지스터: 성공 0 / 실패 1

// atomic swap: X23 <-> [X20]
again: LDXR X10, [X20, #0]
       STXR X23, X9, [X20]   // X9 = status
       CBNZ X9, again
       ADD  X23, XZR, X10    // X23 = 읽은 값

// lock
       ADDI X11, XZR, #1     // 잠금 값
again: LDXR X10, [X20, #0]   // lock 읽기
       CBNZ X10, again       // 0이 될 때까지
       STXR X11, X9, [X20]   // 저장 시도
       CBNZ X9, again        // 실패하면 다시
unlock: STUR XZR, [X20, #0]  // lock 해제

• 비유: 물건 100개 중 5명만 가져갈 때, 남은 개수를 보는 것 = LDXR, 채 가는 것 = STXR.
• 연습문제 2.38·2.39와 같은 유형(같은 문제 공개 예정). 어려운 버전은 안 냄. LDUR(unscaled)과 LDXR(exclusive) 구분.

2.12 프로그램 번역과 실행

• C → 컴파일러 → 어셈블리 → 어셈블러 → 목적 모듈 → 링커 → 실행 파일 → 로더 → 메모리.
• gcc 옵션: -E(.i 전처리), -S(.s 컴파일만), -c(.o 어셈블까지), -static(정적 링크).
• 목적 파일: Header / Text segment / Static data segment / Relocation info / Symbol table / Debug info.
• 링커: ① 세그먼트 병합 ② 레이블 주소 결정 ③ 위치 의존·외부 참조 수정. 가상 메모리 덕에 절대 주소로 로드 가능.
• 로더: ① 헤더로 크기 확인 ② 가상 주소 공간 생성 ③ text·데이터 복사 ④ 스택에 인자 ⑤ 레지스터 초기화(SP·FP) ⑥ startup 루틴 → main 호출, 끝나면 exit.
• Static vs Dynamic linking(과제로 낸 내용, 10/14 재강조): Dynamic = 라이브러리를 호출될 때만 링크·로드, 재배치 가능 코드 필요, 이미지 비대화 방지, 새 버전 자동 반영. DLL = Dynamically Linked Library.
• Lazy linkage(간접 테이블·stub) 세부와 Java(바이트코드·JVM·JIT) 경로는 "외울 필요 없음".

x86 명령어와 오류·함정

• x86 = CISC. 하위 호환성을 지키며 명령어가 계속 늘어남: 8080(1974, 8비트) → 8086(1978, 16비트) → 80386(32비트, IA-32) → Pentium(MMX, SSE) → AMD64(2003, 64비트) → AVX. "Technical elegance ≠ market success."
• ARM은 비교적 늦게(80~90년대) 나왔고 명령어를 최소화 → 저전력·병렬화에 유리.
• Fallacy: 강력한 명령어 = 고성능(아님, 복잡하면 단순 명령까지 느려짐) / 고성능을 위해 어셈블리 작성(아님, 컴파일러가 더 잘함) / 하위 호환 = ISA 불변(아님, 계속 늘어남).
• Pitfall: 연속 워드는 연속 주소가 아님(1이 아니라 워드 크기만큼 증가) / 반환 후 지역변수 포인터 사용.

Lecture 2a — AI를 위한 명령어 (10% 파트)

• 형 변환 비용: 부호 확장·BF16→FP32 = 배선만 / FP16→FP32 = 덧셈기+시프터 / FP4→FP16 = LUT(Look-Up Table)+곱셈기. 4비트 가중치: shift·mask → LUT → scale 곱 → MAC.
• Overflow 대응 4가지: wrap(ADD) / flag(ADDS → NZCV) / exception(LEGv8만, 실제 ARMv8 없음) / saturate(SQADD). INT8 120 + 30 → wrap −106, saturate 127. SIMD는 lane별 플래그·예외 없음 → saturate 또는 넓은 누산기.
• 레지스터 파일: X 31 × 64 = 1,984비트, V(V0~V31) 32 × 128 = 4,096비트(Q·D·S·H·B, lane 16B·8H·4S·2D). 개수 그대로, 폭만 늘려 필드 5비트 유지 = DP2.
• SIMD(Single Instruction, Multiple Data). SDOT Vd.4S, Vn.16B, Vm.16B = 곱셈 16개(스칼라 32 연산 대체). int8×int8 최대 16,384 → int16에는 2개째에 overflow, int32에는 약 131,000개.
• SVE(Scalable Vector Extension) 128~2048비트, WHILELT로 꼬리 루프 없음(n = 102: 고정 SIMD 25회 + 꼬리 2회 vs SVE 26회). SME = 2D 타일 ZA. x86 대응: SDOT↔VNNI, SVE↔AVX-512, SME↔AMX.
• NCHW 주소 = ((n·C+c)·H+h)·W+w, NHWC = ((n·H+h)·W+w)·C+c. 마지막 글자가 연속 축.
• NVIDIA 경로: CUDA C++ → nvcc → PTX(Parallel Thread eXecution), 가상 ISA·공개 → ptxas → SASS, 실제 기계어·비공개. Fat binary + 드라이버 JIT(Just-In-Time). Fallback = 최적 경로가 없을 때 느리지만 동작하는 경로("외워야").
• IR(Intermediate Representation), LLVM(N×M → N+M: 언어 4·HW 4이면 16 → 8), MLIR(Multi-Level IR). Fusion은 고수준, Tiling은 중간 수준.
• "커널"의 3가지 뜻: OS 커널(프로그램) / 계산 커널(함수) / 합성곱 커널(데이터).
• ISA = HW–SW 계약, 공개 범위도 설계 결정

1.1 서론 — 컴퓨터 분류

• 개인용 컴퓨터(PC): 낮은 가격, 단일 사용자, 성능 대 가격.
• 서버: 네트워크 기반, 대용량·고성능·고신뢰성. 슈퍼컴퓨터: 최고 성능이지만 시장 비중은 작음.
• 임베디드: 다른 시스템 안에 들어간 컴퓨터(휴대폰, 자동차, 냉장고). 전력·성능·비용 제약이 가장 엄격.
• 성능을 정하는 것: 알고리즘(연산 수) → 언어·컴파일러·구조(연산당 명령어 수) → 프로세서·메모리(명령어 실행 속도) → I/O·OS(I/O 속도).

1.2 8가지 위대한 아이디어

1. Moore의 법칙을 고려한 설계: 트랜지스터 수가 약 2년마다 2배. 설계 완료 시점의 기술을 예상.
2. 추상화로 설계 단순화: 하위 세부를 숨김.
3. 자주 생기는 일을 빠르게(Make the common case fast): 흔한 경우 개선이 효과 큼.
4. 병렬성을 통한 성능 개선
5. 파이프라이닝을 통한 성능 개선: 단계별 작업 중첩.
6. 예측을 통한 성능 개선: 예측 적중률이 높고 복구 비용이 작을 때.
7. 메모리 계층구조: 빠르고 작은 캐시 + 느리고 큰 DRAM.
8. 여유분을 이용한 신뢰성 개선(Dependability via redundancy).

1.3 프로그램 밑의 세계

• 응용 SW → 시스템 SW(운영체제, 컴파일러) → 하드웨어.
• 코드 수준 (암기): C(고급 언어) → 컴파일러 → 어셈블리 → 어셈블러 → 기계어(이진수).
• 어셈블리 ↔ 기계어는 1:1 규칙 변환. 컴파일러는 품질에 따라 명령어 수(IC)가 달라지는 '고지능' 작업.
• 시험 팁: 컴파일러와 어셈블러가 같이 보기에 나오면, 기계어로 바꾸는 것은 어셈블러. 실무에서는 gcc 같은 '컴파일러 도구'가 두 단계를 모두 부름.
• 내장 프로그램 개념: 명령어와 데이터를 모두 메모리에 숫자로 저장.

1.4 케이스를 열고

• 컴퓨터 5대 요소 (암기 지시): 입력 · 출력 · 메모리 · 데이터패스 · 제어. 프로세서 = 데이터패스 + 제어.
• CPU 안의 핵심 두 부분: ALU(Arithmetic Logic Unit) + 제어 장치(Control Unit). ALU full name을 못 쓰면 "마이너스 100점".
• 폰 노이만 구조(1952): 오늘날 PC 구조와 같은 틀.
• 메모리: 주메모리 DRAM(휘발성), 캐시 SRAM(빠름). 보조기억장치: 하드디스크·플래시(비휘발성).
• ISA(Instruction Set Architecture): 하드웨어–소프트웨어 인터페이스. ABI = ISA 사용자 부분 + OS 인터페이스.

1.5 프로세서와 메모리 생산 기술

• 기술 추이(상대 성능/비용): 진공관(1951) 1 → 트랜지스터(1965) 35 → IC(1975) 900 → VLSI(1995) 2,400,000 → ULSI(2013) 2,500억.
• 실리콘 잉곧 → 웨이퍼 → 패터닝 → 다이 절단 → 패키징. 수율 = 양호 다이 / 전체 다이.
• 예: Core i7 웨이퍼 300 mm, 280칩, 32 nm.

1.6 성능

정의

• 응답시간(Response time) vs 처리량(Throughput). Performance = 1 / Execution time.
• "X가 Y보다 n배 빠르다" = Time_Y / Time_X = n. 예: A 10 s, B 15 s → 15/10 = A가 1.5배 빠름. 방향을 거꾸로 쓰는 선배가 많았다고 경고.
• Elapsed time(I/O·OS·대기 포함 전체) vs CPU time(user CPU time + system CPU time).
• Clock period 250 ps = 250×10^−12 s ↔ Clock rate 4.0 GHz = 4.0×10^9 Hz.

CPU 성능식 (Iron Law)

CPU Time = CPU Clock Cycles × Clock Cycle Time = CPU Clock Cycles / Clock Rate
Clock Cycles = IC × CPI
CPU Time = IC × CPI × Clock Cycle Time = IC × CPI / Clock Rate

• IC(Instruction Count): 프로그램·ISA·컴파일러가 결정. CPI(Clock cycles Per Instruction): CPU 하드웨어가 결정, 명령어별 CPI가 다르면 instruction mix에 좌우됨. CPI는 Linux 도구에서도 자주 보는 필수 용어.
• 가중 평균 CPI:

Clock Cycles = Σ (CPI_i × IC_i)
CPI = Σ CPI_i × (IC_i / IC)      ← IC_i/IC = relative frequency

교과서·강의 예제 3개 (그대로 출제 유형)

1. Clock rate: A는 2 GHz에서 10 s. B는 6 s가 목표이고 클럭 사이클이 1.2배로 늘어남 → Cycles_A = 10 s × 2 GHz = 20×10^9 → Clock_B = 1.2 × 20×10^9 / 6 s = 4 GHz.
2. CPI 비교(같은 ISA): A(250 ps, CPI 2.0) → I × 500 ps, B(500 ps, CPI 1.2) → I × 600 ps → A가 1.2배 빠름.
3. 명령어 클래스 A·B·C의 CPI = 1·2·3:

시퀀스 A·B·C 개수 IC Clock cycles 평균 CPI

• Sequence 3은 C = 메모리 접근(LDUR/STUR 4개, 느림), B = 산술(ADD·LSL), A = 분기(BR)로 놓고 만든 예. 메모리 접근이 많을수록 CPI가 커짐.
• 교훈: IC가 적다고 빠른 게 아님(Sequence 2는 IC가 더 많지만 cycles가 더 적음).

Performance Summary — 무엇이 무엇에 영향을 주나

요인 IC CPI Clock cycle time (Tc)

• ISA가 다르면 IC 자체가 다름: 숫자 5개 더하기는 x86(CISC)이면 1줄, ARM(RISC)이면 2개씩 더하는 명령만 있어 여러 줄.
• ARM = 임베디드·모바일·라즈베리파이·Physical AI, x86 = PC·클라우드 서버.

1.7 전력 장벽

Energy ∝ 1/2 × C × V²                (단위 J)
Power  ∝ 1/2 × C × V² × Frequency    (단위 W = J/s)

• 단위: 에너지 J, 파워 W. 파워를 시간에 대해 적분하면 에너지, 에너지를 시간으로 나누면 파워. "맨날 틀린다"고 강조.
• 전력은 주파수에 선형, 전압에 제곱 비례
• 지난 20년 CMOS: 클럭 ×1000, 전압 5 V → 1 V로 낮춰 전력 증가를 ×30으로 억제.
• 예제: 새 CPU가 커패시턴스 0.85배, 전압 15% · 주파수 15% 감소 →

P_new / P_old = 0.85 × 0.85² × 0.85 = 0.85⁴ ≈ 0.52

• Power wall: 전압을 더 못 낮추고 열을 더 못 빼냄 → 클럭으로 성능 올리는 길이 막힘.

1.8 단일프로세서에서 멀티프로세서로

• 단일 프로세서 성능은 전력, 명령어 수준 병렬성(ILP), 메모리 지연에 막힘.
• 멀티코어 = 칩 하나에 프로세서 여러 개. 프로그래머가 명시적 병렬 프로그래밍을 해야 함(부하 분산, 통신·동기화 최적화).
• ILP는 하드웨어가 알아서 하고 프로그래머에게 숨겨짐. 멀티코어 = ALU 등 연산 장치가 여러 개.

1.9 실례: Intel Core i7 벤치마킹

• SPEC(Standard Performance Evaluation Corp.) CPU: 실제 워크로드를 대표하는 프로그램 묶음. CINT(정수)·CFP(부동소수점).
• 측정: 오래된 참조 기계 대비 실행시간 비율 → 비율들의 기하평균(ⁿ√Π ratio_i). 산술평균이 아닌 이유 = 비율의 평균이라서.
• SPECpower_ssj2008(ssj_ops/W, 부하별 전력 대비 성능)

1.10 오류 및 함정

• Pitfall — Amdahl의 법칙: 일부만 개선하고 전체가 그만큼 빨라지길 기대하는 것.

T_improved = T_affected / improvement factor + T_unaffected
예: 100 s 중 곱셈 80 s. 전체 5배(20 s)를 원하면 80/n + 20 = 20 → 불가능

• Corollary: make the common case fast.
• Fallacy — 한가할 때는 전력을 적게 쓴다: i7은 부하 100% 258 W, 50% 170 W(66%), 10% 121 W(47%). Google 데이터센터는 대부분 10~50% 부하.
• Pitfall — MIPS를 성능 지표로 쓰기: MIPS(Millions of Instructions Per Second).

MIPS = IC / (Execution time × 10⁶) = Clock rate / (CPI × 10⁶)

• 문제점: ISA 차이 무시, 명령어 복잡도 차이 무시, 같은 CPU도 프로그램마다 CPI가 다름.

1.11 결론

• 비용 대비 성능은 기술 발전으로 계속 개선. HW·SW 모두 계층적 추상화.
• ISA = 하드웨어/소프트웨어 인터페이스. 실행 시간이 가장 좋은 성능 척도. 전력이 제한 요인 → 병렬성으로 성능 개선.

Lecture 1a — Top-Level View (기능과 연결)

명령어 사이클 = Fetch + Execute

• PC(Program Counter): 다음에 가져올 명령어의 주소. 가져온 뒤 증가(따로 지시가 없으면).
• IR(Instruction Register): 가져온 명령어가 들어가는 곳. AC(Accumulator): 임시 저장(데이터 버퍼, MBR 역할).
• PC·IR은 "다 외워야 하는" 항목.

예제 컴퓨터 (슬라이드 p4~5)

• 명령어 16비트 = OpCode 4비트 + Address 12비트. 정수 = Sign 1비트 + Magnitude 15비트.
• OpCode: 0001 Load AC, 0010 Store AC, 0101 Add to AC. 16진수 한 자리 = 4비트.
• 추론: PC = 300 → 300~302번지 = 명령어, 940~941번지 = 데이터. PC에 데이터 주소를 넣으면 엉뚱한 명령을 실행해 죽음(바이러스가 노리는 곳).
• 홀수 step = fetch, 짝수 step = execute. Step 4 = 메모리→AC (Load), Step 6 = AC→메모리 (Store).
• Load = 메모리 → 레지스터(Read), Store = 레지스터 → 메모리(Write). 모두 CPU 입장.
• fetch가 따로 있는 이유: PC를 바꾸면 분기·함수 호출·루프가 가능해짐.

버스

• Bus = 두 개 이상의 장치를 잇는 통신 경로(보통 broadcast, 여러 채널 묶음). 예: 32비트 데이터 버스 = 1비트 채널 32개.
• 시스템 버스 3종: Data / Address / Control(Read·Write 신호 등).
• Single bus 문제: 장치가 많으면 전파 지연, 전송량이 용량에 근접 → 다중 버스 사용.
• 주의: 슬라이드의 ISA bus = Industry Standard Architecture 버스(명령어 집합 ISA와 다름). 이후 High Performance Bus.
• Synchronous(동기식) = 클럭에 맞춰 동작(일반적). Asynchronous(비동기식) = 클럭 없이 신호를 주고받음(acknowledge). 가장 큰 차이 = 클럭 유무.
• 동기식 타이밍: T1 주소 출력 + Address Enable → T2 Read/Write 신호 → T3 데이터. Read 사이클은 메모리가, Write 사이클은 CPU가 데이터를 버스에 실음. 최소 3클럭. 타이밍 그림의 기울어진 엣지 = 상승·하강 지연 표현.

Lecture 0 — AI와 컴퓨터구조

• 컴퓨터 3대 구성요소: Processor(CPU·GPU·NPU) / Memory(Cache·DRAM·HBM) / I/O, 연결 = NoC·PCIe·NVLink·CXL.
• 우리나라 3대 산업(암기 지시): 반도체 · 피지컬 AI · 데이터센터.
• y = f(Wx + b) → MAC(Multiply-ACcumulate), 행렬곱 = GEMM(GEneral Matrix Multiply).
• The Free Lunch Is Over → 범용 → 도메인 특화 → 특화. Compute is cheap, data movement is not. Roofline.
• CPU(범용) → GPU(처리량, 원래 그래픽용, Tensor Core) → NPU(Neural Processing Unit): systolic array + 큰 SRAM.
• Memory wall → HBM(High Bandwidth Memory) = 적층 DRAM(삼성전자·SK하이닉스). 차세대 HBF(High Bandwidth Flash), PIM(Processing-In-Memory). 모두 데이터 이동 비용 때문.
• SSD·USB = 플래시(비휘발성 반도체), DRAM = 휘발성, SRAM = CPU 내부 캐시.
• Discrete GPU(그래픽 카드, PCIe 경유 → 느림) vs Integrated GPU(SoC = System on Chip, 메모리 공유 → 빠르지만 대역폭 분배·contention·캐시 문제).
• 순서 암기: Cloud AI → Edge AI → On-device AI → Physical AI("순서 바꾸면 말도 안 됨"). 클라우드 왕복 약 100 ms → 시속 100 km 차는 약 2.8 m 이동. Edge = Cisco의 Fog.
• Mixed-criticality: 자율주행(멈추면 안 됨) + 대화 AI(잠깐 멈춰도 됨)가 한 SoC 공존.
• 디바이스 드라이버·런타임·라이브러리 = 시스템 소프트웨어(하드웨어 아님, 자주 출제).

Lecture 0a — 수 표현

포맷 S-E-M 특징

• 지수 = 범위(range), 가수 = 정밀도(precision). 예: 0x3F800000 = 1.0.
• W4A16(가중치만 4비트 → decode/memory-bound 가속) vs W8A8(8비트 연산 → prefill/compute-bound 가속).

Lecture 1b — AI 성능

• Prefill(행렬×행렬, compute-bound) → TTFT(Time To First Token). Decode(행렬×벡터, memory-bound) → TPOT(Time Per Output Token).
• 총 지연 = TTFT + TPOT × (출력 토큰 수 − 1). 예: 200 + 20 × 100 = 2,200 ms.
• Iron Law 확장: Inference Time = MACs / (PE 수 × clock × η). η(utilization)가 CPI 자리.
• TOPS = PE × 2 × clock / 10^12(MAC 1회 = 2 ops). 예: 4,096 MAC × 1 GHz ≈ 8.2 TOPS. TOPS ≠ TFLOPS, 희소(sparse) 표기 주의.
• Peak vs Sustained: η = 30/100 = 0.3, LLM 학습에서는 MFU(Model FLOPs Utilization).
• MLPerf: SPEC과 달리 정확도 목표·지연 한도를 규칙에 포함. 성능/전력 = TOPS/W.
• AI용 Amdahl: GEMM 80%를 100배 → 1/(0.2 + 0.8/100) ≈ 4.8배, 한계 5배.
• TOPS도 MIPS와 같은 함정: 정밀도마다 연산 뜻이 다름, η 무시, 워크로드마다 다름 → 실행 시간으로 재라.

1. LIKE: 문자열 패턴 검색

• 지금까지는 =로 정확히 일치만 찾았다. LIKE는 패턴으로 비교.
• % = 길이 0 이상의 임의 문자열, _ = 정확히 문자 1개.
• C% → C로 시작(C123, C312, C324, C413) / %413 → 413으로 끝남(C413) / _123 → 한 글자 + 123(C123) / C_1% → C + 한 글자 + 1 + 나머지(C312)

SELECT Cno, Cname FROM COURSE WHERE Cno LIKE 'C%';

2. NULL과 3값 논리

• NULL 의미: 값 누락 / 알 수 없음 / 해당 없음 / 의도적 유보.
• NULL ≠ 0, NULL ≠ 빈 문자열, NULL ≠ FALSE. 그래서 = NULL, != NULL로 묻지 않는다.
• 논리값은 TRUE / FALSE / UNKNOWN 세 가지.
  • AND: 하나라도 F면 F, T∧U = U, U∧U = U
  • OR: 하나라도 T면 T, F∨U = U, U∨U = U
  • NOT U = U
• Year가 NULL이면 Year > 3, Year = 3도 UNKNOWN → WHERE에서 선택되지 않음.
• 검사는 열 IS NULL / 열 IS NOT NULL 두 가지뿐.

3. EXISTS / NOT EXISTS

• “부속 질의 결과가 한 행이라도 있느냐”.
• 교수 설명: 바깥 STUDENT에 튜플 변수(생략됨)가 한 학생을 가리키고, 그 한 튜플과 ENROL을 조인해 결과가 한 개라도 있으면 그 학생 이름을 출력. 다음 튜플로 넘어가며 반복 → 바깥 질의 값이 안쪽 질의에 들어가는 상관 부속 질의.

SELECT Sname FROM STUDENT
WHERE EXISTS (SELECT * FROM ENROL
              WHERE Sno = STUDENT.Sno AND Cno = 'C413');

• 결과: EXISTS → 나수영·정기태·송병길 / NOT EXISTS → 이찬수·박종화

4. UNION

• 1학년 학번(300) ∪ C324 수강 학번(300, 400) = 300, 400.
• SQL 결과는 원래 멀티셋인데, UNION은 중복을 자동 제거. 이유: 합집합을 빨리 구하려고 양쪽을 정렬한 뒤 합치기 때문.
• 중복 유지하려면 UNION ALL.
• 조건(합병 가능): 칼럼 개수가 같고, 대응 칼럼의 도메인이 같아야 함. 관계 대수 합병 가능성과 동일.

5. 데이터 변경문 (DML)

UPDATE

UPDATE STUDENT SET Year = 2 WHERE Sno = 300;   -- 키 조건 → 1행만
UPDATE COURSE SET Credit = Credit + 1 WHERE Dept = '컴퓨터';

• Sno가 기본키(후보키)라서 튜플 하나만 바뀜. WHERE가 없으면 모든 행이 갱신(실습에서 전원 2학년이 됨).
• 부속 질의 결합: IN(대상 행 집합 선택), 스칼라 부속 질의(SET에 들어갈 값 1개 계산)

UPDATE ENROL SET Final = Final + 5
WHERE Sno IN (SELECT Sno FROM STUDENT WHERE Dept = '컴퓨터');

트랜잭션 실습

• SQLite 기본 = Autocommit 모드(한 문장 = 한 트랜잭션). MySQL·Oracle은 기본이 Autocommit이 아님.
• BEGIN TRANSACTION; → 그 뒤 문장들은 하나의 트랜잭션(Autocommit 꺼짐) → COMMIT;(성공, 디스크 반영) 또는 ROLLBACK;(시작 전으로 복귀).
• 실습: BEGIN 후 UPDATE하고 COMMIT 없이 강제 종료 → 다시 열면 트랜잭션 시작 전 값으로 되돌아가 있음. 디스크 반영은 COMMIT 때만.

INSERT

• 열 리스트를 쓰면 순서 지정·일부 열만 삽입 가능, 생략 열은 NULL/DEFAULT. 스키마 순서를 다 외우기 어려우니 열 리스트 쓰는 쪽이 낫다(교수).
• 질의 결과 삽입: INSERT INTO COMPUTER(Sno, Sname, Year) SELECT Sno, Sname, Year FROM STUDENT WHERE Dept='컴퓨터'; (대상 테이블 먼저 CREATE)
• SQLite .schema → 내가 썼던 CREATE TABLE 문을 그대로 보여 줌.

DELETE

• DELETE FROM STUDENT WHERE Sno = 100; 키 조건이면 1개, 조건 넓히면 여러 개, WHERE 없으면 전부 삭제.
• DELETE vs DROP: DELETE는 데이터만 지우고 테이블(스키마)은 남음. DROP TABLE은 데이터 + 테이블 자체 제거.
• 부속 질의 DELETE: C413 수강 + 기말 > 90 + 컴퓨터학과 학생인 ENROL 행만 삭제.
• 정리: 검색 SELECT-FROM-WHERE-GROUP BY-HAVING-ORDER BY / 삽입 INSERT INTO / 삭제 DELETE FROM-WHERE / 변경 UPDATE-SET-WHERE. 여기까지가 SQL 문장 전부(교수).

6. 뷰 (VIEW)

• 외부 스키마를 SQL로 만든 것 = 뷰. 실제 데이터가 없는 가상 테이블, 실제 데이터가 있는 건 기본(base) 테이블.
• SQL 한 문장으로 정의, 정의는 카탈로그에 저장.

CREATE VIEW CSTUDENT(Sno, Sname, Year)
AS SELECT Sno, Sname, Year FROM STUDENT WHERE Dept = '컴퓨터'
WITH CHECK OPTION;

• 뷰 열의 도메인은 따로 지정하지 않는다. 기본 테이블 해당 칼럼의 도메인을 그대로 씀.
• .tables에 CSTUDENT가 테이블처럼 보이고, SELECT * FROM CSTUDENT도 그냥 테이블처럼 쓴다.

뷰 질의가 처리되는 과정

1. 사용자: SELECT * FROM CSTUDENT WHERE Year = 4;
2. DBMS가 뷰를 제거해 기본 테이블만으로 된 SQL로 바꿈: SELECT Sno, Sname, Year FROM STUDENT WHERE Year = 4 AND Dept = '컴퓨터';
3. 부속 질의가 있으면 비중첩(unnest) SQL로 다시 바꿈
4. 최적화: 접근 경로가 들어간 관계 대수 플랜 여러 개 중 cost(=시간) 최소 1개 선택 → 실행

• 뷰 위의 뷰(V3 → V2 → V1 → T1, T2)도 한 단계씩 풀어서 끝내 기본 테이블만 남김.
• 과목 전체 흐름 정리: 릴레이션 → 절차(관계 대수) vs 비절차(투플·도메인 관계 해석) → Codd가 셋의 동등성 증명 → 해석은 수학 기호라 쓰기 어려워 SQL 도입.

WITH CHECK OPTION

• 뷰를 통한 INSERT/UPDATE가 뷰의 WHERE 조건을 만족하는지 검사 → 뷰가 정의한 세계를 벗어나는 변경 방지.
• CSTUDENT에는 Dept 열이 없어서 이 예에서는 큰 쓸모가 없다(교수).

뷰 예제

• DEPTSIZE(Dept, Size): SELECT Dept, COUNT(*) FROM STUDENT GROUP BY Dept → 통계 요약 뷰. SELECT * FROM DEPTSIZE WHERE Size > 1 → 컴퓨터. 기본 테이블로 바뀌면 GROUP BY + HAVING COUNT(*) > 1.
• HONOR(Sname, Dept, Grade): STUDENT ⋈ ENROL, Final > 90 → 조인 뷰(기본 테이블 여러 개 가능)
• COMHONOR: HONOR에서 Dept='컴퓨터' → 뷰로부터 뷰

DROP VIEW (10/15)

• DROP VIEW DEPTSIZE RESTRICT; → 이 뷰를 쓰는 뷰·제약이 있으면 제거 안 됨
• CASCADE → 그 뷰를 참조하는 뷰까지 같이 제거

뷰 변경(삽입·삭제·갱신) 가능성

• SELECT는 다 되지만 INSERT·DELETE·UPDATE는 제한.
• 기본키를 포함한 뷰 → 이론적으로 변경 가능(STUDENT_VIEW1: Sno, Dept)
• 기본키 없음 → 불가(STUDENT_VIEW2: Sname, Dept). 동명이인이면 어느 행인지 구분 불가, 삽입 시 기본키 지정 불가.
• NOT NULL 칼럼(Sname)을 뷰가 안 가지면 삽입 불가.
• 허용 안 되는 대표 경우: 산술식·함수 열 / 집계 함수(COUNT·SUM·AVG·MAX·MIN) / DISTINCT·GROUP BY·HAVING / 두 개 이상 테이블 조인 / 변경 불가 뷰 위의 뷰
• 이론적으로 가능 ⊃ 실제 DBMS가 허용. 범위는 제품마다 다름 → 쓰기 전에 확인.
• SQLite는 뷰에 직접 INSERT/UPDATE/DELETE 불가(직접 실행 시 cannot modify v because it is a view). MySQL·PostgreSQL은 기본키 포함 단순 뷰면 가능.
• 참고: 실제 DBMS는 교과서 집계 함수 5개 외에 대·소문자 변환, 부분 문자열, 표준편차 등 수십 개 함수를 제공.

뷰의 장단점

• 장점
  • 논리적 데이터 독립성: 기본 테이블이 바뀌어도 뷰를 쓰는 코드는 그대로. 예: STUDENT.Sname → StudentName으로 바꿔도 CREATE VIEW V1 AS SELECT Sno, StudentName AS Sname ...으로 V1만 재정의하면 기존 응용 무수정. 스마트폰 주소록 앱이 OS 버전업에도 안 깨지는 이유(뷰를 통해 접근).
  • 물리적 데이터 독립성(복습): 저장 방법을 바꿔도 기본 테이블 정의는 그대로 → 기존 SQL 그대로 동작.
  • 접근 제어·보안: V1(Sno, Sname)만 홍길동에게 권한 → 학년·학과 못 봄
  • 필요한 정보만 단순하게(예: 3학년만 보이는 뷰)
  • 같은 데이터에 사용자별 다양한 표현(V1·V2·V3를 홍길동·김유신·이순신에게)
• 단점
  • 뷰 정의 변경이 제한적(그 뷰를 쓰는 다른 뷰도 고쳐야 함)
  • INSERT/DELETE/UPDATE 범위가 좁음
  • 복잡한 뷰는 풀어내기 어려워 임시 테이블을 만들어 처리 → 성능 문제, 관리자 부담

7. 응용 프로그램 인터페이스

• 방법 3가지: Embedded SQL(교재) / ODBC(마이크로소프트가 만든 윈도우용 표준 C 함수, 모든 DB 업체가 지원, 요즘 대세) / JDBC(Java)
• 공통 기능 2가지: ① DB에 SQL을 보낸다 ② 결과 집합(멀티셋)을 하나씩 꺼내 처리한다

Embedded SQL

• 호스트(주인) 언어 = C, C++, Java, COBOL 등 / 게스트(손님) = 안에 들어간 SQL
• 게스트 영역 표시: EXEC SQL ...;
• 호스트 변수: 게스트 안에서 쓸 때 :sno처럼 콜론. 안 붙이면 속성/테이블 이름으로 취급.
• 쓸 호스트 변수는 EXEC SQL BEGIN DECLARE SECTION; ~ END DECLARE SECTION; 안에 선언
• SQLSTATE: 실행 결과를 받는 특별한 호스트 변수. '00000' = 성공, 그 외 = 경고/오류(번호별 매뉴얼)

EXEC SQL SELECT Sname, Dept
         INTO :sname, :dept
         FROM STUDENT WHERE Sno = :sno;
if (strcmp(SQLSTATE, "00000") == 0) ... else ...;

• INTO = 결과 칼럼을 어느 호스트 변수에 담을지. WHERE Sno = :sno = 프로그램에서 입력받은 값을 질의에 사용.
• 컴파일: DB 제품의 프리컴파일러가 EXEC SQL 부분을 C 함수 호출로 치환한 소스를 만들고 → 그걸 gcc 같은 일반 컴파일러가 컴파일. 이 함수들을 표준화한 게 ODBC.

커서가 필요 없는 연산

• Singleton SELECT: 결과 0 또는 1행(키 조건)
• UPDATE·DELETE·INSERT: 결과를 받지 않고 성공/실패만 알면 됨

커서

• 결과가 여러 행이면 프로그램은 집합을 못 다루니 한 행씩 꺼내야 함 → 지금 어떤 튜플을 처리 중인지 가리키는 것 = 커서
• FETCH: 커서가 가리키는 튜플을 결과 테이블에서 하나 꺼내는 것
• active set(활동 세트): 질의 실행으로 만들어진 결과 집합 / current row(현재 행): 커서가 지금 가리키는 행

1. SQL 개요

• 1974 IBM System R(관계형이 실제·상업적으로 가능한지 확인용 연구 프로토타입)의 언어 SEQUEL(Structured English QUEry Language) → SQL(Structured Query Language). 상용판 DB2, 이후 Oracle·Sybase·Ingres 등이 채택 → 산업 표준.
• 제품마다 확장하며 달라져서 표준 제정: SQL-86 → SQL-92(대규모 확장) → SQL:1999(객체 개념) → SQL:2003(상속 등). 수업 목표 수준은 이 정도.
• 종합 언어: 정의(DDL) + 조작(DML: 검색·삽입·삭제·갱신) + 제어(DCL: 권한·보안·트랜잭션 제어)
• 특징
  • 이론적 기반: 틀은 관계 대수(SELECT-FROM-WHERE), 조건식은 투플 관계 해석
  • 고급 언어: 물리적 접근 경로를 쓰지 않음
  • 비절차적: WHAT 선언
  • 표준: DB 간 이동성, 하나만 익히면 됨
  • 대화식: 터미널에서 직접 질의
  • 응용에 삽입 가능(Java, C, C++, COBOL, Python)
  • 집합(set/bag) 단위 처리, 용어 relation→table, tuple→row, attribute→column
• 사용자가 결과를 명세 → SQL이 **여러 관계 대수(플랜)**로 바뀜 → 효율적인 실행 계획(plan) 1개 선택 → 비절차 질의도 빠르게 실행.

인덱스 (교수 비유)

• 40명 중 홍길동 찾기 = 하나씩 확인 O(n). 이름순으로 좌표(물리 주소)를 적은 종이가 있으면 이진 탐색 O(log₂ n) → 이게 인덱스(키 → 물리 주소).
• 공간을 차지하고 데이터가 바뀔 때마다 유지해야 하므로 필요할 때만. 만들지 말지는 DBA가 결정.
• SQL 문장에는 인덱스를 쓰지 않는다. DBMS가 있으면 쓰고 없으면 안 쓰는 플랜을 알아서 만든다.

DB가 디스크를 쓰는 두 방식

• ① 파일 시스템 위의 파일 하나를 디스크처럼 사용(SQLite의 sample.db) → 일반적
• ② DBMS가 파일 시스템 없이 디스크 전체를 직접 관리 → 은행 같은 고성능 환경. 그 디스크엔 일반 파일 저장 불가

2. 스키마와 카탈로그

• SQL의 SCHEMA = DB 안의 논리적 구역(교무처·학생처·입학처 구역처럼). 물리적으로 붙어 있을 필요 없음.
  • 장점: 구역별 권한 부여(보안), 같은 테이블 이름을 구역마다 독립적으로 사용
  • 앞에서 배운 “DB 구조 = 스키마”와 의미가 다르니 주의
• CREATE SCHEMA UNIVERSITY AUTHORIZATION SHLEE; (관리자 SHLEE). Oracle·MySQL은 이 구역을 DATABASE라고 부름 → CREATE DATABASE UNIVERSITY
• SQLite는 구역이 없음. 파일 전체가 구역 하나.
• 구역·테이블 정보는 모두 시스템 카탈로그에 저장. Catalog ⊃ Schema ⊃ Tables/Views/Domains

3. DDL

• 동사 3개: CREATE / ALTER / DROP + 대상(SCHEMA·DATABASE·DOMAIN·TABLE·VIEW·INDEX) + 이름

CREATE DOMAIN

CREATE DOMAIN DEPT CHAR(4)
  DEFAULT '???'
  CONSTRAINT VALID_DEPT
  CHECK (VALUE IN ('COMP','ME','EE','ARCH','???'));
DROP DOMAIN DEPT RESTRICT | CASCADE;

• RESTRICT = 사용 중이면 삭제 거부 / CASCADE = 참조하는 것까지 연쇄 삭제(무서워서 잘 안 씀)

데이터 타입

• 정수 INT=INTEGER, SMALLINT / 실수 FLOAT(n), REAL, DOUBLE PRECISION
• 정형 숫자 DECIMAL(i,j)=NUMERIC(i,j): 전체 i자리, 소수 j자리. 돈처럼 정확해야 할 때
• 비트열 BIT(n), BIT VARYING(n) / 문자열 CHAR(n) 고정 길이(전화번호), VARCHAR(n) 가변 길이, n은 최대(주소)
• 날짜·시간 DATE, TIME, TIMESTAMP(날짜+시간 한 시점), INTERVAL(두 시간의 간격)

테이블 3종

• 기본 테이블(base/저장 테이블): CREATE TABLE, 실제 저장, 모든 뷰·질의의 기반
• 뷰(가상 테이블): CREATE VIEW, 기본 테이블 또는 다른 뷰에서 유도 = 외부 스키마. 독자 저장 없음
• 임시 테이블: 질의 처리 중 DBMS가 스스로 만들고 지움. 사용자가 만드는 문장 없음
• 테이블 vs 릴레이션: 릴레이션은 set, 테이블은 multiset(bag). 삽입 때마다 중복 검사하면 비용이 커서 허용. multiset에 SQL을 써도 의미상 문제없음이 증명됨

CREATE TABLE

CREATE TABLE ENROL (
  Sno INTEGER NOT NULL,
  Cno CHAR(6) NOT NULL,
  Grade INTEGER,
  PRIMARY KEY (Sno, Cno),
  FOREIGN KEY (Sno) REFERENCES STUDENT(Sno)
    ON DELETE CASCADE ON UPDATE CASCADE,
  FOREIGN KEY (Cno) REFERENCES COURSE(Cno)
    ON DELETE CASCADE ON UPDATE CASCADE,
  CHECK (Grade >= 0 AND Grade <= 100)
);

• SQL 문장 끝은 세미콜론. 그 전까지는 여러 줄에 걸쳐 써도 됨
• 제약 ↔ 관계 모델
  • PRIMARY KEY: 유일 + NULL 금지 → 개체 무결성. 한 번만 나옴
  • UNIQUE: 후보키/대체키. 여러 번 가능
  • NOT NULL: 애트리뷰트 제약(STUDENT에서 Sno·Sname 필수)
  • FOREIGN KEY: 참조 무결성. 여러 개 가능
  • CHECK: 도메인·사용자 제약(Year 1~4, 점수 0~100)

참조 동작 (부모 행 삭제·변경 시 FK를 어떻게?)

• CASCADE: 100번 학생 삭제 → ENROL의 100번 행도 같이 삭제 / 100→200 변경 → FK도 200으로
• RESTRICT: 참조하는 행이 있으면 거부 → 자식부터 지워야 함(졸업하려는데 수강 기록이 있어 못 함)
• SET NULL: FK를 NULL로. 단 FK가 NOT NULL이면 불가
• SET DEFAULT: 기본값(예: 가상 학생 700번)으로
• 어느 걸 쓸지는 학칙(규정)에 따라 결정

DROP / ALTER

• DROP TABLE STUDENT RESTRICT; → 이 테이블로 만든 뷰가 있으면 거부(뷰부터 지우는 안전한 방법) / CASCADE → 뷰, 뷰의 뷰까지 삭제(영향 범위 큼)
• DROP SCHEMA UNIVERSITY CASCADE;
• ALTER TABLE ENROL ADD Final CHAR DEFAULT 'F'; / DROP Grade CASCADE / ALTER 열 SET|DROP DEFAULT
• 대부분 DBMS(SQLite 포함)는 열 ADD만 허용. 새 열은 기존 응용·뷰에 영향이 없지만, 삭제는 그 열을 쓰는 응용이 깨지기 때문

4. SQLite 실습

• sqlite3 test.db → DB 파일 생성. .tables로 테이블 목록
• PRAGMA foreign_keys; → 0(꺼짐). PRAGMA foreign_keys = ON; → 1. 실행할 때마다 켜야 함
• 대학 DB: STUDENT · COURSE · ENROL (교재 값 그대로)

5. SELECT 기본

SELECT Sname, Sno FROM STUDENT WHERE Dept = '컴퓨터';
-- = π Sname,Sno ( σ Dept='컴퓨터' (STUDENT) )

• SELECT=π(무엇을 출력), FROM=입력 릴레이션(카티션 곱), WHERE=σ(어떤 행)
• 투플 변수 생략: SELECT S.Sname FROM STUDENT S WHERE S.Dept='컴퓨터'와 같음. 변수가 하나라 헷갈리지 않으면 생략, DBMS가 내부적으로 붙임
• 최소 형태 = SELECT + FROM. 나머지는 선택
• 작성 순서(외우기): SELECT – FROM – WHERE – GROUP BY – HAVING – ORDER BY
• DISTINCT: 중복 제거(정렬해서 제거 → 행이 많으면 비용 큼). 안 쓰면 ALL(기본, 아무도 안 적음)
  • SELECT DISTINCT Dept FROM STUDENT; → 컴퓨터, 전기, 산공 / SELECT Year, Dept는 5행 → DISTINCT로 4행
• SELECT * = 모든 열
• ORDER BY: ORDER BY Sname DESC(역순), ORDER BY Sno DESC, Cno ASC(학번 역순, 같은 학번 안에서 과목번호 순)
• AS / 산술식 / 상수 열: SELECT Sno AS 학번, '중간시험 =' AS 시험, Midterm + 3 AS 점수 FROM ENROL WHERE Cno='C312'; 결과 테이블의 열 이름을 바꾸고, 상수 문자열 열과 계산 열을 만들 수 있음

6. JOIN

• FROM에 두 테이블 → 카티션 곱(대부분 의미 없음) → 기본키 = 외래키인 것만 남기는 동등 조인이 의미 있는 조인

SELECT S.Sname, S.Dept, E.Grade
FROM STUDENT S, ENROL E
WHERE S.Sno = E.Sno AND E.Cno = 'C413';   -- 나수영 A, 정기태 A, 송병길 B

• 자기 조인: 같은 테이블을 두 번 쓰면 모호하므로 반드시 별칭(S1, S2)

SELECT S1.Sno, S2.Sno FROM STUDENT S1, STUDENT S2
WHERE S1.Dept = S2.Dept AND S1.Sno < S2.Sno;   -- 같은 학과 후배 쌍

• FROM 절 명세 (모두 같은 결과)
  • FROM STUDENT JOIN ENROL ON (STUDENT.Sno = ENROL.Sno) → 조건 직접
  • FROM STUDENT JOIN ENROL USING (Sno) → 같은 이름 열 지정, 조인 열 1개만 남음
  • FROM STUDENT NATURAL JOIN ENROL → 같은 이름 공통 열 자동
  • WHERE ENROL.Cno = 'C413'은 세 방식 모두 추가 가능

7. 집계 함수

• COUNT · SUM · AVG · MAX · MIN
• SELECT COUNT(*) AS 학생수 FROM STUDENT; → 5. 열 이름이 COUNT(*)이면 이상하니 AS로
• COUNT는 테이블이 멀티셋이라 중복 포함 개수. 서로 다른 개수는 COUNT(DISTINCT Cno) (300번 학생 → 3)
• SELECT AVG(Midterm) AS 중간평균 FROM ENROL WHERE Cno='C413'; → 88 / C413 MAX 95, MIN 80

8. GROUP BY / HAVING

SELECT Cno, AVG(Final) AS 기말평균 FROM ENROL GROUP BY Cno;
SELECT Cno, AVG(Final) AS 평균 FROM ENROL GROUP BY Cno HAVING COUNT(*) >= 3;  -- C413 90, C312 90

• 그룹별 결과에는 어느 그룹인지(Cno)를 같이 출력해야 의미가 있음(교수)
• WHERE = 그룹 전 개별 행 필터 / GROUP BY = 묶기 / HAVING = 그룹에 대한 조건

9. 부속 질의 (Subquery)

• 질의 안의 SELECT. 전체를 중첩 질의(nested query)라 함

SELECT Sname FROM STUDENT
WHERE Sno IN (SELECT Sno FROM ENROL WHERE Cno = 'C413');   -- 나수영, 정기태, 송병길

• IN = “부속 질의 결과 집합의 원소인가”. NOT IN = 원소가 아닌가(C413 미수강 → 이찬수, 박종화)
• =(단일 값): 정기태와 같은 학과 → WHERE Dept = (SELECT Dept FROM STUDENT WHERE Sname='정기태'). 안쪽 결과가 여러 개면 위험 → 정확히 1개일 때만
• ALL: WHERE Final > ALL (SELECT Final FROM ENROL WHERE Sno=500) → 500번의 모든 기말보다 높은 것. IN은 하나라도 맞으면, ALL은 다 맞아야
  • SQLite는 ALL 미지원(교안). SQLite 3.45로 직접 실행 → near "all": syntax error

중첩 질의를 써도 되는 이유

• 중첩 질의는 “안쪽 먼저” 순서가 있는 절차적 사고. 순서를 사람이 정하면 기계가 더 빠른 방법을 찾을 기회를 뺏음
• Kim Won이 SQL의 모든 중첩 질의를 조인으로(비중첩으로) 바꿀 수 있음을 증명 → DBMS가 unnest한 뒤 접근 경로 포함 관계 대수 플랜으로 바꿔 최적화
• 그래서 생각하기 편한 대로 써도 된다. 성능 걱정 불필요

10. SELECT 논리 처리 순서

• FROM/JOIN → WHERE → GROUP BY → HAVING → SELECT(projection) → ORDER BY
• 적는 순서와 다름. 이건 논리적 순서이고, 실제 물리적 실행은 최적화가 동일 의미의 더 빠른 방식으로 바꿀 수 있음

11. 총정리 + 트랜잭션

• DDL: CREATE TABLE/VIEW/INDEX/SCHEMA(DATABASE), DROP, ALTER(열 ADD 정도만)
• 키 지정: 기본키 PRIMARY KEY, 후보키 UNIQUE, 외래키 FOREIGN KEY + RESTRICT/CASCADE 등
• PK → 개체 무결성, FK → 참조 무결성
• MySQL·Oracle은 참조 무결성 검사가 기본, SQLite는 기본 OFF → PRAGMA foreign_keys = ON;
• 트랜잭션: DB는 무조건 트랜잭션 단위로 실행
  • 시작 BEGIN TRANSACTION(생략 가능, 첫 SQL 문장이 시작으로 간주) / 성공 종료 COMMIT / 실패 시 시작 전으로 ROLLBACK
  • Autocommit: 한 문장 = 한 트랜잭션. SQLite 기본 = Autocommit(그래서 COMMIT 안 써도 반영됨). Oracle 등은 기본이 아님(autocommit on 필요)

1. 관계 해석

• 술어 논리 기반 비절차적 질의.
• 관계 대수와 표현력 동등.

튜플 관계 해석

• 기반: Predicate calculus. Predicate = 실행 결과가 반드시 True/False인 함수. 이 논리식으로 관계 모델의 연산을 표현
• 관계 해석은 표현력은 관계 대수와 동등하지만 사고 방식이 다름(절차 없이 조건만 선언)
• 구성 요소 ① 변수
  • 투플 변수(범위 변수) t: 릴레이션의 한 투플을 가리킴
  • 범위식 R(t): t의 범위 릴레이션은 R. 예: STUDENT(s)
  • 한정 애트리뷰트 t.A 또는 t[A]: t가 가리키는 투플의 애트리뷰트 A 값. 예: s.Sno, s.Sname, s.Year, s.Dept
• 구성 요소 ② 원자식 3종 (결과는 항상 True/False)
  • 범위식 R(t)
  • 속성 간 비교 t.A θ u.B
  • 상수 비교 t.A θ c
  • θ ∈ {=, ≠, <, ≤, >, ≥}
• WFF(정형식) = 원자식 + 불리언 연산자 + 정량자를 규칙대로 결합한 식
  1. 모든 원자식은 WFF
  2. F가 WFF면 (F), ¬F도 WFF
  3. F, G가 WFF면 F∧G, F∨G도 WFF
  4. F(t)가 WFF면 ∀t(F(t)), ∃t(F(t))도 WFF
  5. 위 규칙으로 만든 식만 WFF
  • 예: s.Sno = 100, s.Sno = e.Sno ∧ e.Cno ≠ c.Cno, (∃e)(e.Sno = s.Sno ∧ e.Cno = 'C413')
• 자유 변수 vs 속박 변수
  • 자유 변수: 정량자에 묶이지 않은 변수 → 질의 결과(막대 왼쪽)에 나올 수 있음. 예: { s.Sname | … }의 s
  • 속박 변수: ∀t, ∃t로 한정된 변수. ∀ = for all, ∃ = there exists / for some
  • 등식: (∀t)F(t) ∧ (∀t)H(t) = (∀t)(F(t)∧H(t)) / (∃t)F(t) ∨ (∃t)H(t) = (∃t)(F(t)∨H(t))
• 자연어로 읽기: ∃ “어떤 e가 존재하여…” / ∀ “모든 c에 대하여…” / ¬∃ “그런 e가 존재하지 않는다”
• 형식: { t.A, … | F } — 막대 왼쪽 = 목표 리스트(자유 변수만), 오른쪽 = 조건 WFF
• 예: C413에서 A 받은 학번 { e.Sno | ENROL(e) ∧ e.Cno='C413' ∧ e.Grade='A' }
• 예: C413 등록 학생 이름·학과 { s.Sname, s.Dept | STUDENT(s) ∧ ∃e(ENROL(e) ∧ s.Sno=e.Sno ∧ e.Cno='C413') }
• 예: 모든 과목에 등록한 학생 이름 { s.Sname | STUDENT(s) ∧ (∀c)(∃e)(COURSE(c) ∧ ENROL(e) ∧ e.Sno=s.Sno ∧ e.Cno=c.Cno) }
• 예: C413에 등록하지 않은 학생 이름 { s.Sname | STUDENT(s) ∧ ¬∃e(ENROL(e) ∧ s.Sno=e.Sno ∧ e.Cno='C413') }

도메인 관계 해석

• 도메인 변수로 각 속성 값을 가리킴. 범위식 STUDENT(xSno, xSname, xYear, xDept)
• 튜플 변수 1개 vs 도메인 변수 여러 개. 속성 접근은 s.Sname 대신 xSname
• 원자식: 범위식 / 변수끼리 비교 / 변수와 상수 비교. WFF 규칙은 투플 해석과 동일
• 필요 없는 도메인 변수는 ∃로 묶어 결과에서 뺌
• 형식: { x1, …, xn | F(x1, …, xn, xn+1, …, xn+m) } — 왼쪽 목표 리스트, 오른쪽 조건
• 예: 컴퓨터학과 3·4학년 이름 { xSname | (∃xYear)(∃xDept)(STUDENT(xSno,xSname,xYear,xDept) ∧ xYear≥3 ∧ xDept='컴퓨터') }
• 예: C413 성적 A 학번 { xSno | (∃xCno)(∃xGrade)(ENROL(xSno,xCno,xGrade,xMidterm,xFinal) ∧ xCno='C413' ∧ xGrade='A') }
• 예: 기말 90 이상 학번·이름 → STUDENT 범위식 ∧ (∃xFinal)(∃xxSno)(ENROL(…) ∧ xSno=xxSno ∧ xFinal≥90)
• 예: C324 미등록 이름 → STUDENT(…) ∧ ¬(∃xxSno)(∃xCno)(ENROL(…) ∧ xSno=xxSno ∧ xCno='C324')
• 비교표: 변수 단위(투플 전체 vs 애트리뷰트 값) / 범위 선언(STUDENT(s) vs STUDENT(xSno,…)) / 접근(s.Sname vs xSname) / 논리 구성·비절차·표현력은 동일
• 두 테이블 조인은 두 범위식의 학번 변수가 같다는 조건으로(xSno = xxSno)

왜 관계 해석을 직접 안 쓰나

• ∀·∃·∧·¬ 같은 기호를 타이핑하기 어렵고, 조건 제시법이라 수학에 익숙하지 않으면 쓰기 어려움
• 그래서 System R은 관계 해석을 질의어로 채택하지 않고 같은 의미를 영어 문장식으로 만든 SQL을 채택

2. QBE (Query By Example)

• IBM 1975. 도메인 관계 해석 기반 2차원 테이블 질의.
• 테이블 스켈레톤 + 예제 원소(언더바 변수).
• P. = 출력, I. = 삽입, D. = 삭제, U. = 갱신.
• 기본은 중복 자동 제거(관계 모델 결과는 집합), P.ALL = 중복 허용.
• 테이블 이름 아래 P. = 모든 열 출력(SELECT *).
• 같은 행에 조건 = AND, 서로 다른 행에 조건 = OR. 복잡하면 CONDITIONS 박스에 _EC = C413 AND _EF ≥ 85처럼 식으로.
• 같은 예제 원소(_STX)를 두 테이블에 쓰면 조인. 검색 결과를 다른 테이블(SENIOR)에 I.로 삽입 가능.
• U. 산술 갱신: Final 칸 _G+5. 그래픽 디스플레이 환경 전제(지금은 다 됨). MS Access에서 볼 수 있는 방식.

3. SQLite

• 경량·임베디드 출발 (CCTV, 스마트폰).
• 특징:
  • 클라이언트-서버 아님
  • 유저 개념 없음
  • 단일 파일 DB
  • 읽기 동시 여러 개 O, 쓰기는 한 순간 1개만 → 병렬 수행이 매우 제한(이 코드가 빠져 전체의 약 2/3가 줄어듦)
  • 단일 사용자·단일 트랜잭션 환경에서는 가장 빠름
  • 라이선스: 퍼블릭 도메인(수정·비공개 모두 자유). 비교: 리눅스 GPL은 수정하면 공개 의무
  • DB 파일 이름을 직접 지정해야 함 (sqlite3 lab.db)
• 안드로이드·iOS 기본 DB.
• FK 제약 검사 기본 OFF → PRAGMA foreign_keys = ON; 필요.
• 점(.) 명령: .tables, .headers on, .mode col, .nullvalue NULL. 점 명령은 SQL 표준이 아니라 SQLite 도구 명령(제품마다 다름).
• 스키마 실습: STUDENT(PK Sno, CHECK Year 1~4), COURSE(PK Cno), ENROL(PK (Sno,Cno), FK 2개 ON DELETE/UPDATE CASCADE, CHECK 점수 0~100)
• INSERT는 열 목록을 쓰면 VALUES 순서를 바꿀 수 있음. 문자열은 작은따옴표.
• FK 때문에 넣는 순서: STUDENT → COURSE → ENROL

1. 관계 대수 vs 관계 해석

• 관계 대수: 절차적. WHAT + HOW(무엇을 + 어떻게)를 함께 명세. 컴퓨터가 실행할 순서.
• 관계 해석: 비절차적. WHAT(무엇을) 만. 사람이 편하게 묻는 방식.
• Codd가 두 표현력이 동등함을 증명 → 사람은 해석으로 묻고 DBMS가 대수로 바꾸면 된다. 

2. 폐쇄 성질 (Closure)

• 연산 결과가 다시 릴레이션 → 다른 연산의 피연산자가 될 수 있다.
• 예: 선택 결과를 다시  ㅡ선택하거나 조인에 넣을 수 있다.

3. 일반 집합 연산

• 합집합 ∪ : T ∈ R or T ∈ S
• 교집합 ∩ : T ∈ R and T ∈ S
• 차집합 − : T ∈ R and T ∉ S
• 카티션 프로덕트 × : R의 모든 튜플과 S의 모든 튜플 조합
• 크기: |R∪S| ≤ |R|+|S|, |R∩S| ≤ min(|R|,|S|), |R−S| ≤ |R|, |R×S| = |R|×|S|
• 합병 가능: 차수(속성 개수) 같고, 대응 속성 도메인 같아야 함. 학생 ∪ 과목은 말 안 됨.
• 결합·교환 법칙: ∪ ∩ × 성립. 차집합은 안 됨.

4. 순수 관계 연산자

선택 σ (Select)

• 수평 방향 부분집합. 조건 만족 튜플만.
• 예: σ_{Dept=‘컴퓨터’}(STUDENT)
• 조건 형태: A θ v(상수) 또는 A θ B(속성끼리), θ ∈ {<, >, ≤, ≥, =, ≠}. 스키마는 그대로 유지
• 선택도(selectivity) = 선택되는 튜플 비율. 학생 5명 중 컴퓨터 3명 → 60%.
• σ_c2(σ_c1(R)) = σ_(c1∧c2)(R)

투영 π (Project)

• 세로 방향 부분집합. 속성 선택 + 중복 제거(π학년(학생) → 4, 3, 1, 2).
• π_Y(π_X(R)) = π_Y(R) (Y ⊆ X)
• 선택·투영 모두 릴레이션 크기를 줄임 → 질의 최적화에서 먼저 줄이는 게 중요

조인 ⋈ (Join)

• 카티션 프로덕트 + 선택.
• θ-조인: 비교 연산자 조건.
• 동일 조인(equijoin): 등호 조건.
• 자연 조인(natural join): 공통 속성을 한 번만 남김. 가장 자주 쓰임.
• 의미 있는 조인은 대부분 기본키 ⋈ 외래키.
• 이름 충돌 시: 릴레이션이름.속성이름으로 구분.
• 결과 차수 = degree(R) + degree(S) (학생 4 + 등록 5 = 9, 자연 조인은 8)
• 조인 속성은 1개일 필요 없음. 키가 여러 속성이면 R.A=S.A ∧ R.C=S.C처럼 여러 개
• 조인이 필요한 이유: 중복을 막으려고 릴레이션을 쪼갰기 때문(정규화), 질의 때 다시 결합

디비전 ÷ (Division)

• “모두”를 만족하는 튜플 추출.
• 예: C312와 C413을 모두 듣는 학생 → 300, 400. 세 과목이면 400만.
• R(X) ÷ S(Y), Y ⊆ X, 결과 스키마 D = X − Y

5. 확장 연산

• 개명(ρ): 속성 이름 변경 (자기 조인 시 필수).
• 기본 연산(다른 연산으로 대체 불가): ∪, −, ×, π, σ, ρ / 복합 연산: ∩, ⋈, ÷. 예: R∩S = R−(R−S), R⋈S = σ(R×S)
• 세미 조인 R⋉S = π_X(R⋈S): S와 조인되는 R 튜플만, R 속성만. 분산 DB 전송량 절감. 교환 법칙 X
• 외부 조인: 짝이 없는 튜플도 버리지 않고 상대 속성을 NULL로
• 외부 합집합 ∪+: 합병 불가능한 릴레이션도 모든 속성을 합치고 없는 값은 NULL
• 집계: GROUP_A F_B(E). 예: GROUP과목번호 AVG성적(등록). 실행 순서 GROUP → AVG

6. 관계 대수 질의 예제

• 모든 학생 이름·학과: π이름,학과(학생)
• C413 등록 학생 이름·성적: π이름,성적(σ과목번호='C413'(학생 ⋈N 등록)) — 안쪽부터 JOIN → SELECT → PROJECT 순서로 읽기
• '화일구조' 담당교수: π담당교수(σ과목이름='화일구조'(과목))
• 모든 과목 수강 학생 학번·이름: π학번,이름((π학번,과목번호(등록) ÷ π과목번호(과목)) ⋈N 학생) — “모든” = 디비전
• 삽입: 학생 ∪ {⟨600, '김영호', 4, '컴퓨터'⟩}
• 삭제: 과목 − σ과목이름='데이터베이스'(과목)