Xpoint
   [напомнить пароль]

Поиск в глубину

Метки: [без меток]
2009-09-07 10:30:04 [обр] Филипп Ткачев(0/115)[досье]

Для сайта реализована система меток. Метки пришиваются к статьям, страницам, новостям через таблицу пересечений.
Имеется страница с выводом этих меток и поиском по ним.
При выборе какой-либо метки хочется подкрашивать другие метки, которое связаны с текущей через контент, но еще и с указанием глубины связи.
Т.е. по сути это вывод релевантности других меток текущей.

Структура таблицы

CREATE TABLE /*!32312 IF NOT EXISTS*/ `xlabel` (
  `id` int(11) unsigned NOT NULL auto_increment,
  `module` int(11) unsigned NOT NULL,
  `object` int(11) unsigned NOT NULL,
  `label` int(11) unsigned NOT NULL,
  PRIMARY KEY  (`id`),
  UNIQUE KEY `id` (`id`),
  UNIQUE KEY `glob` (`label`,`module`,`object`)
) ENGINE=MyISAM AUTO_INCREMENT=194 /*!40100 DEFAULT CHARSET=utf8*/;
спустя 22 часа [обр] Филипп Ткачев(0/115)[досье]
Пока в голову пришла идея создать хранимую процедуру с курсором внутри и ее рекурсивным вызовом. Естественно с обрывом рекурсии на определенной глубине.
Кстати, не сказал, что используется СУБД MySQL, что в свою очередь накладывает ограничения.
спустя 1 час 21 минуту [обр] Thirteensmay(0/157)[досье]
Уточните что значит "связаны через контент", допустим есть некоторый контент (страница) C1, на ней есть метки M1 и M2, очевидно что они связаны через этот контент, предполагаю что у вас есть другие "контенты", и в них есть другие метки, например С2 с меткой M3 и С3 c M4. Как прослеживается взаимосвязь между разными контентами ? Предполагаю что существует какая то структура контентов ?
спустя 7 минут [обр] Филипп Ткачев(0/115)[досье]

xlabel - таблица пересечений между таблицей с метками и таблицами с контентом.
module - переключатель типа контента (т.е. новости, статьи etc...)
object - поле с идентификатором конкретного контента.
label - идентификатор метки.

Связь прослеживается тогда, когда module и object совпадают.

С1 с метками М1 и М2. С5 с меткой М2 и М4.

С1-М2-С5
M2-C5-M4
C1-М2-С5-М4

спустя 1 час 53 минуты [обр] Thirteensmay(0/157)[досье]
"Связь прослеживается тогда, когда module и object совпадают" - ниасилил, из примера вижу что связь между контентами прослеживается по совпадению меток. Т.е. если какие либо 2 контента имеют одинаковую метку то они считаются связанными, а связь меток через контент означает что метки считаются связанными если они располагаются в связанных контентах. Связанность контентов на заданную глубину при этом вычисляется рекурсивно (что не есть хорошо хотябы с точки зрения производительности, т.к. будет выполняться каждый раз). Правильно ли я все понял прежде чем предлагать варианты ?
спустя 15 минут [обр] Алексей Севрюков(0/1292)[досье]
Thirteensmay[досье] Короче, как я понял: имеется основной элемент и его метки, имеются вспомогательные элементы и их метки. Нужно вывести список меток вспомогательных меток, при условии что вспомогательные элементы содержат те же метки что и основной элемент.
P.S. Перечитал Ваш пост, вы тоже самое написали, только другим языком )
спустя 22 минуты [обр] Филипп Ткачев(0/115)[досье]

xlabel:

moduleobjectlabel
1c1m1
1c1m2
1c2m3
1c3m4
1c5m2
1c5m4
2n1m1
2n2m1

Смотрите, для меток M1 и М2 можно заметить, что и module и object одинаковы: m1 -> c1 -> m2 -> c5 -> m4.
На входе у меня есть только метка M1, потом я добираюсь до других по цепочке. Если получается несколько цепочек, то нужно их отсортировать по минимальному кратчайшему пути.
Мне кажется, что алгоритм в любом случае должен быть рекурсивным, глубина рекурсии будет ограничена 3-мя шагами, иначе будет очень накладно по производительности.
Это чем-то похоже на "друзья друзей", если взять социальные сети в пример, но только с большей глубиной: "друзья друзей друзей".

спустя 18 минут [обр] Thirteensmay(0/157)[досье]
Т.е. в дополнение вышеопределенному мной и Алексеем, надо учитывать что одна и та же метка может использоваться как среди новостей так и среди статей, но связь надо прослеживать только в пределах одного типа контента (module) ?
спустя 12 минут [обр] Филипп Ткачев(0/115)[досье]

Связь может быть через любой модуль, т.е. наличие модуля не влияет на связь. Но наличие столбца модуль обусловлено возможностью совпадения идентификаторов контента.
Например и новость и страница может иметь id = 1.

Пример таблицы xlabel

idmoduleobjectlabel
1111
2112
3211
4221
5212
спустя 3 часа 44 минуты [обр] Thirteensmay(0/157)[досье]

Ладно, детали не до конца, но в общем случае понятно.

Очевидно что без рекурсии в конечном случае не обойдется, однако есть как минимум следующие соображения:

1 - Продолжить приближать процесс к базе, вы уже съехали с внешних скриптов на хранимые процедуры, с целью дальнейшего уменьшения накладных расходов можно реализовать все в пределах SQL, т.е. склонить базу к скрытой низкоуровневой SQL рекурсии, а не выполнять ее явно сверху, сэкономив при этом на постоянных переключениях контекста между SQL и ХП. Ваша задача, а именно рекурсия, очень хорошо отзывается на такого рода оптимизацию, выигрыш в производительности может достигать десятка раз. Однако т.к. MySQL не поддерживает иерархических и аналитических SQL конструкций, этот метод вам не доступен, имейте ввиду на будущее ;)

2 - Облегчить рекурсию за счет преподготовки данных, например организовать синтетическую таблицу с уже готовыми связями контентов, тогда вычислять связанность метог станет легче. Очевидно что например добавление метки операция гораздо менее частая чем их просмотр, соответственно выгодно заполнять нашу синтетическую таблицу автоматически триггерами по факту добавления метки, т.е. триггер будет запускать процедуру пересчета связей контентов с учетом добавленной метки. В результате нагрузка на базу снизится за счет более редкого просчета связанности контентов, ускорения просчета связанности меток, и более плавного распределения нагрузки. Вообще преподготовка данных (синтетические таблицы) это общий подход, суть надеюсь ясна, по поводу приложения к вашей задаче думайте сами.

3 - Ваша задача не требует произвольной вложенности, это не многоуровневая иерархия которая частенько встречается, вам достаточно 3..4 уровней, ибо больше не просто будет медленно, а будет бесполезно с логической точки зрения, т.к. теряется смысл и пользователю такое нагромождение не нужно. А раз так то по идее можно обойтись вложенными select или union.

спустя 4 часа 59 минут [обр] German[досье]

задача интересная вроде, но непонятная, хотя простейшая табличка вроде... Хорошо бы иметь конкретный пример. Вообще в таблице пересечений вроде ни к чему `id`, зачем вы считаете эти пересечения?

почему бы не предложить какой-то пример

1 - статья про кур S 1 2
2 - статья про медведей S 2
3 - статья про апельсины S 3
4 - статья про презервативы S 4
5 - статья про приготовление торта S 5
6 - статья обо всем S 1 2 3 4
7 - статья про приготовление куринного бульона S 1 3

метки
1 - о курах и в этом роде
2 - о животных
3 - кулинария
4 - про секс

Но вроде у вас как-то не так? Или в этом роде?

спустя 11 часов [обр] Филипп Ткачев(0/115)[досье]

German[досье], именно так.

Thirteensmay[досье], спасибо, подумаю...

спустя 35 минут [обр] Thirteensmay(0/157)[досье]
Филипп Ткачев[досье] Сделать рекурсивную ХП, посмотреть что получится, если будет тормозить тогда можно думать, но скорее всего ввиду того что меток не миллион и уровней вложенности всего 3..4 все будет нормально и так.
спустя 3 часа 5 минут [обр] German[досье]

если похоже на то, что я написал, то самым быстрым решением будет создать к-во столбцов по числу меток
NLLLLLLLLLLLLLLLLLLLLLLLLLLLLSSSS
N - стоблбец с номером статьи
L - логический столбец true|false соответствующий одной метке
S - номера статей самых близких ссылок (столько столбцов сколько надо ссылок)

Cron запускает обновление SSSS полей таблицы

При этом можно заменить все логические столбцы одним числовым столбцом, в котором можно разместить до (если не ошибаюсь) 64 меток. Это наверно чуть медленнее чем 64 логических столбца, но нуна проверить

Рекурсия, понятно, не нужна

спустя 1 час 26 минут [обр] German[досье]

хотя, наверно я упрощаю, а требуется универсальное решение с неограниченным к-вом меток... тогда рекурсия, деваться некуда

Я еще не понял, что окончательно это значит
module object label

В моем представлении пока есть только конструкция
object label
То есть номер статьи, и номер метки. В таком случае я бы оставил только эти столбцы, дав им общий индекс
PRIMARY KEY (object, label) причем больше никаких индексов сюда вроде тогда не надо, толку от них не предвидится

Мне придется делать нечто подобное через 3-4 месяца, так что интерес у меня недетский

Если module это нечто вроде типа статьи:
- новость
- интервью
- статья

То включать это в таблицу стоит только в двух случаях
- если нумерация {новостей | интервью} осуществляется раздельно
- если module как -то влияет на метки (это сложный случай)

PS если все-таки существует простой способ выделять 64 (128, 256, 6400 - счетное к-во) актуальных меток, — меток, по которым будет производится анализ взаимосвязанности статей — то очень даже можно вернуться к предложенной мной модели анализа — она-то будет работать мгновенно и эффективно. В этом случае можно считать мою модель как бы диспетчером взаимосвязанности

То есть актуальные номера меток из вашей таблицы переназначаются в "мою" для анализа
по типу yours -> mine
1 -> 1
2 ->2
34 ->3
454 -> 4
дальше все как предложено

спустя 19 часов [обр] Филипп Ткачев(0/115)[досье]
German[досье], мне очень не нравится ваш подход.
Лично я предполагаю использовать хранимую процедуру для построения конечного набора релевантных меток. Для повышения производительности буду использовать кэширование на уровне СУБД. Возможно, для ускорения, будет добавлена статичная таблица с набором представлений для каждого случая, которая будет пересчитываться при изменении контента.
спустя 8 часов [обр] German[досье]

Филипп[досье], сначала кажется, что ваш подход более правильный...
Но, например, кеширование для формирования (или перезаписи) статичной таблицы точно не пригодится...

Причем, если загрузка или быстродействие базы данных окажутся критическими параметрами, то у моего подхода могут возникнуть некоторые преимущества перед осуществлением рекурсионного запроса всякий раз при выводе данных... Но Ваш-то подход - другой.

Вы же все-таки решили тем или иным способом создать "статичную" таблицу типа такой
NSSSS
N - столбец с номером статьи
S - номера статей самых близких ссылок
и пересчитывать эту таблицу всякий раз при добавлении новой статьи (идея хорошая, хотя очевидная)

Но там же еще вроде понадобится процедура старения для статей (и желательно сколько-то интелектуальная) -> не будете же вы давать ссылки на статьи, давно устаревшие!

То есть я считаю, что метки - это не просто метки. Метки, здесь — это метод, который вы предоставляете в распоряжение пользователя.

Метки, которые актуальны все одновременно, вроде утрачивают свой смысл. Тогда можно было бы сделать метку из каждой статьи, которая значила бы «статья, похожая на эту»

И если задача такая широкая (меток больше, чем статей или почти столько же)— то оправдан ваш подход. Если же метки должны повторяться, запоминаться, если ограничение на число меток — это важное свойство всего класса меток, как таковых, — то вроде более оправдан мой подход.

Причем актуальные метки можно даже выбирать автоматически, актуальными можно считать последние использованные.

Практически же, если первоначально меток от 8 до 50 и пользователь не хочет больше, хочет только уточнить смысл некоторых меток, а не вводить новые — то ваш подход совершенно неоправдан.
Если же пользователь хочет создавать метки почем зря, а не уточнять их значение , тогда Ваш подход может быть оправдан (хотя классификаторский пыл пользователя тоже может быстро остыть)

Удачи вам!

спустя 8 минут [обр] German[досье]
хотя если сервис публичный, а одной из меток может быть указание на авторство... статей десятки миллионов, меток и пользователей (здесь пользователь — это тоже вид метки) — миллион, то подход Филипп Ткачев[досье] наверно единственно возможный, при обязательном создании «статических» таблиц...
Интересно было бы посмотреть как это будет развиваться
спустя 6 дней [обр] German[досье]

Thirteensmay[досье] писал

MySQL не поддерживает иерархических и аналитических SQL конструкций, этот метод вам не доступен, имейте ввиду на будущее

Наверно правильней создать свою тему, но влаженные SELECT только на заре туманной юности не поддерживались MySQL, поэтому хотелось бы знать что именно автор имеет в виду? какой-то простой пример, если не трудно.

может правильней для этого создать свою тему... но вроде этот вопрос в контексте

спустя 19 часов [обр] Thirteensmay(0/157)[досье]

Проблема подзапросов в том что они вопервых могут сильно снижать производительность, т.к. часто выполняются для каждой строки основного, охватывающего их запроса, а во вторых в том что иногда вообще не решают проблемы, т.к. вложенность может быть велика или вообще не определена. Аналитические и иерархические конструкции позволяют отказаться от подзапросов, упрощая запрос, повышая его производительность, и вообще решая проблему не решаемую подзапросами.

Пример простейшего аналитического запроса вычисляющего прирост продаж текущего месяца относительно среднего значения предыдущего, текущего и следующего месяцев, т.е. "сглаженный" прирост:

таблица mytable:

id |  month  | sale
1       1       10
2       2       30
3       3       50
4       4       20
5       5       10

прирост считаем как sale текущего месяца деленный на среднее значение sale за текущий и окружающие его месяцы
т.е. например для 4 месяца sale = 20, а среднее значение = 50 + 20 + 10 = 80 / 3 = 26.6, значит прирост = 20/26.6 = 0.75

запрос:

select month, sale/avg(sale) over (order by month rows between 1 preceding and 1 following) as delta
from mytable
order by month

результат:

month | delta
1        0.5
2        1
3        1.5
4        0.75
5        0.66

Пример простейшего иерархического (рекурсивного) запроса строящего дерево:

таблица mytable:

id |  name  | parent
0   Все       
1   Объект 1    0   
2   Объект 2    0
3   Объект 3    1
4   Объект 4    1
5   Объект 5    3

запрос:

select level, t.*
from mytable t
start with id = 1
connect by prior id = parent
order by level, id;

результат:

level | id |  name  | parent
1       1   Объект 1    0
2       3   Объект 3    1
2       4   Объект 4    1
3       5   Объект 5    3
спустя 6 часов [обр] German[досье]

Thirteensmay[досье], благодарю Вас, смотрю с интересом. Но вроде это-то все есть, если я правильно понимаю.
Вроде в MySQL есть и левое (правое) объединение с использованием нескольких значений (кортеж)
Ну, транзакции давно уже есть, появляется возможность использования таблиц из внешней базы данных (federated), возможность использования таблиц более 4 гигабайт (merge). Быстро работают таблицы memory, располагающиеся в памяти, временные таблицы скрывают постоянные с таким же имянем, что может быть удобно, если они создны как копии постоянных и в других случаях. Можно использовать внешние (foreign) индексы, можно использовать подзапросы в предложениях FROM (SELECT ...)
Возможно использование и коррелированных запросов, установка пользовательской переменной (@var:=)...

Правда, почти все (или все?) вложенные выборки реализуются в виде объединений, поэтому я использую их редко.
В запросах можно использовать агрегирующие функции (среднее, минимальное, максимальное), и пользовательские функции, условия, относящиеся к выборке (HAVING), повторное использование в одном запросе тех же таблиц и полей, использование результатов функций, как столбца результата выборки.

Много таких приятных маленьких удобств — например, можно даже искать по значению NULL (оператор <=>).

Ну а в хранимых процедурах можно использовать расширенный синтаксис SQL, включающий операторы циклов и ветвления (это нормально, так как в таких случаях обычно желательно использовать проверенный алгоритм)

спустя 10 часов [обр] Thirteensmay(0/157)[досье]
Напишите аналоги представленных мной запросов для MySQL, сравните объем кода, понятность, и самое главное производительность (как MySQL будет вычислять результат), особенно интересна реализация в MySQL второго моего примера.
спустя 13 часов [обр] German[досье]

Уважаемый Thirteensmay[досье]!

Я еще раз вас благодарю.
Я хотел сказать лишь о том, что любые реальные задачи сейчас эффективно решаются средствами MySQL
Я не особенный сторонник слишком понятных выражений SQL, но и в MySQL теперь уже можно использовать много выражений, делающих "фразы" языка более понятными...
И полнотекстовый поиск вполне внятный, и курсоры вот попрубую - они прекрасно справятся с задачами типа первого запроса.

Но ведь я могу в приложении написать такую задачу (причем вполне реальную), которая никакими средствами SQL решаться не будет никогда. Например, анализ рынка по паттернам (шаблонам, включающим 20-500 разных правил относительного положения баров) Или самообучающуюся программу анализа рынка?

Стоит ли напрягать аппарат SQL тем, что нередко эффективней, быстрее можно решить непосредственно в приложении? Ведь база данных — это прежде всего инструмент хранения, а не анализа.

Попробуйте-ка переписать даже ваш простейший запрос так чтобы можно было подставлять колличество усредняемых месяцев
(или лучше считайте эти месяцы днями)

Ну допустим реальная потребность — усреднение от 3 до 90 дней (то есть как и у вас - три месяца максимум). Как будет выглядеть ваш простой запрос для такого действительно простейшего случая?

Но в любом случае, еще раз благодарю. Сведения интересные и полезные.

спустя 54 минуты [обр] Thirteensmay(0/157)[досье]
Ничего переписывать не надо, подставляйте вместо 1 в preceding/following необходимое. Я не предлагаю напрягать аппарат SQL тем, что нередко эффективней, быстрее можно решить непосредственно в приложении, а наоборот, предлагаю использовать те механизмы базы которые эффективнее и быстрее чем решение в приложении. Говорю вам, напишите рекурсивное простроение того же дерева из приложения и посмотрите что получится, ХП будет быстрее, а SQL еще быстрее. Я не предлагаю пытаться решать с помощью SQL все на свете, это невозможно, понятно что решение в приложении гораздо более универсально, но есть такие вещи которые быстрее проще и эффективнее решать в базе, я именно про них, SQL вы же пользуете, не гоняете же в основном массивы туда сюда и циклами их в приложении ведь в основном не пилите, потому что знаете что зачастую использование SQL даст гораздо лучший результат, я обращаю ваше внимание лишь на то что гдето этот SQL победнее, а гдето побогаче, и соответственно дает лучший результат. Я абсолютно с вами согласен в том плане что MySQL сейчас позволяет эффективно решать задачи, но ее старшие братья и сестры позволяют их решать еще эффективнее.
спустя 8 часов [обр] Филипп Ткачев(0/115)[досье]

Кое-что набросал, прошу покритиковать:

// структура данных

// label_id - идентификатор метки
// depth - глубина связи
// lables_list - список меток

lables_list[label_id ] = depth;


//-- прототипы функций

lables_list = get_labels_list() // получить начальный список меток

nested_content = get_nested_content(current_label) // получить связанный контент

nested_labels = get_nested_labels(nested_content) // получить связанные метки

nested_labels = clean_nested_labels(nested_labels, labels_list) // вычесть из nested_labels все метки, глубина которых уже есть

update_labels_list(labels_list, nested_labels,depth_level); // обновить список ссылок


//-- примерный алгоритм работы основной функции

update_labels_list(labels_list, nested_labels,depth_level) {

   // если достигнута глубина, прервать рекурсию
   if (depth_level > 3) break;


// проход по полученному списку меток
   foreach (nested_labels as nested_label) {
   
      // если глубина для метки не установлена, то 
      if (labels_list[nested_label] !=0) 
         
         // установить ее 
         labels_list[nested_label] = depth;
      
      // получить связанный контент для текущей метки
      nested_content = get_nested_content(nested_label)
      // получить список связанных меток
      inner_nested_labels = get_nested_labels(nested_content)
      // вычесть из полученного списка метки с заданной глубиной
      inner_nested_labels = clean_nested_labels(inner_nested_labels, labels_list)
      
      // обновить список ссылок
      update_labels_list(labels_list, inner_nested_labels,++depth_level);
   }

}

пример вызова:

current_label = 5; // текущая метка

depth_level = 1; // глубина прохода

lables_list = get_labels_list();

update_labels_list(labels_list, current_label,depth_level);
спустя 12 минут [обр] Филипп Ткачев(0/115)[досье]

Скорее, основная функция должна выглядеть так (уровень вычисляется неправильно):

update_labels_list(labels_list, nested_labels,depth_level) {

   ++depth_level;

   // если достигнута глубина, прервать рекурсию
   if (depth_level > 3) break;


// проход по полученному списку меток
   foreach (nested_labels as nested_label) {
   
      // если глубина для метки не установлена, то 
      if (labels_list[nested_label] !=0) 
         
         // установить ее 
         labels_list[nested_label] = depth;
      
      // получить связанный контент для текущей метки
      nested_content = get_nested_content(nested_label)
      // получить список связанных меток
      inner_nested_labels = get_nested_labels(nested_content)
      // вычесть из полученного списка метки с заданной глубиной
      inner_nested_labels = clean_nested_labels(inner_nested_labels, labels_list)
      
      // обновить список ссылок
      update_labels_list(labels_list, inner_nested_labels,depth_level);
   }

}

Кстати, а как реализовать вычитание множеств clean_nested_labels()? На это моих знаний не хватает(

спустя 2 часа 41 минуту [обр] Thirteensmay(0/157)[досье]

Чето помоему вы слегка передекомпозировали ;) Возможно ошибаюсь, не видя каких то подводных камней, но на мой взгляд, учитывая что всякие приятности типичные Oracle и т.п., нам не доступны, можно сделать следующим образом:

Заводим временную сеансовую таблицу для итерационного накопления результата, с полями level и label.
Кладем в эту таблицу стартовую метку приписывая ей level = 0.

Далее повторяем следующее, столько раз сколько уровней глубины нам надо:

Выполняем запрос выбирающий из временной таблицы метки последнего вычисленного уровня (с максимальным level).
Для каждой выбранной метки выбираем метки с которыми она связана напрямую, т.е. расположена в одном контенте.
Из полученного множества меток вычитаем с помощью SQL оператора MINUS те что у нас уже лежат во временной таблице,
т.е. те которые уже просчитаны.
Оставшееся множество меток кладем в таблицу с level + 1

Перечисленные выше 4 шага похоже реализуются одним SQL запросом. Надеюсь идея понятна, попробуйте, возможно я чего то не учел, если не понятно то могу попробовать накидать пример, но только под Oracle (дельфинов сейчас не вожу), и уже в понедельник.

спустя 44 минуты [обр] German[досье]

Thirteensmay[досье], в том-то и дело... Вот вы пишите:

но ее старшие братья и сестры позволяют их решать еще эффективнее

Я о чём хочу сказать. Иногда появляется ощущение, что для решения многих задач мускул работает просто лучше платных аналогов
Иногда бывает, что затраты на самый дорогой софт всё равно ничтожны, по сравнению со стоимостью разработки...
И я совсем не уверен в том, что я должен предложить любому богатому клиенту переходить на Оракл. И отказаться от использования MySQL

Филипп Ткачев[досье], я, честно говоря, не вижу поставленной задачи.
Установить взаимосвязь между статьями, на основе наличия одинаковых меток?
Но решается какая-то другая задача...

Кстати, а как реализовать вычитание множеств clean_nested_labels()? На это моих знаний не хватает(

Если вы хотитие убрать из А все элементы, которые есть в B — то вроде не особенно это сложно и прямым перебором сделать.
В битах было бы A ^ (A & B) — проверьте, это на вскидку!
Оператора MINUS вроде в мускуле нет, но механизм его действия — наверняка операции с битами — реализовать нетрудно

В общем, будет время, поясните все-таки чего вы добиваетесь на том простом примере, который я не поленился написать (там про медведей с апельсинами)

спустя 1 час 12 минут [обр] Thirteensmay(0/157)[досье]
Бог мой, минуса нету... это же базовая реляционная концепция, заложенная в стандартах SQL... ну тогда джойнами придется, пример есть на mysql.com (см. по ключевому слову MINUS), или еще какими другими костылями. Вот оно че German[досье], вот про это я и говорю, а с тем что если задача нормально решается MySQL то переходить на Oracle не стоит я не спорю, но вот видите как она решается, того нету, сего нету, там перебор, тут костыль... Oracle кстати бесплатная версия есть, с ограничениями конечно (4 гига базы и один проц), но такого ограничения в большинстве случаев хватает.
спустя 1 час 49 минут [обр] German[досье]
Это я просто поспешил, минус фактически есть. Да и все так — никакие не костыли, это просто немного другая запись
SELECT a FROM A WHERE a NOT IN (SELECT b FROM B)
спустя 7 часов [обр] Thirteensmay(0/157)[досье]
Эта запись позволяет не лучшим образом решить текущую задачу, но это никак не минус, кол-во полей, и самое главное, я уже говорил, сколько раз будет выполняться запрос внутри not in ?
спустя 10 часов [обр] Филипп Ткачев(0/115)[досье]

German[досье], насчет задачи я уже не знаю как объяснять.
Представьте себе граф, узлами которого являются метки и контент (разный, безразлично какой). Какие-то дуги есть, каких-то нет. Длина каждой дуги 1/2 уровня связи. С.м. иллюстрацию ниже.

Мне нужно найти кратчайшее расстояние от метки А до всех остальных меток.
Текущая метка номер 5 (m5).

В конечном случае мой результирующий набор будет выглядеть так:

label depth
m1    1
m2    3
m3    2
m4    1
m5    0
m6    3
m7    null

Насчет битовых операций идея ясна. Только рассматриваются записи, а не биты.

Насчет конструкции IN в MySQL. Она предназначена для операции с множествами (SET), а насколько я помню, там есть ограничение на количество элементов множества - 64. Пока их будет меньше, будет работать, как только количество превзойдет этот порог, правильно работать не будет.

спустя 7 часов [обр] German[досье]
Насчет конструкции IN в MySQL

Уважаемый Филипп Ткачев[досье]! Мне казалось, что вы должны были проверить свое утверждение.
IN прекрасно работает для таблиц без каких-либо ограничений, причем для нескольких полей - тоже работает. И мне представляется, что это никак не отличается от оператора minus (в последнем могу ошибаться). Оптимизатор MySQL действует здесь вполне адекватно, не повторяя ненужного запроса многократно. Хотя у Оракла есть, масса преимуществ, которые, правда, редко удается применить на деле и без которых практически всегда можно обойтись.

Можно также сделать все в перл: уберите из списка @a любой элемент, который найдется в списке @b
Тоже очень просто, причем может оказаться еще и быстрее чем в базе данных.

спустя 2 часа 2 минуты [обр] Thirteensmay(0/157)[досье]
Если "Оптимизатор MySQL действует" то в данном случае без претензий.
спустя 2 часа 16 минут [обр] German[досье]

Уважаемый Thirteensmay[досье] !
Да, наверно, я не вполне правильно выразился относительно оптимизатора, нужно был сказать о самой СУБД.
Дело в том, что различаются коррелированные и некоррелированные подзапросы. Коррелированный подзапрос содержит ссылки на значения из внешнего запроса, и потому не может быть выполнен самотоятельно. А предложенная мной форма — это некоррелированный подзапрос, она не будет выполнятся повторно.

Вместо формы написания запроса =# NOT IN #= можно писать =# <> ALL #= будет работать точно также. Кроме того здесь даже можно использовать левое (правое) объединение, чтобы убрать из результата все данные

SELECT a FROM A LEFT JOIN B ON a=b WHERE b IS NULL (только столбец b должен быть NOT NULL)

Уважаемый Филипп[досье] ! Может вам больше по вкусу такая "левая" форма? Но разницы в работе, я полагаю, не будет.

спустя 10 часов [обр] Филипп Ткачев(0/115)[досье]

Про конструкцию IN, в старых версиях MySQL действительно существовало ограничение. Сейчас же

The number of values in the IN list is only limited by the max_allowed_packet value.

И с IN у меня связаны некоторые печальные моменты. Он все-таки плохо работает. Недавно пользовался вариацией с вложенными запросами и напарывался на проблемы с большим числом записей. Конечно, я понимаю, что версия MySQL довольно старая у хостера (4.1.22), но ничего с этим не поделаешь.

Про "левую" форму мне больше нравится решение, я его вчера нагуглил.

Про Perl: я пишу модуль на PHP.

спустя 6 часов [обр] German[досье]
Филипп[досье]! Левое объединение давно и исправно работает с 3-ей версии (или раньше), правда, на человеческий язык некоторые такие запросы перевести почти невозможно, ну, если только переводить WHERE b IS NULL, «как которых нет в таблице (наборе, выборке)»
Thirteensmay[досье] может вдоволь поиздеваться над таким выражением... Это меня и заставляло воздерживаться от того, чтобы привести этовыражение с самого начала.
Но я, честно говоря, что-то не верю, что такие левые запросы реализуются движком MySQL хоть сколько-нибудь по другому, чем NOT IN или <>ALL
спустя 20 минут [обр] German[досье]

Я всегда правлю маленькие ошибки после отправки сообщения. Плохо, что на этом форуме нет такой возможности.

Версия 5.1 MySQL имеет много преимуществ, там значительно усилен аппарат процедур, фукнций, триггеров... Дружище Дюбуа многое описывает в выпуске своей книжки за 2007 год на русском, так что мне почти не приходится пользоваться он-лайн документацией. Правда, у него там искать нужные сведения неудобно.
Есть и странности в переводе. Например VIEW переводится как курсоры, хотя имеется и CURSOR, как таковой. Я бы перевел VIEW, хоть как отображение — довольно точно соотвествует сути на русском языке.
Но вне сомнения надпись на книге "Полное и исчерпывающее руководство" — справедлива и в русском переводе.

А что мешает сменить провайдера, если этот провайдер совсем «мух не ловит»? Задача у вас — довольно сложная, и интересная. Наверно правильно, что Вы ее не описываете подробно. Вроде вы делаете нечто наподобие микроинтеллекта, ассоциативного мышления, но в очень ограниченном, конечно, формате. Во всяком случае я давно думал о чем-то таком. Это и не должно реализоваться слишком просто

спустя 15 дней [обр] German[досье]
NOT IN
 
должно применяться для выборки несовпадений по всем или многим полям, LEFT JOIN может заменить его только для одного поля...
Кроме того NOT IN выглядит понятней. В 5 версии работает без проблем
Powered by POEM™ Engine Copyright © 2002-2005