Задача: необходимо спроектировать базу данных отрезков на прямой, заданных координатами левого и правого концов (например: [200; 400]), так что бы можно было бы максимально эффективно построить поиск для заданной точки (например с координатой 110) всех отрезков в которых она содержится. Ограничение на число таблиц нет.

Какие будут идеи?

Спасибо.

Здравствуйте, _Lexx, Вы писали:

_L>Задача: необходимо спроектировать базу данных отрезков на прямой, заданных координатами левого и правого концов (например: [200; 400]), так что бы можно было бы максимально эффективно построить поиск для заданной точки (например с координатой 110) всех отрезков в которых она содержится. Ограничение на число таблиц нет.

Если это единственный критерий — то храни левый и правый конец отрезка.

Здравствуйте, King Oleg, Вы писали:

KO>Здравствуйте, _Lexx, Вы писали:

_L>>Задача: необходимо спроектировать базу данных отрезков на прямой, заданных координатами левого и правого концов (например: [200; 400]), так что бы можно было бы максимально эффективно построить поиск для заданной точки (например с координатой 110) всех отрезков в которых она содержится. Ограничение на число таблиц нет.

KO>Если это единственный критерий — то храни левый и правый конец отрезка.

Ну, хранить-то мне их по-любому придется так.
Я точно знаю, что это не оптимальное решение — одна таблица на все отрезки.
Причем на сколько я понимаю, фишка в использование нескольких таблиц.
То есть либо из надо как-то хитро при добавление связать.
Например: каждый указывает на отрезок, в котором он целиком лежит (если таковой есть).
И потом можно найдя вхождение точки в одни отрезок тут же выдать несколько других по этим связям (которые его покрывают).

Здравствуйте, _Lexx, Вы писали:

1. Это реальная задача или учебная? В принципе и одна таблица с двумя составными индексами справится достаточно неплохо (или кластерная с одним индексом).

2. Поиск только средствами SQL или произвольный (например, движок может выбрать таблицу, в которой искать)?

3. Координаты точек только целые?

4. Примерная статистика данных — ширина области определения, то есть область, накрывающая все отрезки; средняя длина самого отрезка?

Здравствуйте, _Lexx, Вы писали:

_L>Например: каждый указывает на отрезок, в котором он целиком лежит (если таковой есть).
_L>И потом можно найдя вхождение точки в одни отрезок тут же выдать несколько других по этим связям (которые его покрывают).

Подозреваю, это будет много медленнее независимой проверки отрезков. Переход по связи — долгая операция; у нас все-таки не сетевые БД, а реляционные.

Здравствуйте, Softwarer, Вы писали:

S>Здравствуйте, _Lexx, Вы писали:

S>1. Это реальная задача или учебная? В принципе и одна таблица с двумя составными индексами справится достаточно неплохо (или кластерная с одним индексом).

учебная.

S>2. Поиск только средствами SQL или произвольный (например, движок может выбрать таблицу, в которой искать)?

sql only

S>3. Координаты точек только целые?

нет — float

S>4. Примерная статистика данных — ширина области определения, то есть область, накрывающая все отрезки; средняя длина самого отрезка?

не совсем понял вопрос. поясни подробнее если не сложно?

Здравствуйте, _Lexx, Вы писали:

S>>4. Примерная статистика данных — ширина области определения, то есть область, накрывающая все отрезки; средняя длина самого отрезка?

_L>не совсем понял вопрос. поясни подробнее если не сложно?

Для учебной задачи вряд ли на него можно ответить — имелось в виду, над какими именно данными будет осуществляться поиск. Если в курсе логики стоимостного оптимизатора и статистики для него — тот же принцип.

Здравствуйте, _Lexx, Вы писали:

Скажем так, насколько я в курсе, для решения подобных задач используется так называемый R-индекс. Я понаслышке знаком с этой областью; вкратце, это дерево переменной высоты, в котором каждый узел покрывает некую область пространства (отрезок в одномерном случае). То есть часть прямой, покрытая отрезками, делится на несколько меньших отрезков, те — на еще меньшие итп; соответственно, можно довольно быстро перейти от корня к отрезкам, "близким" определенной точке. Не знаю, как решается коллизия, если область нельзя разбить на меньшие так, чтобы не разрезать один из реальных отрезков. Проблема в том, что если мы говорим об SQL и не подразумеваем Oracle (где есть возможность создания собственных типов индексов, а r-индексы реализованы) то вряд ли удастся найти эффективное решение на основе имитации R-индекса.

Практически, полагаю, я бы просто сделал партиционированную таблицу (партиции по диапазонам значений левых границ отрезка, субпартиции по диапазонам значений правых границ). В этом случае обычный запрос с условием X between Left and Right эффективно отбросит партиции, в которых заведомо нет нужных отрезков. Эта возможность, насколько я знаю, доступна уже не только в Oracle.

Стандартное решение, о котором всегда следует помнить — выделение стандартных областей. Допустим, есть отрезок с координатами 1,1 ... 2,6. Мы можем сказать, что он пересекает стандартные отрезки [1..2] и [2..3]. Поэтому — вставим во вспомогательную таблицу записи

id, 1
id, 2

где id — идентификатор отрезка. Теперь, желая найти все отрезки, содержащие X, можно выполнить следующий запрос:

select
  p.id,
  p.left,
  p.right
from
  MainTable p,
  ServeTable s
where 
  s.value = trunc ( :x ) and
  s.id = p.id and
  :x between p.left and p.right

В этом случае довольно просто построить пример, где этот метод будет намного эффективнее простого поиска по одной таблице и столь же легко построить пример, где он будет намного менее эффективным.

Что-то читаю ответы и рассуждения и всё сильнее тупеют мозги мои...

Кажись задачка то сводилась только к тому, что есть прямая, на ней куча отрезков, описываемых своими левыми и правыми координатами, задача — найти все отрезки в которые входит определенная координата...
Чего ж проще?
(Извеняюсь — пример на MSSQL2000)

declare @t table(l_bord float, r_bord float,
        i int identity            --вспомогательная колонка,
                        --в случае использования постоянных
                        --или временных таблиц не нужна
        unique(l_bord , r_bord, i)    --иммитация создания покрывающего индекса
        )
--пример заполнения данными
insert @t values(15, 20)
insert @t values(150, 225.6)
insert @t values(321, 456)
insert @t values(220, 230)
insert @t values(1, 1532)
insert @t values(555, 777)

declare @point float
set @point = 223.7    --искомая точка

--собственно запрос
select * from @t
    where l_bord <= @point and r_bord >= @point

Или заблуждаюсь?

Здравствуйте, _Lexx, Вы писали:

_L>Спасибо.
Если отобразить начала и концы отрезков на оси Y и X, то получим равносторонний прямоугольный треугольник — геометрическое место точек, обозначающих все возможные отрезки. Поиск отрезков, содержащих точку A, задается предикатом X > A && Y < A. Геометрически, это четверть плоскости, ориентированная вправо-вниз, с вершиной в точке (A, A).
Очевидно, не существует скалярного индекса, который позволил бы найти все нужные точки за один index seek. Для небольших задач index scan уже будет вполне неплох, особенно если сделать два композитных индекса по L, R и по R,L и выбирать один из них в зависимости от того, к какому концу диапазона ближе точка A.
Если же эффективности index scan недостаточно, то надо привлекать многомерные индексы. Я думаю, что R-Tree здесь будет не очень эффективно, из-за специфической формы регионов, по которым ведется поиск. Скорее всего, можно построить какое-нибудь достаточно эффективное решение, специфичное для данного случая.

Здравствуйте, tpg, Вы писали:
tpg>Или заблуждаюсь?
Нет, не заблуждаешься. Но предложенное тобой решение не намного эффективнее, чем

public static IEnumerable<Point> FilterPoints(int a)
{
  foreach(Point p in Points)
      if (p.x<a && p.y>a)
            yield return p;
}

Для приведенного тобой примера разницы в способах измерить не удастся. Но добавь в список миллионов пятьдесят этих точек, и твой алгоритм уснет навеки. Интересны сублинейные по производительности решения, т.е. затраты должны расти медленнее, чем O(N). Для больших объемов крайне не рекомендуется выходить за пределы O(logN).

Здравствуйте, _Lexx, Вы писали:

_L>Задача: необходимо спроектировать базу данных отрезков на прямой, заданных координатами левого и правого концов (например: [200; 400]), так что бы можно было бы максимально эффективно построить поиск для заданной точки (например с координатой 110) всех отрезков в которых она содержится. Ограничение на число таблиц нет.

_L>Какие будут идеи?
Я, конечно, не волшебник, я тока учусь, но...
А что если не хранить координаты отрезков, привязать систему координат к прямой и хранить координаты (а точнее координату) начала и конца отрезка в привязанной к приямой системе координат. Если не понятно, ну... эээ... сделать доп. систему координат и пустить её ось X по заданной прямой, ясен пень что какую-нить точку на главной системе координат примем за ноль -- поличться, что каждую точку на прямой можно будет задать одной координатой.
Если прямая одна и она железно на прямой, то вааще всё сводится к переводу координат точки из "глобальной" СК к привязанной и решению задачи о вхождении в интервал.
Если прямая и точка чёртзнаетгде то надо будет хранить k и b прямой (те что в Y=k*X+b) и множ координат отрезков на данной прямой. Потом поискать в таблице с прямыми (с k и b) какие из них подойдут для переданных координат точки — что-то типа:

SELECT Lines.Line_ID FROM Lines WHERE @PointY = Lines.k * @PointX + Lines.b

А потом опять перевести координаты точки в координаты СК привязанной к прямой и "поиск вхождения в интервал".
Ну... вот как-то так... надо будет две таблицы: с прямыми {k, b} и с координатами отрезков {Start, End}

Всё! Надеюсь не глупость вышла.

Здравствуйте, Sinclair, Вы писали:

S>Для приведенного тобой примера разницы в способах измерить не удастся. Но добавь в список миллионов пятьдесят этих точек, и твой алгоритм уснет навеки.

C 50 лимонами искомых отрезков куда входит 1 точка любой алгоритм уснет, самый эффективный — тупой таблескан.
Приведенный мной алгоритм, как и любой индексный поиск эффективен лишь при достаточно малом числе вхождений в общее множество (высокая избирательность индекса). А вот тут, думаю, оптимизаторы и должны сказать свое слово в выборе алгоритма.
Или мы про разное?

Здравствуйте, tpg, Вы писали:
tpg>C 50 лимонами искомых отрезков куда входит 1 точка любой алгоритм уснет, самый эффективный — тупой таблескан.
tpg>Приведенный мной алгоритм, как и любой индексный поиск эффективен лишь при достаточно малом числе вхождений в общее множество (высокая избирательность индекса). А вот тут, думаю, оптимизаторы и должны сказать свое слово в выборе алгоритма.
а, я не заметил индекса. Тем не менее, речь идет о том, что скалярный индекс здесь рискует оказаться малоэффективным. Грубо говоря, при поиске отрезков, покрывающих точку c координатой = MAX(l_bord) индекс скан захватит все точки. Для точек близких к "левой границе" сканирование ограничится достаточно небольшим подмножеством.
Для данной задачи можно ввести два индекса — (L, R) и (R, L) и надеяться на то, что оптимизатор выберет лучший в зависимости от значения @point. Тем не менее, для точек близких к середине производительность все равно будет неоптимальной.
tpg>Или мы про разное?
Я имею в виду пятьдесят миллионов отрезков. Объем результата, конечно же, зависит от распределения данных.

ZAM>Я, конечно, не волшебник, я тока учусь, но...
ZAM>А что если не хранить координаты отрезков, привязать систему координат к прямой и хранить координаты (а точнее координату) начала и конца отрезка в привязанной к приямой системе координат.
Увы, отрезки уже привязаны к ровно одной прямой.

Здравствуйте, Sinclair, Вы писали:

ZAM>>Я, конечно, не волшебник, я тока учусь, но...
ZAM>>А что если не хранить координаты отрезков, привязать систему координат к прямой и хранить координаты (а точнее координату) начала и конца отрезка в привязанной к приямой системе координат.
S>Увы, отрезки уже привязаны к ровно одной прямой.
Почему ж "увы" тогда. Значит достаточно хранить по координате начала и конца отрезка, а потом переводить координаты точки в координату на прямой и сравнивать.

Здравствуйте, ZAMUNDA, Вы писали:
S>>Увы, отрезки уже привязаны к ровно одной прямой.
ZAM>Почему ж "увы" тогда. Значит достаточно хранить по координате начала и конца отрезка, а потом переводить координаты точки в координату на прямой и сравнивать.
Почитай остальные сообщения в треде.

Здравствуйте, Sinclair, Вы писали:

S>Если отобразить начала и концы отрезков на оси Y и X, то получим равносторонний прямоугольный треугольник
Таких не бывает

Здравствуйте, wildwind, Вы писали:

S>>Если отобразить начала и концы отрезков на оси Y и X, то получим равносторонний прямоугольный треугольник
W>Таких не бывает
Ой, равнобедренный.