GIS DB 설계 방법론 (Models of Spatial Information) 건국대학교 컴퓨터공학과 데이타베이스 연구실 97년 11월 한 기 준

모델링 한 도메인(원시 도메인)내의 원소들이 다른 도메인(목표 도메인)내에서 표현되는 인공적 과정 원시 도메인으로 부터 단순화와 추상화 과정 정확성과 정밀성 보장 필요

모델 유형 1. 필드-중심 모델 2. 객체-중심 모델 정보를 필드들의 집합으로 취급(e.g., 관계형 모델) 정보를 객체들의 집합으로 취급

객체-중심 모델 객체는 정적인 데이타 중심 측면(애트리뷰트)과 동적인 행위 측면(연산) 제공 eg., 영역(region) 애트리뷰트 : 경계 (점들의 집합 또는 선분들의 집합) 연산(메소드) : 면적 계산, 영역을 축적하여 도식화 등

객체 중심 모델링 실세계 내에 존재하는 객체를 그대로 객체로 모델링 가능 (관계형 모델 사용시에는 관계형 개념으로 변환 필요) 정보의 구조적 특성뿐만 아니라 행위(연산)도 모델링 가능 객체 중심 도형(v.s. E-R 도형) type road state name : string classification : string year built : date centre line : arc • • • behaviour create : -> road delete : road -> length : road -> real update classification : road -> road display : road, scale -> end road type motorway inherits road state service stations : set(building) • • • end motorway

공간 데이타 구성 방법 (1/2) (1) 관계형 표현 (2) 계층형 표현 (3) 네트워크형 표현

공간 데이타 구성 방법 (2/2)

데이타베이스 설계 과정 (1/2) 1. 외부적 모델링 단계 2. 개념적 모델링 관계 3. 논리적 모델링 단계 사용자가 실세계에서 자신의 요구와 관련된 부분 집합을 정의 다양한 목적을 갖는 다수의 외부 모델들이 존재 주로 요구조건에 관한 서술식 기술 사용 2. 개념적 모델링 관계 모든 외부 모델들의 합성 데이타베이스 정보 내용만 취급 주로 entity-relationship 모델 사용 3. 논리적 모델링 단계 관계형, 계층형, 네트워크형 모델로 사상 데이타 요소의 중요 특성(즉, 이름, 타입, 값, 범위 등)에 관한 기술 4. 내부적 모델링 단계 데이타베이스의 바이트-수준 데이타 구조와 관련 저장 장치, 화일 구조, 엑세스 방법등을 취급

데이타베이스 설계 과정 (2/2)

Entity-Relationship 모델 (2) 개체들의 클래스 (3) 관계 (4) 애트리뷰트 (5) 카디날리티(cardinality) 관계에 참여하는 개체의 최소와 최대 갯수 (6) 무결성 제한조건 부합되어야 하는 predicate

Entity-Relationship 도형 예 (1/2)

Entity-Relationship 도형 예 (2/2) IC : 한 선분은 2개의 필지 또는 한 필지와 한 도로를 경계

논리적 모델링 예 (1/2) 개념적 모델 관계형 모델 (E-R 도형) 사상 (관계형 스키마)

논리적 모델링 예 (2/2) toy cadastre 경우 5개 개체 4개 관계 STREET(Street-ID, Street_name, etc. ) OWNER(Owner-ID,Owner_name,etc. ) COORDINATES(Point-ID, X, Y) SEGMENT(Segment-ID)* PARCEL(Parcel-ID, Address) 4개 관계 STREET-SEGMENT(Street-ID, Segment-ID) PARCEL-SEGMENT(Parcel-ID, Segment-ID) SEGMENT-POINT(Segment-ID, Point-ID)* OWNER-PARCEL(Owner-ID, Parcel-ID) SEGMENT-ENDPOINT(Segment-ID, Point1-ID, Point2-ID) 재배치 : 한 선분은 항상 오직 2개의 끝점을 갖음

관계의 카디날리티 유형

정규화(Normalization) 릴레이션 중복된 데이타가 없음 -> 데이타 일치성 보장

가변 길이 레코드

비정규화 릴레이션(Nested 테이블) 애트리뷰트 값으로 데이타의 집합 가능 SEGMENT_COORDINATES(Segment-ID, (X,Y)*) (X,Y)* : 별개 테이블 또는 좌표 쌍들의 리스트(즉, 가변 길이 필드) STREET_SEGMENT(Street-ID, Street_name, (Segment-ID)*) OWNER_PARCEL_SEGMENT(Owner-ID,(Parcel-ID,(SEGMENT-ID)*)*)

정보 시스템 설계 방법론 1. top-down 방법론 2. bottom-up 방법론 3. walk-through 방법론 4. prototyping 방법론 5. technology driven 방법론

객체를 위한 공간 모델 유형 1. 선분-중심 모델 2. 면적과 부피-중심 모델 0차원과 1차원 객체들의 개념적 모델링 기하학적 객체는 경계들로 정의(+내부 부분) 2. 면적과 부피-중심 모델 2차원과 3차원 객체는 매우 작은(Cell)로 구성 fractal 기하에서 점은 작은 영역 또는 작은 부피로 정의(근사) 입체는 fractal 점들의 집합으로 정의

영역과 부피를 위한 개념적 모델링

규칙적 셀 그리드 표현 1. 셀 매트릭스 표현 2. Run-length 엔코딩 GRID_CELL (X, Y, Attribute) 2. Run-length 엔코딩 셀들의 이웃하는 셀들과 동일한 값을 갖을 때 ROW_REGROUPING(Y, X_begin, X_end, Attribute) COLUMN_REGROUPING(X, Y_begin, Y_end, Attribute)

Quadtree (2차원) 4개의 링크를 갖는 계층적 데이타 구조(quadrant) 객체 표현 또는 공간 인덱스로 사용 엔코딩 : GGWBBWBWGWBBW

선형 Quadtree 정사각형 셀의 순서화

Quadtree를 사용한 다각형 모델링 QUADRANT (Zone-ID, Peano_key, Quadrant_size, Quadrant_attributes) ZONES (Zone-ID, Zone_attributes)

선형 Quadtree를 사용한 지형 모델링

확장형 Quadtree 내부와 경계를 모두 표현 (4종류의 quadrants)

결합 표현 방법 Quadrant와 선분으로 표현

확장형 Quadtree를 위한 개념적 모델 QUADRANT (Polygon-ID, Peano_key, Side_length, Type) POLY1 (Polygon-ID, Edge-ID) POLY2 (Edge-ID, Vertex1-ID , Vertex2-ID) POINT (Vertex-ID, X, Y) (  POLY2-BIS (Edge-ID, Peano_key1, Peano_key2) ) EDGE_QUADRANT (EQ_Peano_key, Edge-ID) VERTEX_QUADRANT (VQ_Peano_key, Edge1-ID, Edge2-ID, Vertex-ID)

피라미드 모델 (1/2)

피라미드 모델 (2/2) 이미지와 래스터 데이타 저장 정사각형 그리드들에 의해 표현되는 임의의 객체 모델링 이미지 (bitmap 형태) 자체 뿐만 아니라 하위 해상도를 갖는 같은 이미지도 저장 512×512, 256×256, 128×128, 64×64, ••• PYRAMID (Pyramid-ID, (Level-ID, (Locator, Colour)*)*) ① Locator : 좌표값 (x, y) (2x, 2y), (2x+1, 2y), (2x, 2y+1), (2x+1, 2y+1) ② Locator : Peano key P (4p), (4p+1), (4p+2), (4p+3)

Octtree (3차원) 8개의 링크를 갖는 계층적 데이터 구조(Octant)

선형 Octtree OCTANT (Solid-ID, Peano_key, Side_length, Matter) SOLID (Solid-ID, Attributes)

확장형 Octtree 4종류 Octants OCTANT (Solid-ID, Peano_key, Side_length, Matter, Type) POLYHEDRON1 (Polyhedron-ID, Facet-ID) POLYHEDRON2 (Polyhedron-ID, Edge-ID) POLYHEDRON3 (Edge-ID, Vertex1-ID , Vertex2-ID) POINT (Vertex-ID, X, Y) (  POLYHEDRON3-BIS (Edge-ID, Peano_key1, Peano_key1) ) FACET_OCTANT (FQ_Peano_key, Facet-ID) EDGE_OCTANT (EQ_Peano_key, Edge-ID) VERTEX_OCTANT (VQ_Peano_key, Edge1-ID, Edge2-ID, Vertex-ID)

Ruled 표면에 의한 절단을 지원하는 Octtree

지질학 객체를 위한 모델링 Octant가 지층을 표현하고 0개 이상의 시굴공(boring)을 갖음

우수한 표현의 선택 조건 1. 적절성 2. 비용 3. 유지보수 사용자의 관점과 공간 정보 시스템의 관점이 부합 시간과 공간 측면에서 최소 3. 유지보수 데이타 구조에 대한 갱신 융통성 제공 benchmark 필요 (기능과 성능 비교)

다른 표현들과의 통합 외부 모델들을 통합하여 개념적 모델 생성 사용자들이 다른 기하적 표현들을 필요로 함 (1) 하나의 표준 모델 사용 강조 (어려움) (2) 서너개의 기하학적 모델을 사용 (불일치성 문제)

통합 환경 예 (도로) 단일 표현 선택의 어려움 -> 4가지 표현의 공존

데이타베이스 설계 과정 표준 공간 표현 모델 사용

Entity-Category-Relationship(ECR) 방법 위상적 arc-node 모델에 근거한 지도 뷰 (개체 : 점 좌표, 노드, 체인) 의사 결정 시스템을 위한 공간 분석 뷰

복합 Feature 공간 기본요소 : 선, 노드, 삼각형, 다각형 공간 객체 : 공간 기본요소들로 구성 (1) 복잡(complex) feature 다른 공간 형태인 현상들의 집합 다각형(정원), 점(나무), 선(하수도), 부피(집)으로 구성된 부동산 (2) 복합(compound) feature 유사한 공간 형태인 현상들의 집합 링크들로 구성된 네트워크

복잡과 복합 Feature의 이질성

Feature 생성 (1) 공간적으로 객체들을 그룹화 (2) 애트리뷰트나 앤티티 타입에 근거하여 클러스터링 그래프 edge들을 연결, polyline의 조각들을 연결, 삼각형들로부터 tessellation 생성 (2) 애트리뷰트나 앤티티 타입에 근거하여 클러스터링 미리 계산된 인구 밀도 애트리뷰트에 근거하여 도시화 정도 분류 책상, 의자, 책꽂이, working 테이블로 구성된 사무실 (3) (1)과 (2)의 결합 특정한 애트리뷰트 값을 갖는 근접한 다각형들의 그룹 생성

공간 요소의 연결 방법 (1) 기능적 관련 (2) 계산적 관련 (3) 그룹화 두개의 공간 단위가 물리적 또는 가상적 흐름에 의해 관련됨 하수도, 전화 통화 (2) 계산적 관련 어떤 파생된 통계는 공간 표현과 관련됨 인구 밀도는 인구수 뿐만 아니라 영역에도 관련 (3) 그룹화 한 종류의 원소들은 유사성과 기능성의 기준에 근거하여 보다 큰 집합으로 그룹화됨 hamlets, villages, towns, 도시영역은 사람 거류지로 그룹화

시멘틱 데이타 모델(1/2) 확장된 E-R 모델(보다 많은 의미 포함) 1. Hypergraph Based Data Structure (HBDS)

시멘틱 데이타 모델(2/2) 2. 객체-지향 모델 generalization specialization aggregation 클래스 집합 -> 클래스 specialization 클래스 -> 클래스 집합 aggregation 애트리뷰트 집합 -> 클래스 association 클래스 집합 -> 클래스 (e.g. : road signals)

기존 시스템의 위상 데이타 구조(1/4) 1. SICAD 시스템 일종의 CODASYL 네트워크 구조 Master-Detail 시스템 내부 주소 기법이 Master와 Detail 원소들간의 위상 관계 생성 벡터와 래스터 그래픽스 통합

기존 시스템의 위상 데이타 구조(2/4) 2. ARC/INFO georelational 모델 coverage : 한 theme에 대해서 feature라 불리는 공간 단위들의 집합 각 feature는 좌표값 위치를 갖고 다른 feature(비공간 애트리뷰트 포함)들에 대해서 위상 포인터를 갖음 coverage BND(Coverage-ID, X_minimum,Y_minimum, X_maximum, Y_maximum) polygon, node, arc PAT(Coverage-ID, Polygon-ID, Polygon_area, Polygon_perimeter, Attributes) NAT(Coverage-ID, Node-ID, Arc-ID, Attributes) AAT(Coverage-ID, Arc-ID, From_node-ID, To_node-ID, Left_polygon-ID, Right_polygon-ID, Length_of_arc, Attributes) linear와 turn Length_of_arc, Arc_impedance, Arc_demand) TRN(Coverage-ID, Node-ID, (From_arc-ID, To_arc-ID, Angle_of_turn, Azimuth_degree, Turn_impedance)*) route SEC(Coverage-ID, Section-ID, Arc-ID, From_position, To_position) RAT(Coverage-ID, Section-ID, Route-ID) EVENTS(Coverage-ID, Route-ID, From_position, To_position, Attributes) surface NODE(Triangle-ID, Node1-ID, Node2-ID, Node3-ID) EDGE(Triangle-ID, (Adjacent_triangle-ID)*) ELEVATION(Node-ID, Height) COORDINATES(Node-ID, X, Y)

기존 시스템의 위상 데이타 구조(3/4) 3. SYSTEM 9 비계층 위상 구조 공간 기본요소인 node, line, surface가 포인터에 의해 서로 연결됨 공유되는 기본요소는 중복 저장되지 않음 저장 공간 절약

기존 시스템의 위상 데이타 구조(4/4) 4. TIGRIS 비계층 위상 구조 공유되는 기본요소는 중복 저장되지 않음(다른 데이타 구조) NODE(Node-ID, Class-ID, X, Y, Z) DE(DE-ID, Class-ID, Orient, Face-ID, Next-DE, Node-ID) EDGE(Edge-ID, Class-ID, Positive-ID, Negative-ID, Coord_count, Coordinates) FACE(Face-ID, Class-ID) NODE_TO_FACE(Node-ID, Node_class-ID, Face-ID, Face_class-ID) AREA_TO_FACE(Area-ID, Area_class-ID, Face-ID, LINE_TO_DE(Line-ID, Line_class-ID, DE-ID, DE_class-ID) POINT_TO_NODE(Point-ID, Point_class-ID, Node-ID, Node_class-ID)

국가 지도 데이타베이스(1/3) 1. Ordnance Survey of Great Britain (1) OSMAP 링크와 노드들이 위상적으로 구성됨 GIS를 위한 기본도로 사용 (2) OSCAR 도로와 고속도로의 중심선 정보 포함 자동차 운항, 도로 관리 및 유지 보수용 (3) OSLAND 토지 필지 다각형과 도로 주소 행정 기능 지원용

국가 지도 데이타베이스(2/3) 2. United States Census Bureau(TIGER) 인구 센서스와 매핑 작업을 결합 포인터에 의해서 연결되는 디렉토리와 리스트로 구성 (네트워크 모델 개념) C0RALS, C1RALS, C2RALS 0셀, 1셀, 2셀 위상 단위 거대한 양의 공간과 애트리뷰트 정보로 구성된 단일 레이어 데이타베이스 서너개 데이타베이스 뷰 지원 (1) 기하학적 뷰 (2) 선형 애트리뷰트 뷰 (3) 지리적 뷰 (4) 센서스 지리적 뷰

국가 지도 데이타베이스(3/3) 2. United States Gensus Bureau(TIGER)