Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
Всем привет.
Есть две таблицы T и S
CREATE TABLE T
(
ID BIGINT PRIMORY KEY,
ST_DT DATETIME,
ED_DT DATETIME,
)
CREATE TABLE S
(
ID BIGINT PRIMORY KEY,
ST_DT DATETIME,
ED_DT DATETIME,
)

Имеем набор в T (1, 2010-01-01, 2011-01-01) и в S {(1, 2010-02-01, 2010-05-01), (1, 2010-07-01, 2010-08-15)}
На выходе нужно получить
(1, 2010-01-01, 2010-01-31)
(1, 2010-05-02, 2010-06-30)
(1, 2010-08-16, 2011-01-01)
Может кто знает оптимальный алгоритм?
7 авг 12, 10:42    [12973136]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902


К сообщению приложен файл. Размер - 8Kb
7 авг 12, 10:44    [12973154]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Glory
Member

Откуда:
Сообщений: 104751
Какая же это разница множеств
Это какое пересечение периодов. Вернее нахождение дырок в периодах
7 авг 12, 10:46    [12973172]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
Glory,
Разность двух множеств — это теоретико-множественная операция, результатом которой является множество, в которое входят все элементы первого множества, не входящие во второе множество. Обычно разность множеств A и B обозначается как A\setminus B, но иногда можно встретить обозначение A-B и A\sim B.
7 авг 12, 11:12    [12973428]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Glory
Member

Откуда:
Сообщений: 104751
Yagrus2
Разность двух множеств — это теоретико-множественная операция, результатом которой является множество, в которое входят все элементы первого множества, не входящие во второе множество. Обычно разность множеств A и B обозначается как A\setminus B, но иногда можно встретить обозначение A-B и A\sim B.

Каким боком это относится к вашей задаче то ?
Вы хотите получить из таблицы данные, которых там нет.
7 авг 12, 11:18    [12973487]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
Glory, Ну это как посмотреть.
Каждой записи первой таблице соответствует временной интервал. Его можно изобразить на числовой оси в виде отрезка, который состоит из точек. Касаемо моего примера можно заметить, что день 2010-01-01 есть в первой табличке, но отсутствует во второй!
7 авг 12, 11:29    [12973619]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
Glory,
По элементом я понимаю момент времени.
Разница отрезков и есть разница множеств.
7 авг 12, 11:32    [12973651]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Glory
Member

Откуда:
Сообщений: 104751
Yagrus2
Glory, Ну это как посмотреть.

Как не посмотри, сервер все равно не может выбрать данные, которых у него нет.
Поэтому ему нужны все даты, из которых он может отфильтровать ненужные вам.
Вот и "нарисуийте" серверу "числовую ось в виде отрезка, который состоит из точек", только в объектах, которые понятны серверу
7 авг 12, 11:33    [12973661]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
aleks2
Guest
Получение дырок очень простая операция. Достаточно осознать два элементарных факта

1. Количество "начал" дырок в точности равно количеству "концов" дырок. И их можно упорядочить.
2. Дырка начинается там, где фсе имеющееся заканчивается и заканчивается там, где что-то начинается.
7 авг 12, 11:34    [12973670]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Читатель неместный
Guest
а если чтото может пересекаться с чемто из своей же банки, то алгоритм не пройдет!! ...?
7 авг 12, 11:38    [12973713]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
Читатель неместный,
У меня в обоих таблицах интервалы не пересекаются.
7 авг 12, 11:42    [12973760]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
aleks2,
Поясните поподробней.
Если заджойнить все отрезки первой и второй таблицы получим две записи, а "дырки" три.
7 авг 12, 11:46    [12973810]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
MyNiGoo
Member

Откуда:
Сообщений: 234
слей все уникальные даты в один столбец
поджойни его сам на себя со смещением на одну строчку, получишь все периоды, которые у тебя есть
и теперь вычитай, что хочешь и откуда хочешь
7 авг 12, 11:57    [12973939]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
MyNiGoo
Member

Откуда:
Сообщений: 234
алгоритм оптимальный, можно даже с cte сделать, красиво будет
7 авг 12, 11:58    [12973959]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
iap
Member

Откуда: Москва
Сообщений: 47052
Yagrus2
aleks2,
Поясните поподробней.
Если заджойнить все отрезки первой и второй таблицы получим две записи, а "дырки" три.
Каждое начало отрезка из второй таблицы - это потенциальный конец результирующей дырки,
а каждый конец отрезка второй таблицы - это потенциальное начало результирующей дырки.
Надо только скорретировать границу самой левой дырки по границе отрезка первой таблицы
и границу самой правой дырки по правой границе отрезка первой таблицы.

По-хорошему, надо бы сначала определить границы отрезков из первой таблицы с учётом возможных пересечений
разных записей этой таблицы и границы дырок с учётом возможных пересечений периодов во второй таблице.
Можно оба полученных множества оформить в виде CTE для простоты восприятия.
И окончательный SELECT делать уже из этих CTE.
7 авг 12, 12:00    [12973987]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
aleks2
Guest
Читатель неместный
а если чтото может пересекаться с чемто из своей же банки, то алгоритм не пройдет!! ...?

Это тока у неместных.

declare @T TABLE 
(
ID BIGINT ,
ST_DT DATETIME,
ED_DT DATETIME
)
declare @S TABLE 
(
ID BIGINT ,
ST_DT DATETIME,
ED_DT DATETIME
)

insert @T
select 1, '20100101', '20110101'

insert @S
select 1, '20100201', '20100501'
union all
select 1, '20100701', '20100815'

declare @b table (id int, d DATETIME, n int identity primary key clustered)
declare @e table (id int, d DATETIME, n int identity primary key clustered)

insert @b (id, d)
select ID, ED_DT from @S
union all
select ID, ST_DT from @T T where ST_DT<(select min(ST_DT) from @S x where x.ID=T.ID )
order by 1, 2

select * from @b

insert @e (id, d)
select ID, ST_DT from @S
union all
select ID, ED_DT from @T T where ED_DT>(select max(ED_DT) from @S x where x.ID=T.ID )
order by 1, 2

select * from @e

select b.d ST, e.d EN
from @b b inner join @e e on b.n=e.n -- and b.id=e.id
7 авг 12, 12:43    [12974428]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
MyNiGoo
Member

Откуда:
Сообщений: 234
use tempdb
go

create table t(
	id int
	,startDate datetime2
	,endDate datetime2
)

create table s(
	id int
	,startDate datetime2
	,endDate datetime2
)

insert into t values (1, '20100101', '20110101')
insert into s values (1, '20100201', '20100501'),(2, '20100701', '20100815') 

;with d as (
	select *, row_number() over (order by q.dd) rnb from(
	select t.startDate dd from t
	union
	select t.endDate from t
	union
	select s.startDate from s
	union
	select s.endDate from s
	) as q
)
select dl.dd, dr.dd from d dl join d dr on dl.rnb = dr.rnb - 1
except
select s.startDate, s.endDate from s

drop table t
drop table s


какие там границы включать-исключать думайте сразу, я считаю, что в бд диапазоны дат лучше всегда хранить отрезками (т.е. начало-конец включительно)
7 авг 12, 14:43    [12975543]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
Yagrus2
Member

Откуда: Москва
Сообщений: 902
Спасибо за предложенные варианты! Буду их курить)
7 авг 12, 16:05    [12976200]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм помучения разницы множеств  [new]
NIIIK
Member

Откуда: Россия, Ростовская область, г. Таганрог
Сообщений: 1295
Yagrus2,

Офигеть, две темы за сегодня со словом "алгоритм" в БД.

Да это БД/СУБД, нельзя тут программерского мышления!
7 авг 12, 16:14    [12976255]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить