Как опеспечить уникальность записи в VARCHAR(255)?

← →
Shama_n © (2004-06-29 18:23) [0]

База данных InterBase примерно на 15000 записей и в поле типа VARCHAR(255) нужно недопустить дублирования одинаковых записей. Данные в БД добавляются очень часто и выполнение проверки уникальности каждого значения методами поиска. Подскажите максимально быстрый метод обеспечения уникальности значения?

← →
Соловьев © (2004-06-29 18:26) [1]

> проверки уникальности каждого значения методами поиска

для такого поля самое оно...

← →
Shama_n © (2004-06-29 18:38) [2]

Сомневаюсь что самое оно...
Допустим сейчас в моей программе реализован не прямой поиск по VARCHAR а существует индексное поле integer в которое заносится сумма кодов всех бувк в VARCHAR и перед поиском строки сначала суммируются все коды букв и затем производится поиск по индексному полю integer что гораздо быстрей. Но когда БД увеличивается до 3000-4000 тыс записей и этот метот оказывается бесполезным. У меня есть еще мысли как все можно оптимизировать но возможно я изобретаю велосипед дважды и хочется услышать мнение мастеров :)

← →
Vlad © (2004-06-29 18:55) [3]

> Shama_n © (29.06.04 18:38) [2]

> существует индексное поле integer в которое заносится сумма
> кодов всех бувк в VARCHAR и перед поиском строки сначала
> суммируются все коды букв и затем производится поиск по
> индексному полю integer

Это что, шутка ? Сумма кодов всех символов это не даст уникального значения.
"AB" и "BA" даст одно и тоже число, и что ты дальше будешь делать ?

Я так понимаю, поле в русской кодировке и уникальный индекс ты по нему создать не можешь из-за его длины (255) ?

← →
Shama_n © (2004-06-29 19:05) [4]

>Vlad
>Это что, шутка ? Сумма кодов всех символов это не даст уникального значения.
>"AB" и "BA" даст одно и тоже число, и что ты дальше будешь делать ?
Конечно не даст :) После нахождения записи по индексному полю нужно сделать проверку по VARCHAR что нашли именно нужную запись и если запись не та что искали то ищем следующую запись и так или пока не найдем то что искали или пока таблица не закончится. В итоге такой алгоритм всеравно гораздо быстрей чем обычный поиск

← →
Vlad © (2004-06-29 19:15) [5]

> Shama_n © (29.06.04 19:05) [4]

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

И вобще, в сети есть много материала по хэш таблицам, почитай, скорее всего это будет оптимальный способ в твоей ситуации.

← →
TohaNik © (2004-06-29 19:20) [6]

Оч. скромное ИМХО.

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

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

← →
Vlad © (2004-06-29 19:26) [7]

> TohaNik © (29.06.04 19:20) [6]

Как у кого ? У меня на Оракле индекс уникальный ставится в таком случае :-)))

← →
Vlad © (2004-06-29 19:32) [8]

> TohaNik © (29.06.04 19:20) [6]

Если ты имеешь ввиду чтобы пользователь не ввел к примеру так:
"Иванов И И" и "Иванов И.И." ?
ИМХО, подобные "дубли" ты никак не отследишь.
Такие значения нужно позволять вводить, просто потом делать ручную выверку базы, это стандартная схема.

← →
Shama_n © (2004-06-29 19:35) [9]

Создание уникального индекса в моем случае ничего не решает. Обращение к БД происходит так часто что что поиск в даже по индексному полю в БД с числом записей свыше 4000 сильно тормозит сервер. У меня есть мысли как обеспечить мгновенный поиск в базе данных любого размера просто не хотел изобретать велосипед дважды, но кажется придется. Напишу как это сделать когда приеду домой. Часа через 2 . Может кто за это время меня опередит? ;)

← →
Vlad © (2004-06-29 19:53) [10]

> Shama_n © (29.06.04 19:35) [9]

> Создание уникального индекса в моем случае ничего не решает

Как это не решает ? По крайней мере уникальный индекс автоматически обеспечивает уникальность поля. Разве не это требовалось ?
Другое дело, что IB вроде-бы не позволяет создавать индексы по varchar полям длиннее 80 с чем-то символов, если они в русской кодировке.

← →
TohaNik © (2004-06-29 19:53) [11]

Vlad © (29.06.04 19:32) [8]
>Такие значения нужно позволять вводить, просто потом делать ручную выверку базы, это стандартная схема.

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

P.S. Видел старую клипперовкую программу по учету мат. ценностей
так вот кроме этой стандартной для клиппера ф-и при вводе "Оце" - возвращалось "ацетон" ну смысл понятен.
Вероятно использовался некий алгоритм перестановок в хэш таблицах с доп условиями. ??? Вообще интересует наиболее удобная и понятная для пользователя схема.

← →
Vlad © (2004-06-29 19:58) [12]

> TohaNik © (29.06.04 19:53) [11]

ИМХО, наиболее понятная (и полезная для системы) схема - это жесткие маски ввода.
Если у тебя поле содержит ФИО то пользователь должен вводить его в три разных Edit"а. Причем каждый из них должен пропускать только определенный набор символов, и т.п.
А если просто пытаться разбирать строчку на части, то это надо сложную чуть ли не интелликтуальную систему писать :-)

← →
TohaNik © (2004-06-29 20:25) [13]

> А если просто пытаться разбирать строчку на части, то это
> надо сложную чуть ли не интелликтуальную систему писать
>

Ну почему - разбить фразу на слова при наличии пробелов ест-но не сложно.
Можно в цикле потом и каждый символ видеть как любой-делая select- и вываливать это в какой-нибудь List исключая одинаковые id Но ИМХО это криво и без логики и медленно наверно(не пробовал). А интеллектуальная система- ну смотря до какого уровня соответствий и требований....
Хотелось-бы ссылки увидеть;)

← →
TohaNik © (2004-06-29 20:26) [14]

← →
Vlad © (2004-06-29 20:36) [15]

> Хотелось-бы ссылки увидеть;)

На сколько я знаю, для этого используются нейронные сети
Хороших ссылок на эту тему к сож. не знаю, но вот первое что в Яндексе попалось
http://ermak.cs.nstu.ru/~avg/ARTICLES/Ngtu-99.htm

← →
Sergey Masloff (2004-06-29 20:39) [16]

Считай хэш для строки. Какой-нибудь MD5 я думаю обеспечит вполне достаточную уникальность.

← →
Vlad © (2004-06-29 20:51) [17]

> Sergey Masloff (29.06.04 20:39) [16]

Я боюсь что не будет особой разницы, хранить хеш MD5 (16 байт в числовом или 32 в HEX формате) или же саму строчку VARCHAR.
Во всяком случае при таком небольшом количестве записей как у автора, разницу в скорости врядли почувствуешь

← →
TohaNik © (2004-06-29 20:54) [18]

Vlad © (29.06.04 20:36) [15]
Завтра посмотрю.
Sergey Masloff (29.06.04 20:39) [16]
И про MD5 поищу, ато не осведомлен%)

← →
Mim1 © (2004-06-29 21:14) [19]

> Shama_n © (29.06.04 18:23)

Скажите а что хранится в этом поле? Нельзя ли эти 255 разделить на части?

← →
Vlad © (2004-06-29 21:15) [20]

> Mim1 © (29.06.04 21:14) [19]

И как дальше эти части индексировать ?

← →
Sergey Masloff (2004-06-29 21:37) [21]

Vlad © (29.06.04 21:15) [20]
Кстати я как всегда наискосок прочитал первое сообщение и все. Про хэш ты почти сразу написал - я просто не видел ;-)

← →
Fay © (2004-06-29 21:39) [22]

Очень неплохо помогает выбор другой СУБД. 8)

← →
Vlad © (2004-06-29 21:46) [23]

> Fay © (29.06.04 21:39) [22]

ага, Оракл например :-)

← →
Fay © (2004-06-29 21:47) [24]

Да хоть бы и Oracle.

← →
Vlad © (2004-06-29 21:49) [25]

> Fay © (29.06.04 21:47) [24]

> Да хоть бы

:-)))

← →
Shama_n © (2004-06-29 21:49) [26]

Mim1>В поле хранится наименование товара. В основном больше 70 символов

Создание одного только уникального, точней полууникального :), индекса не решает проблемму так как в базу из 15000 записей необходимо загнать только недублирующиеся в БД значения примерно из 7000 записей. Тоесть для всего списка из 7000 нужно сделать сверку с базой данных. Если перемножить то получим немаленькое кол-во необходимых операций :( Единственное до чего додумался это создать 2 таблицы В одной будут находится отсортированые по индексу записи и поиск в ней будет производится бинарным методом. Во вторую таблицу будут попадать только новые и еще неотсортированые записи в ней придется искать стандартным способом. Когда размер второй таблицы превысит скажем 200 записей, все записи нужно будет перенести в первую таблицу и произвести там повторную сортировку

← →
Johnmen © (2004-06-29 23:13) [27]

>Shama_n © (29.06.04 21:49) [26]

>Если перемножить то получим немаленькое кол-во необходимых операций

Какая разница, сколько операций. Главное - время. Какое тебя удовлетворит ?

>В одной будут находится отсортированые ...

Сортировка к хранению никакого отношения не имеет...:)

>поиск в ней будет производится бинарным методом

А при поиске по индексированному полю думаешь используются более слабые алгоритмы ? :)

>>> опять при сортировку.......

Она здесь ну абсолютно непричём. См.выше.

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

← →
Алхимик © (2004-06-30 01:05) [28]

Сдаётся мне что про нормализацию Вы не слышали.
Ключ на основе наименования товара (естественный ключ ЕК) - не самое лучшее решение.
Рекомендую -
Анатолий Тенцер
"Естественные ключи против искусственных ключей"
http://www.akzhan.midi.ru/devcorner/articles/NaturalKeysVersusAtrificialKeysByTentser.html

>Какая разница, сколько операций. Главное - время. Какое тебя удовлетворит?
Сейчас уходит по 3-4 часа времени и скорость падает прогрессирующе относительно размера базы. Думаю когда база вырастет в 3-4 раза сверка будет занимать дней 5 :(

>Сортировка к хранению никакого отношения не имеет...:)
К хранению согласен а к поиску в наборе данных тоже не имеет?

>>поиск в ней будет производится бинарным методом
>А при поиске по индексированному полю думаешь используются более слабые алгоритмы ? :)
Думаю бинарный и используется но работает он только с отсортированым набором данных. InterBase производит сортировку после каждой новой записи? Если так и есть то возможно только в этом причина прогрессирующего падения скорости. Мой способ с 2 таблицами реализовывает сортировку после каждых 200 записей.

Я новичек в БД и поправьте меня пожалуйста если я где-то ошибаюсь

[29] Shama_n © (30.06.04 10:57)
> Я новичек в БД и поправьте меня пожалуйста если я где-то
> ошибаюсь

В РСУБД, как правило, записи пишутся как попало, никак не сортированые физически.
Почитай книжки про РСУБД, про индексы в частности, они тебя спасут, о чем тебе неоднократно уже говорили.

> Shama_n © (30.06.04 10:57) [29]

> Думаю бинарный и используется но работает он только с отсортированым
> набором данных

Неверное предположение. Бинарный метод работает с любым, хоть отсортированным хоть неотсортированным набором данных. Главное чтобы индекс был по тому полю, которому отбираешь записи.

> InterBase производит сортировку после каждой новой записи?
>

Ну не причем тут сортировка. После вставки каждой новой записи (равно как и при удалении и изменении) он просто изменяет соотв. информацию в индексе.

Цитата: Большинство существующих систем главным образом основаны на B-tree индексных структурах. Эти индексные структуры могут оптимально использоваться только при работе со статической информацией и время от времени требуют оптимизации

Какие операции понимаеются под оптимизацией? Как ее можно реализовать?

> Shama_n © (30.06.04 13:47) [32]

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

> Сейчас уходит по 3-4 часа времени

Судя по этому, у тебя либо неверно построен SQL запрос, либо
нет необходимых индексов для его оптимального исполнения.

>в базу из 15000 записей необходимо загнать только
>недублирующиеся в БД значения примерно из 7000 записей

>Сейчас уходит по 3-4 часа времени

Т.е. в лучшем случае выходит ~1.5 сек на запись...:)
У тебя IBM XT с проц.8088 ? Или у тебя/у меня тяжелый бред ?

[34] Johnmen © (30.06.04 14:05)
Дык, а если у него индекса нет и он в среднем пробегает 7 000 х 15 000 / 2 = 52.5 мильенов записей, чтобы определицца, уникальная она или нет. :))

> Johnmen © (30.06.04 14:05) [34]

> У тебя IBM XT с проц.8088 ? Или у тебя/у меня тяжелый бред
> ?

Так у него же еще какой-то алгоритм отбора дублей работает :-)

>Danilka © (30.06.04 14:15) [35]
>Vlad © (30.06.04 14:15) [36]

Это понятно. Но для одной записи он в среднем пробегает 1 х 15 000 / 2. Потом, возможно, вставляет. И это занимает 1.5 сек ???
"Не верю !" (с)

> Danilka © (30.06.04 14:29) [38]

> Смотря где пробегает, может на клиенте..
> while not table1.eof ...

и еще вдобавок машина IBM XT с проц.8088 :-)

Как опеспечить уникальность записи в VARCHAR(255)? Найти похожие ветки