단일 차원 내에서 겹치지 않는 범위의 데이터 구조

단일 차원 내에서 겹치지 않는 범위를 저장할 수있는 데이터 구조가 필요합니다. 차원의 전체 범위를 완전히 다 커버 할 필요는 없습니다.단일 차원 내에서 겹치지 않는 범위의 데이터 구조

예를 들어 회의실 스케줄러가 있습니다. 크기는 시간입니다. 두 가지 일정이 겹칠 수는 없습니다. 회의실이 항상 예약되지는 않습니다. 다시 말해, 주어진 시간 동안 최대 하나의 스케줄이있을 수 있습니다.

빠른 해결책은 시작 및 종료 시간을 저장하는 범위입니다.

Range { 
    Date start 
    Date end 
}

이 비 규격화되고 겹치는 시행 않음 용기를 필요로한다. 인접한 두 범위의 경우 이전 '끝은 다음 시작과 중복됩니다.

또 다른 체계는 각 범위에 하나의 경계 값을 저장하는 것을 포함 할 수 있습니다. 그러나 일련의 연속 된 범위의 경우 범위보다 경계 값이 하나 더 많습니다. 같을 수

BrBrB

데이터 구조를

B = 경계 값 R = 범위

: 시퀀스가 경계 값 및 범위가 교대로 표현 될 수있는이 이겨내
을
Boundary { 
    Date value 
    Range prev 
    Range next 
} 

Range { 
    Boundary start 
    Boundary end 
} 
본질적으로 교대 유형으로 이중 연결된 목록입니다.

궁극적으로 내가 사용하는 모든 데이터 구조는 메모리 (응용 프로그램 코드)와 관계형 데이터베이스로 표현됩니다.

나는 학구적으로나 업계에서 시도한 해결책이 무엇인지 궁금합니다.

출처

2008-10-17 Steve Kuo

정규화 된 데이터를 나타내는 방법은 각 시간 단위에 대한 레코드를 저장하는 것입니다. 이는 회의 예약 응용 프로그램의 예에서 수행 할 수 있습니다. 귀하의 제약 조건이 연속 범위의 경우

(RoomId, StartTime)

에 대한 고유 제약 조건이 될 것입니다, 당신은 반드시 두 가지, 하나 개의 경계와 두 번째 경계 또는 길이 중 하나를 저장해야합니다. 그것은 일반적으로 당신이 전용으로 사용하기 때문에

가

(startBoundary < endBoundary)

출처

2008-10-17 00:32:10 Sklivvz

이중 연결리스트가 잘 작동하는 추가적인 제약 조건 종류

(boundary not between colBoudaryA and colBoundaryB)

모두 경계에 제약을 생성 한 다음 두 번째 경계를 저장하고 수행한다 범위가 채워지는만큼 많은 메모리가 필요하며 삽입시 겹치는 부분 만 확인하면되므로 그 시점에서 그렇게 할 일이 거의 없습니다. 겹치면 새 항목이 거부됩니다.

 
RoomID 
ReservationID 
PreviousReservationID 
NextReservationID 
StartTimeDate 
EndTimeDate 
Priority 
UserID

우선 순위 및 사용자 ID는 새로운 항목을 삽입하는 동안 방해가되지 않는 낮은 우선 순위 항목을 '노크'할 수 있도록 (교수가 학생 그룹보다 더 영향력이있을 수 있습니다) 우선 순위를 가지고 일정을 허용하고, 사용자 ID를 사용하면 충돌이있는 회의 구성 도우미로 전자 메일을 보낼 수 있습니다.

검색을 최적화 할 수 있도록 매일 첫 회의를 가리키는 표를 추가하는 것이 좋습니다.

-Adam

출처

2008-10-17 00:33:46

많은 당신이 데이터 될 거에요에 따라 달라집니다, 따라서 작업을 효율적으로 할 필요가있다. 그러나, 시작 부분과 끝 부분의 설정자에있는 논리를 가진 범위의 이중 연결된 목록을 고려하여 이웃과 겹치는 지 여부를 확인하고 예외가 있으면 축소합니다. 그러나 시도한 내용을 처리하려고합니다. 오버랩).

이렇게하면 예약 된 기간의 읽기 쉬운 링크 된 목록이 제공되지만 중복되지 않는 규칙을 유지 관리해야하는 컨테이너는 없습니다.

출처

2008-10-17 00:34:03 stevemegson

Constraint Programming 세계에서 "단항 리소스"제약 조건이라고합니다. 이 분야에 대한 많은 연구가 있습니다. 특히 이벤트 시간이 고정되어 있지 않은 경우와 각 이벤트 시간 슬롯을 찾아야하는 경우가 있습니다. 문제를 일으키는 상용 C++ 패키지가 있으며 Ilog CP이 더 많습니다.하지만 과도한 사용 가능성이 있습니다. eclipse (IDE와 관련이 없음)이라고 불리는 다소 오픈 소스 버전도 있습니다.

출처

2008-10-17 01:21:36

(데이터베이스 세계에서) 중첩되지 않는 범위를 결정하기 위해 여러 행을 비교해야하기 때문에 이것은 간단합니다. 분명히, 정보가 메모리에있을 때, 시간순으로리스트와 같은 다른 표현이 가능하다. 그래도 목록에서조차도 '시작 + 끝'표기법을 사용하는 것이 가장 좋을 것이라고 생각합니다.

주제에 관한 전체 책 - '임시 데이터베이스'처리의 일부. Darwen, Date 및 Lorentzos는 ""과 (극단적으로 다른 극단의) "Developing Time-Oriented Database Applications in SQL", Richard T. Snodgrass, Morgan Kaufmann Publishers, Inc., 샌프란시스코, 1999 년 7 월, 504 페이지, xxiii 페이지, ISBN 1-55860-436-7. 인쇄본은 절판되었지만 자신의 웹 사이트 cs.arizona.edu에서 PDF로 볼 수 있습니다 (Google 검색을 사용하면 쉽게 찾을 수 있습니다).

관련 데이터 구조 중 하나는 R-Tree입니다. 이것은 2 차원 구조에 종종 사용되지만 1 차원 구조에도 효과적입니다.

간격을두고 "Allen's Relations"을 찾을 수도 있습니다. 도움이 될 수도 있습니다.

출처

2008-10-17 03:51:33

시작 시간과 기간을 저장하는 데 성공했습니다. 중복에 대한 시험은 내가 테스트를하지 않고 생각 뭔가

WHERE NOT EXISTS (
    SELECT 1 FROM table 
    WHERE BeginTime < NewBeginTime AND BeginTime + Duration > NewBeginTime 
) 
AND NOT EXISTS (
    SELECT 1 FROM table 
    WHERE NewBeginTime < BeginTime AND NewBeginTime + NewDuration > BeginTime 
)

같은 것, 그러나 희망 당신은 겹치지 않는 간격으로 들어 시작 지점과 그럴 수 그저 당신 간격을 드리프트

출처

2009-04-19 13:35:17 dkretz

를 얻을. 이 구조체에 새 간격을 추가 할 때 시작점과 끝점이이 간격 집합에 속하지 않는지 확인할 수 있습니다. 어떤 포인트 X가 간격 설정에 속하는지 확인하려면 이진 검색을 사용하여 가장 가까운 시작 지점을 찾고 X가 간격에 속하는지 확인하십시오. 이 방법은 수정 작업에 적합하지 않습니다.
너는 Interval tree 구조를 볼 수있다 - 겹치지 않는 간격을 위해 그것은 최적의 질의와 수정 동작을 가진다.

출처

2010-07-26 14:28:20 Dmitry

행운의 (!)을 사용하면 Postgres를 사용할 수 있으므로 tstzrange 열을 사용하고 겹침을 방지하기 위해 제한 조건을 적용 할 수 있습니다. 범위 유형을 사용할 때의 보너스는 본질적으로 시작보다 더 큰 시작을 방지한다는 것입니다.

ALTER TABLE "booking" 
ADD CONSTRAINT "overlapping_bookings" 
EXCLUDE USING gist ("period" WITH &&, "room" WITH =);

당신은 확장자없이 지원되지 않습니다 & &를 사용하여 요점을 만들기로, CREATE EXTENSION IF NOT EXISTS btree_gist해야 할 수도 있습니다.

출처

2014-09-30 03:57:13

단일 차원 내에서 겹치지 않는 범위의 데이터 구조

답변

관련 문제