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


V>>Я лишь ответил, что если считать выделение индекса

DG>зачем вообще нужны индексы? в чем их point?

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

Почему именно декомпозиция с вводом доп. аттрибута? Ну просто же (рассуждения для случая уникального индекса): по определению такого индекса должно существовать однозначное соответствие м/у кортежом индекса и кортежом исходного отношения, правильно? Т.е. в кортеже индекса должен храниться некий внешний ключ (термин из теории реляционных БД) однозначно определяющий кортеж остатка декомпозиции исходного отношения. Спор, похоже, подогревается тем, что коль физический характер такого суррогатного ключа нам недоступен, мы не можем использовать его в рассуждениях. Дудки, еще как можем, ведь наличие такого соответствия аксиоматично из определения самого понятия "индекс", но просто дается на откуп конкретной схеме реализации индекса.

Итого, как это есть на самом деле: берем отношение ABCD, в нем есть некий ключ (необязательно первичный) AB, т.е. была задана свыше зависимость AB->CD, выносим этот индекс через суррогатный ключ X# (тот самый, ндоступный для непосредственнго оперирования в большинстве СУБД, а в некоторых СУБД таки доступный!), получаем декомпозицию зависимостей: AB->X#, X#->CD. В реальности, как говорил, исходные данные индекса могут храниться избыточно вместе с остальными данными, т.е. иметь место такая декомпозици схемы: {ABX#, X#ABCD}. Более того, для случая X#ABCD сам X# физически не обязан храниться в кортеже (физический уровень в IT — это уровень размещения данных по адресам/байтам/смещениям), хотя обязан являться являться неким его св-вом (т.е. атрибутом), например, порядковым номером или еще каким-нибудь значением в какой-нибудь разновидности адресации. И мы таки обязаны этим атрибутом оперировать в рассуждениях, если хотим выразить операции над индексами в терминах РА.

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

G>>Еще раз читай то что я процитировал. Первый пункт.

DG>значит ты в слово meaningful включаешь в том числе, чтобы код был понятен и с точки зрения его производительности.
DG>о чем тогда дискуссия?

Там написано "set goals". Надо задать цели, причем они должны быть измеримы. Это значит что можно получить ответ достигуты они или нет.
Например "выдерживать нагрузку 100500 одновременных активных пользователей на таком-то железе", вполне можно запустить профайлер с таким сценарием.
В вот "выдерживать как можно большее количество пользователей на любом железе" — уже не получится.

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

DG>>зачем вообще нужны индексы? в чем их point?

V>Ну, автор теории реляционных БД вводит индексы исключительно как ср-во повышения эффективности доступа к данным.

отсюда и получается, что пока речь идет лишь о корректности преобразованиий РА, то никаких индексов еще нет.

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

V>Это ты откуда берешь? В терминах РА мы всегда выполняем некую последовательность операций, где последующие операции используют результаты предыдущих.
В РА нет изменяемого состояния, поэтому она не более императивна, чем ФП.

V>Но, доказано, что РА и реляционное исчисление взаимно эквивалентны, т.е. декларативные формулы реляционного исчисления всегда могут быть выражены через императив реляционной алгебры. Вспомним ниже, когда дойдем до SQL.

V>Насчет эффективности — я даже не знаю, как можно было не понять, о чем речь. Что не так с сохранением частоиспользуемых операций? И повторюсь: для операций РА эффективность является вычислимой. Т.е. берем конкретную операцию из РА, берем некую структуру данных... так вот, для этой пары {операция РА, структура данных} обязательно есть оценка стоимости в терминах K*O(n). И опять же повторюсь, именно так работает оптимизатор, он же не на кофейной гуще гадает...
Всё правильно, только оптимизатор работает не с РА, а со значительно более низким уровнем. Попробую объяснить на более простом примере: возьмем, скажем, комплексные числа. С точки зрения математики комплексных чисел, операция умножения a * b не имеет никакой "стоимости". А вот если мы перейдём к некоторому представлению комплексных чисел в компьютере, то операция a * b будет иметь некоторую реализацию в этом представлении. И вот уже у этой реализации будет некоторая стоимость, выраженная в терминах более низкоуровневых операций. Именно это даёт возможности реализации, скажем, операции "быстрого" умножения комплексных чисел, которая экономит одно умножение за счёт сложения. Быстрота этого умножения имеет смысл в том случае, если относительная стоимость скалярного умножения по сравнению со сложением велика.

V>Садись, два.
V>Выделенное неверно. Далее все рассуждения, основанные на этом — тоже.
ОМГ, какой апломб. Я поскипаю нерелевантные рассуждения, ок? Вопрос не в том, чтобы "однозначно определить". Вопрос в том, чтобы имея bookmark, получить по нему значение записи за O(1).
Вы вот проигнорировали мой пример, а напрасно. Вот у вас есть отношение (id, name, age). Предположим, мы знаем, что name — уникально. Вы хотите найти по name значение age. Стоимость этой "операции" — O(N), где N — количество кортежей в отношении. Это дорого. Что вы сделаете для ускорения? Какая операция проекции даст вам хоть какую-то пользу?
Правильный ответ — никакая. Потому что вы никак не измените N. Единственный способ бороться с O(N) — это построить индекс, т.е. упорядоченное отношение (name, RID), где RID — это внутренний идентификатор записи, учитывающий особенности размещения, и позволяющий делать lookup за O(1).

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

V>Плевать, есть разные индексы. В хеш-таблице у меня будет близко к O(n), но это всё не принципиально в нашем обсуждении.
Если у вас в хеш-таблице близко к O(N), значит вы плохо реализовали хеш-таблицу.

V>Имел ввиду операцию сравнения на больше/меньше, конечно, которая обязательная для выполнения индексов в виде деревьев для упомянутого случая MS SQL. Ес-но, операция на равенство в домене должна быть, иначе смысл в индексе на таком домене пропадает, это и так понятно.
Хорошо.

V>Таки настаиваю, потому как встречал разные БД в свое время, в том числе такие, где индексы выделялись как некластерные исключительно для улучшения K при O(n), ввиду банально меньших данных, требуемых для сканирования. А в MS SQL строки таблиц с кластерным индексом имеют фиксированную длину, именно для этого блобы, выше определенной длины, не хранятся в самих таблицах. Их можно разместить где угодно, хоть на других жестких дисках. Поэтому... поэтому просто прочти еще раз, что я там написал. Кстати, неплохая вышла иллюстрация побочного эффекта, возникающего при использовании пропагандируемого подхода, что "необязательно понимать устройство того, с чем работаешь". Не объяснишь, как же ты в своих проектах принимаешь решение, делать некие индексы кластерными или нет? Мне уже очень любопытно услышать этот алгоритм рассуждений.
В MS SQL строки таблиц вообще всегда имеют ограничение по длине. Это никак не связано с наличием или отсутствием кластерных индексов. Это связано со страничной организацией хранилища (Возможно, в новых версиях это изменили, но во времена, когда я с ним работал, размер кортежа был ограничен 8000 байт).
Поэтому алгоритм выбора кластерности индекса связан в первую очередь с эффективностью операций по этому индексу. Есть несколько соображений:
1. Для кластерных индексов не нужно делать bookmark lookup. Поэтому имеет смысл делать кластерный индекс по тому ключу, по которому чаще всего происходит поиск разнообразной информации.
2. В случае наличия кластерного индекса, остальные индексы вместо RID используют ключ кластерного индекса. Поэтому не стоит делать кластерный индекс по длинному ключу, если других индексов много.
3. Поскольку кластерный индекс определяет физический порядок расположения записей, то не стоит делать его по монотонному ключу, если в таблицу будет идти интенсивная вставка из многих потоков — это уменьшит коэффциент параллельности.
В общем, всё. Как видим, блобы тут вовсе не участвуют.

V>Тем не менее, классический SQL оперирует понятиями реляционного исчисления + непосредственно поддерживает некоторые операции РА, а кое-какие диалекты поддерживают еще больше операций РА, чем даже классический SQL-92.
Классический SQL не оперирует понятиями реляционного исчисления.

V>Взаимосвязь SQL с реляционным исчислением и алгеброй там же: http://www.mstu.edu.ru/study/materials/zelenkov/ch_4_6_1.html
Вы сами-то это читали?

В то же время SQL подвергается суровой критике как раз за недостаточное соответствие реляционным принципам

V>Еще из первой страницы гугла про реляционное исчисление: http://www.ref.by/refs/67/28689/1.html
V>Эта ссылка напомнила мне краткий конспект того, как именно оно преподавалось нам когда-то.


V>>>Я не знаю, что есть логическое, а что есть физическое в твоем понимании?
S>>Это я вижу. Поясняю: При рассмотрении анатомии оптимизаторов запросов в СУБД, выделяют два вида "планов запроса":
S>>1. Логический план. Выражается в терминах операций расширенной РА; является результатом синтаксического разбора SQL запроса и некоторой предварительной оптимизации. Предварительные оптимизации на этом этапе имеют целью упрощение плана для дальнейшего анализа и устранение заведомых неоптимальностей.
S>>2. Физический план. Выражается в терминах императивных операций, работающих над конкретными объектами реляционной базы. Это совсем другие операции. Скажем, там, где в логическом плане была пара операций π и σ, в физическом плане будет одна операция table scan. Или одна операция index seek. Или операция index scan и операция bookmark lookup.

V>Улыбнуло.
Рад за ваше чувство юмора.

V>Index scan — это по прежнему операция ограничения из РА, а bookmark lookup — один из видов того самого соединения.
Нет.
V>Похоже, разный уровень подробностей происходящего застилает от тебя суть вещей... ИМХО, это от того, что ты представляешь себе индексы не как декомпозицию исходного отношения, а нечто "монолитное" (С), присущее данным.
Индексы не являются "декомпозицией" исходного отношения. Чтобы начать разговаривать об индексах, нам придётся перейти от абстрактного термина "отношение" к конкретному термину "таблица", и начать учитывать подробности хранения данных. Вы почитайте учебник по устройству СУБД — того же Гарсиа-Молина. Оптимизатор "видит" совсем другую модель, чем вы в ваших задачках по РИ.

Просто большинство "учебников" остаются на уровне плохого пересказа РА и РИ, с внезапным перепрыгиванием в сторону SQL (избегая обсуждения природы различий между SQL и абстрактной реляционной моделью), и, собственно, всё. Следующие учебники уже берут с места в карьер изложение подробностей конкретной СУБД, опять же избегая обсуждать связь этих подробностей с реляционной моделью.

V>>>Использование разного порядка сканирования индексов — это физическое отличие или логическое?
S>>Конечно же это отличие физического плана. В логическом плане никаких индексов нет.
V>Сорри, но выделеное профанирует вообще весь спор об абстракциях.
К сожалению нет. Вы, похоже, как-то неправильно представляете себе устройство оптимизаторов запросов и связанные с этим теории. Поймите, что если мы попробуем засунуть индексы внутрь логического плана, то сразу же потеряем возможности по оптимизации. Ведь физический план обязан соответствовать логическому.

V>Давай тогда уже так: что есть абстракция на твой взгляд? Может, мы спорим "каждый о своем"?
Очень на то похоже. Я не очень понимаю ваш вопрос. Своё видение того, как всё устроено, я изложил. На всякий случай приведу его ещё раз:
1. Есть Реляционная Модель. Грубо говоря, построена на теории множеств, вводит некоторое математическое пространство.
1.а Есть неразрывно связанные с РМ Реляционная Алгебра (механизм по конструированию из одних отношений других) и РИ (механизм по описанию уравнений над реляционной моделью)
Это пока что всё один и тот же уровень абстракции. На нём мы получаем полезные вещи типа Теоремы Кодда, а также несколько соотношений эквивалентности между операциями РА
2. Есть модель SQL. В зависимости от версии стандарта, обладает разными особеннностями. Она отдалённо напоминает Реляционную Модель, но существенно отличается от неё в важных нюансах. В частности, введены понятия NULL и трёхзначной логики, а также явным образом разрешены дубликаты в таблицах (в отличие от отношений). Эти отклонения внедрены как компромисс между простотой РМ и требованиями удобства в реальных задачах. Важный нюанс: напрямую модель SQL нигде не ссылается на реляционную модель; все взаимосвязи — исключительно идеологические, на уровне "о, отдалённо похожую штуку мы видели и там". Реально сходство примерно такое же, как между преобразованием Фурье и поворотом векотор в трёхмерном пространстве.

2.а. Помимо черт реляционной модели, в SQL есть также черты теории транзакций. Как и в случае РМ, модель SQL привносит в чистую транзакционную теорию некоторые важные модификации, в частности вводит понятие уровней изоляции. Это понятие очень часто неверно интерпретируется разработчиками из-за отстутствия вменяемой литературы, покрывающей зазор между теорией и практикой.
2.б. Существенная роль в модели SQL отводится элементам, которых в математических моделях вовсе не было. Это всяческие view, триггеры, индексы, хранимые процедуры и прочая кунсткамера.

3. Есть модели реализации конкретных СУБД.
3.а. В них добавляются расширения модели стандартного SQL
3.б. А также придаётся конкретный смысл абстрактным понятиям модели SQL.
Именно на этом уровне работают оптимизаторы запросов. Большинство промышленных СУБД позволяют разработчику самому выбирать, на каком уровне абстракции работать — 2, 3а, или 3b. То есть я могу просто написать select age from person where name = 'vdimas', оставаясь в рамках SQL-92. Могу воспользоваться расширениями конкретной СУБД, создав, скажем, table-valued функцию для того же запроса. А могу опуститься на уровень реализации, хинтами вынудив оптимизатор использовать специфический индекс.

V>Натурально обидно после стольких постов увидеть, что "в логическом плане никаких индексов нет", это же сколько потраченного времени...
Срыв покровов произошёл? Ничего, со временем в голове всё устаканится.

V>Угу, смотрю в книгу, вижу известно что. Короче, преобразования данных, выполняемых в терминах РА — это ВСЕГДА императивный алгоритм, построенный на примитивах-операциях РА. Важна последовательность операций, а сами аргументы операций — это результаты (в общем случае) предыдущих операций.
Вы попробуйте хотя бы читать те ссылки, которые сами приводите.

В частности, ни один из подходов нельзя назвать « более непроцедурным « по сравнению с другим.

Это чтобы вы не думали, что РА как-то фундаментально менее декларативна, чем РИ.

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

DG>зы
DG>в моем понимании, хороший программист должен уметь строить модель узких мест своих программы прямо по коду, используя профайлер лишь для проверки и корректировки своего понимания

В моём понимании, главная характеристика хорошего программиста — понимание собственной органиченности. Пока программист использует свою интуицию и умение строить модель узких мест программы в уме лишь как подсказки для возможных направлений поиска узких мест инструментальными методами, всё хорошо. Но когда он начинает думать, что он и без профайлера молодец — это тупик. Рано или поздно такой программист начнёт заниматься ерундой.
Вот мы разобрали примитивную, крошечную программу, которая работает в идеальных условиях — один поток, один запрос, нет конкурирующих за ресурсы приложений. И то уже наблюдаются значительные сложности в предсказаниях узких мест.
В реальных программах всё гораздо хуже и запутаннее. Без измерений можно потратить месяц на вылизывание кусочка кода, который почти не повлияет на общую производительность.

S>И снова я против того что бы рассматривать переменную как объект.

есть глубокое непонимание, что такое модель.

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

ни ты, ни sinclair, ни gandjustas так до сих пор и не описали, какие допущения для ООП делаются, какие из этого следствия вытекают, и как это всё доказывается. хотя я неоднократно это просил.

допустим, что для ООП достаточно следующих допущений:
1. можно выделить объекты
2. для объектов есть функция идентичности, определяющую что такое один и тот же объект
3. взаимодействие представлено в виде обмена сообщений
следствие:
если вышеуказанные допущения выполняются, то применим ООП-аппарат.

из всего это следует, что как только для переменной все эти допущения выполняются, то она автоматически становится объектом в терминах ООП
Опишем эти допущения для переменной:
1. каждую переменную будем рассматривать как отдельный объект
2. в качестве функции идентичности возьмем имя переменной
3. взаимодействие с переменной представимо в виде двух сообщений getvalue/setvalue
вывод:
при данных условиях, переменная есть объект в терминах ООП, и для нее применим весь аппарат ООП.

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

V>>Ну, автор теории реляционных БД вводит индексы исключительно как ср-во повышения эффективности доступа к данным.

DG>отсюда и получается, что пока речь идет лишь о корректности преобразованиий РА, то никаких индексов еще нет.

А почему операции РА не могут быть применены к самим индексам? Я никак не воткну в этот "запрет". Не обоснуешь?

Индексы — это реально существующие объекты БД, созданные не самой базой, но исключительно разработчиками. Зачем делать вид, будто их нет?

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

V>Исследования для одного из случаев...
О да. "Обещали показать выступление камерного оркестра, а ограничились жалким частным случаем для K равного трём"...

V>А почему операции РА не могут быть применены к самим индексам? Я никак не воткну в этот "запрет". Не обоснуешь?

сейчас речь не о том: могут или не могут.
а речь о том: нужны или не нужны индексы в рамках реляционной модели и алгебры?
и ответ — не нужны, пока речь идет лишь о корректности реляционной алгебры.

V>Индексы — это реально существующие объекты БД, созданные не самой базой, но исключительно разработчиками. Зачем делать вид, будто их нет?

потому что можно обойтись и без них

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

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

V>>Это ты откуда берешь? В терминах РА мы всегда выполняем некую последовательность операций, где последующие операции используют результаты предыдущих.
S>В РА нет изменяемого состояния, поэтому она не более императивна, чем ФП.

Опять продемагогил... спасибо... ФП не означает отсутствие императивности, оно означает наличие ф-ий как первоклассных объектов языка, только и всего. И с чего бы императивному алгоритму оперировать обязательно иммутабельным состоянием? Чай не ООП...


V>>Насчет эффективности — я даже не знаю, как можно было не понять, о чем речь. Что не так с сохранением частоиспользуемых операций? И повторюсь: для операций РА эффективность является вычислимой. Т.е. берем конкретную операцию из РА, берем некую структуру данных... так вот, для этой пары {операция РА, структура данных} обязательно есть оценка стоимости в терминах K*O(n). И опять же повторюсь, именно так работает оптимизатор, он же не на кофейной гуще гадает...
S>Всё правильно, только оптимизатор работает не с РА, а со значительно более низким уровнем.

Ниже уровня РА ничего нет, кроме исходного кода, имплементирующего эти самые операции (как раз на лабораторках по реляционным БД дают задание реализовать набор операций РА по заданному виду контейнера). Пройдись по любым исходникам SQL-серваков для подробностей. Кстати, по исходникам MS SQL я подробно проходился в далеком 98-м, видел таблицы с константами и формулы вычисления стоимости для пар {объект, операция}.


S>Попробую объяснить на более простом примере: возьмем, скажем, комплексные числа. С точки зрения математики комплексных чисел, операция умножения a * b не имеет никакой "стоимости".

Это с т.з. какой матемитики-то? Если в коде идет реализация этого умножения и мне инетересно оперировать в рантайм ее стоимостью, то для нее обязательно заранее будет подсчитана стоимость в неких попугаях. Но давай вернемся к твоей математике. С т.з. терминов O(n) стоимостью единичных операций никто и никогда не пренебрегает, ты не прав, их сумму выносят за скобки в виде единого коэф К при O(n), поэтому в реальных формулах этот K имеет вполне реальную величину.

S>А вот если мы перейдём к некоторому представлению комплексных чисел в компьютере, то операция a * b будет иметь некоторую реализацию в этом представлении.

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

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

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


V>>Садись, два.
V>>Выделенное неверно. Далее все рассуждения, основанные на этом — тоже.
S>ОМГ, какой апломб. Я поскипаю нерелевантные рассуждения, ок? Вопрос не в том, чтобы "однозначно определить". Вопрос в том, чтобы имея bookmark, получить по нему значение записи за O(1).
S>Вы вот проигнорировали мой пример, а напрасно. Вот у вас есть отношение (id, name, age). Предположим, мы знаем, что name — уникально. Вы хотите найти по name значение age. Стоимость этой "операции" — O(N), где N — количество кортежей в отношении. Это дорого. Что вы сделаете для ускорения? Какая операция проекции даст вам хоть какую-то пользу?
S>Правильный ответ — никакая. Потому что вы никак не измените N. Единственный способ бороться с O(N) — это построить индекс, т.е. упорядоченное отношение (name, RID), где RID — это внутренний идентификатор записи, учитывающий особенности размещения, и позволяющий делать lookup за O(1).

Ну вот, сам же и дошел до всего, надо было лиь сфокусировать твое внимание на этом. Я же говорю, никакого rocket science, всё на поверхности. Вот здесь подробней в последнем абзаце: http://www.rsdn.ru/forum/philosophy/4537996.1.aspx

Автор: vdimas
Дата: 12.12.11

... для случая X#ABCD сам X# физически не обязан храниться в кортеже (физический уровень в IT — это уровень размещения данных по адресам/байтам/смещениям), хотя обязан являться являться неким его св-вом (т.е. атрибутом), например, порядковым номером или еще каким-нибудь значением в какой-нибудь разновидности адресации.

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

V>>Плевать, есть разные индексы. В хеш-таблице у меня будет близко к O(n), но это всё не принципиально в нашем обсуждении.
S>Если у вас в хеш-таблице близко к O(N), значит вы плохо реализовали хеш-таблицу.

Поправился тут же: http://www.rsdn.ru/forum/philosophy/4537923.1.aspx

Автор: vdimas
Дата: 12.12.11

читать близко к O(1).

В Хроме практически не пользуюсь предпросмотром, бо в нем глаза сломать можно из-за мелкого шрифта.


S>В MS SQL строки таблиц вообще всегда имеют ограничение по длине. Это никак не связано с наличием или отсутствием кластерных индексов. Это связано со страничной организацией хранилища (Возможно, в новых версиях это изменили, но во времена, когда я с ним работал, размер кортежа был ограничен 8000 байт).

Ну так что первично, а что вторично? Мне как разработчику видно ровно обратное, фиксированные размеры страниц нужны исключительно для нужд кластерных индексов, которые принципиально живут только в контексте детерминированных размеров. И полно было БД без кластерных индексов с совсем другой организацией памяти.

S>Поэтому алгоритм выбора кластерности индекса связан в первую очередь с эффективностью операций по этому индексу. Есть несколько соображений:
S>1. Для кластерных индексов не нужно делать bookmark lookup. Поэтому имеет смысл делать кластерный индекс по тому ключу, по которому чаще всего происходит поиск разнообразной информации.
S>2. В случае наличия кластерного индекса, остальные индексы вместо RID используют ключ кластерного индекса. Поэтому не стоит делать кластерный индекс по длинному ключу, если других индексов много.
S>3. Поскольку кластерный индекс определяет физический порядок расположения записей, то не стоит делать его по монотонному ключу, если в таблицу будет идти интенсивная вставка из многих потоков — это уменьшит коэффциент параллельности.
S>В общем, всё. Как видим, блобы тут вовсе не участвуют.

Ну это залет, это даже полный ппц, я бы сказал.
Кластерный индекс хорош лишь там, где seek по всем данным в процессе двоичного поиска относительно дешев. Т.е. когда размеры таблицы заведомо меньше размера ОП. Для сценариев, где от относительно большой таблицы в процессе поиска требуется относительно малое кол-во значений по ключу, ключ надо делать некластерным. Профит получается многократный. Пример с 4-хкратным профитом я приводил. Надо просто помнить, откуда растут ноги у понятия "индекс" изначально (в первых СУБД не было кластерных индексов, из-за ограничений на размер ОП, очевидно), там же: http://www.rsdn.ru/forum/philosophy/4537996.1.aspx

Автор: vdimas
Дата: 12.12.11

V>>Тем не менее, классический SQL оперирует понятиями реляционного исчисления + непосредственно поддерживает некоторые операции РА, а кое-какие диалекты поддерживают еще больше операций РА, чем даже классический SQL-92.
S>Классический SQL не оперирует понятиями реляционного исчисления.

Ну оставайся при своем.

V>>Взаимосвязь SQL с реляционным исчислением и алгеброй там же: http://www.mstu.edu.ru/study/materials/zelenkov/ch_4_6_1.html
S>Вы сами-то это читали?
S>

S>В то же время SQL подвергается суровой критике как раз за недостаточное соответствие реляционным принципам

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

SQL (Structured Query Language — структурированный язык запросов) основывается на некоторой смеси алгебраических и логических конструкций.

Полностью согласен. В SQL торчат уши как реляционного исчисления, так и примитивов РА.

S>Рад за ваше чувство юмора.

Дык, пора бы знать уже, что в IT есть "физический уровень". ИМХО, прямо сейчас стоит закруглить насчет БД и сделать gosub на "абстракции". Иначе разговор ни о чем.


V>>Index scan — это по прежнему операция ограничения из РА, а bookmark lookup — один из видов того самого соединения.
S>Нет.

Достойный аргумент. Ничего если я предположу отсутствие навыков по операциям РА, бо эти вещи как бы аксиоматичны?


S>Индексы не являются "декомпозицией" исходного отношения. Чтобы начать разговаривать об индексах, нам придётся перейти от абстрактного термина "отношение" к конкретному термину "таблица", и начать учитывать подробности хранения данных. Вы почитайте учебник по устройству СУБД — того же Гарсиа-Молина. Оптимизатор "видит" совсем другую модель, чем вы в ваших задачках по РИ.

Ес-но, только что мне мешает видеть ту же самую модель, что и оптимизатор? Как я тогда буду писать эффективные приложения для СУБД, если я не понимаю показания плана оптимизатора? Или вот я разработчик СУБД, с какой радости я не могу прикладывать РА к индексам? Это откуда такие запреты-то? Я не только могу, но я обязан использовать весь этот аппарат, чтобы не породить УГ.


S>Просто большинство "учебников" остаются на уровне плохого пересказа РА и РИ, с внезапным перепрыгиванием в сторону SQL (избегая обсуждения природы различий между SQL и абстрактной реляционной моделью), и, собственно, всё. Следующие учебники уже берут с места в карьер изложение подробностей конкретной СУБД, опять же избегая обсуждать связь этих подробностей с реляционной моделью.

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

V>>>>Использование разного порядка сканирования индексов — это физическое отличие или логическое?
S>>>Конечно же это отличие физического плана. В логическом плане никаких индексов нет.
V>>Сорри, но выделеное профанирует вообще весь спор об абстракциях.
S>К сожалению нет. Вы, похоже, как-то неправильно представляете себе устройство оптимизаторов запросов и связанные с этим теории.

Да правильно представляю. Исходники смотрел в свое время. Более одной БД. Представляю как есть, хоть и похоже, не так, как это представляешь себе ты.

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

Давай возьмем другие термины, вместо "физический" и "логический", ок? А то уже совсем грустно.

S>Очень на то похоже. Я не очень понимаю ваш вопрос. Своё видение того, как всё устроено, я изложил. На всякий случай приведу его ещё раз:
S>1. Есть Реляционная Модель. Грубо говоря, построена на теории множеств, вводит некоторое математическое пространство.

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

S>1.а Есть неразрывно связанные с РМ Реляционная Алгебра (механизм по конструированию из одних отношений других) и РИ (механизм по описанию уравнений над реляционной моделью)
S>Это пока что всё один и тот же уровень абстракции.

Опять не так. Есть операции над этой моделью (суть над исходной абстракцией), РА-операции НЕ являются независимыми абстракциями, а лишь дополняют терминологию модели в области динамики, давая имена примитивным операциям непосредственно над моделью. Т.е., вот есть некая структура, в вот примитивные (неделимые) операции над ней. Это один и тот же уровень абстракции, бо не происходит ни как уточнения подробностей, ни уменьшения исходного кол-ва подробностей, т.е. это один и тот же уровень согласно самого определения "абстракция".

Далее. Есть реляционное исчисление — это (ты абсолютно правильно сказал) банальные уравнение, заданные в терминах модели. Как и любое уровнение, в уравнениях в РИ заданы характеристики результата, а сами уравнения имеют более одного решения в общем случае. Так вот, я не соглашусь, что любые уравнения — это тот же уровень абстракции, что и термины, которыми уравнение оперирует. Коль уравнение задает вид результата, оно заведомо абстрагируется от действий по получению этого результата. Здесь происходит как в классике, декларативность одних сущностей по отношению к другим. Тот самый более высокий уровень абстракции. Так вот, цель построения реляционной модели была как раз в обслуживании исключительно РИ, бо это РИ шла как исходная (полезная) задача по обработке данных.

S>Итого, минимум 2 уровня абстракции.

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


Переходя к СУБД мы переходим в область другой принятой терминологии, но пока еще не переходим ни на какой новый уровень абстракций. Например:

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

Какое красивое соответствие 1-в-1.

S>2. Есть модель SQL.

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


S>Она отдалённо напоминает Реляционную Модель, но существенно отличается от неё в важных нюансах.

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

S>В частности, введены понятия NULL и трёхзначной логики

И? Реляционная модель никак не ограничивает область значений доменов. Она ими даже не интересуется. Если некая область хочет включить NULL, Nil, папу_римского — да ради бога. Насчет трехзначной логики аналогично — бредятина. По предикатам в в SQL (например в операции JOIN) всегда только два ветвления, т.е. предикаты приводимы булевскому значению, хоть и неявно. Иначе они не могли бы исопльзоваться как предикаты. Или ты имел ввиду, что есть операции сравнения в домене значений {true, false, NULL}? Ну и какие проблемы? Определи этот домен и операции по нему для конкретной схемы реляционной модели и вперед — конкретно реляционной модели, повторюсь, это по барабану.

S>а также явным образом разрешены дубликаты в таблицах (в отличие от отношений).

Угу, в таблицах с отсутствующим первичным ключом. Разумеется, такие таблицы не могут иметь аналогов из реляционной модели, даже если в таблице нет дубликатов. И единственный доступ к данным — это тупой перебор. А раз так, т.е. раз аппарат реляционного исчисления к ним не применим, я бы эти "фишки" вообще не обсуждал... Ведь для подобных таблиц не требуются никакие теории.

Кстати, уместно вспомнить, что операция union без специального хинта таки убирает дубликаты, прямо как в РА... Это к слову, что SQL не подерживает напрямую операции из РА.


S>Эти отклонения внедрены как компромисс между простотой РМ и требованиями удобства в реальных задачах. Важный нюанс: напрямую модель SQL нигде не ссылается на реляционную модель; все взаимосвязи — исключительно идеологические, на уровне "о, отдалённо похожую штуку мы видели и там".

Тогда не существовало бы теории реляционных БД, коль она не нужна?

S>Реально сходство примерно такое же, как между преобразованием Фурье и поворотом векотор в трёхмерном пространстве.

Я бы скорее сравнил Фурье и корреляцию по сетке частот. По произвольной сетке — это просто корелляция, но по сетке с шагом 1/N — оппа!!! уже преобразование Фурье. Примерно так же. Разница в терминологии и ширине области приложения. Фурье — суть частный случай, но отнюдь не бесполезный из-за этого. Скорее наоборот, самый полезный частный случай был разобран до ниточек и были выведены очень полезные прикладные алгоритмы, на которых живет чуть более чем всё цифровое медиа + все современные сетевые технологии. Поэтому как разработчику в области обработки информации необходимо разбираться, откуда растут ноги Фурье (ведь частичное преобразование Фурье — это опять "просто" корреляция, но иногда достаточно и этого) для написания адекватных приложений, так разарботчик БД должен владеть РА и РИ. Это даже неприлично обсуждать, ИМХО.


S>2.а. Помимо черт реляционной модели, в SQL есть также черты теории транзакций. Как и в случае РМ, модель SQL привносит в чистую транзакционную теорию некоторые важные модификации, в частности вводит понятие уровней изоляции. Это понятие очень часто неверно интерпретируется разработчиками из-за отстутствия вменяемой литературы, покрывающей зазор между теорией и практикой.

Для реляционной модели это неважно. Повторюсь, в РА важна последовательность операций, никакая конкуренция не рассматривается. Транзакционность — это из конкурентной реализации конкретно СУБД следует, более ни от чего. Реализация простейшей СУБД могла бы быть и не конкурентная, а как в классике СМО. В общем, это другой раздел прикладной науки, который мы пока не обсуждали.. но если очень хочешь...

S>2.б. Существенная роль в модели SQL отводится элементам, которых в математических моделях вовсе не было. Это всяческие view, триггеры, индексы, хранимые процедуры и прочая кунсткамера.

Угу, в разделе DDL... Я все ждал, когда же, наконец, прозвучит DDL как "последний аргумент"... Че-то долго ждал.


S>3. Есть модели реализации конкретных СУБД.
S>3.а. В них добавляются расширения модели стандартного SQL
S>3.б. А также придаётся конкретный смысл абстрактным понятиям модели SQL.
S>Именно на этом уровне работают оптимизаторы запросов. Большинство промышленных СУБД позволяют разработчику самому выбирать, на каком уровне абстракции работать — 2, 3а, или 3b. То есть я могу просто написать select age from person where name = 'vdimas', оставаясь в рамках SQL-92. Могу воспользоваться расширениями конкретной СУБД, создав, скажем, table-valued функцию для того же запроса. А могу опуститься на уровень реализации, хинтами вынудив оптимизатор использовать специфический индекс.

Я пока еще не вижу противоречий с примитивами РА. Намомню, что формулы реляционного исчисления имеют в общем случае более одного решения в терминах РА. Сама РА оперирует заданной схемой декомпозиции отношений и зависимостями над атрибутами. Поэтому уместно любое решение, которое подходит под заданные зависимости. Ну, указал ты хинтами предпочтение одного из решений, в чем проблема-то? О чем речь?


V>>Натурально обидно после стольких постов увидеть, что "в логическом плане никаких индексов нет", это же сколько потраченного времени...
S>Срыв покровов произошёл? Ничего, со временем в голове всё устаканится.

Да нету никаких индексов на физическом уровне просто. Индексы — это тоже логическая единица модели конкретной СУБД. И к ним все так же применимы операции из РА аж бегом и их таки применяют разработчики СУБД. И как можно пытаться нагнать туману на примитивнейшие вещи и называть это "срывом покровов"? Поделись каким-нить знанием, которое будет новым и интересным, тогда и скажешь так. А пока что ты просто выдаешь собственное представление, в котором еще с первых постов невооруженным взглядом виден большо-о-ой такой провал в теории реляционных БД. Ничего личного, но споры относительно РА я бы предпочел вести в терминах самой РА, взаимоотношения операций, разбора конкретных типовых задач из области РА и т.д., а не путем перестрелки с помощью выхваченных из контекста фраз "из интернета".


V>>Угу, смотрю в книгу, вижу известно что. Короче, преобразования данных, выполняемых в терминах РА — это ВСЕГДА императивный алгоритм, построенный на примитивах-операциях РА. Важна последовательность операций, а сами аргументы операций — это результаты (в общем случае) предыдущих операций.
S>Вы попробуйте хотя бы читать те ссылки, которые сами приводите.
S>

S>В частности, ни один из подходов нельзя назвать « более непроцедурным « по сравнению с другим.

S>Это чтобы вы не думали, что РА как-то фундаментально менее декларативна, чем РИ.

Я могу еще повторить больими буквами, если не понял — РА всегда оперирует неким последовательным алгоритмом. По другому просто никак. Или покажи обратное на примере из более одного шага в решении или прими как данность.

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

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


V>>А почему операции РА не могут быть применены к самим индексам? Я никак не воткну в этот "запрет". Не обоснуешь?

DG>сейчас речь не о том: могут или не могут.
DG>а речь о том: нужны или не нужны индексы в рамках реляционной модели и алгебры?
DG>и ответ — не нужны, пока речь идет лишь о корректности реляционной алгебры.

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


V>>Индексы — это реально существующие объекты БД, созданные не самой базой, но исключительно разработчиками. Зачем делать вид, будто их нет?

DG>потому что можно обойтись и без них

Для случая эффективной реализации требований/ограничений целостности — нельзя.

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

V>>Это верно в той области ПО, для которой эффективность не является конкурентным преимуществом. Например, для заказного ПО, там же никакой конкуренции... Нужна лишь некая "достаточная" производительность.

G>Да-да-да. Забавная байка. У тебя есть сведения о корреляции производительности и продаж для определенного класса программ?

Есть.


G>Уверен что нет, тогда зачем ты продолжаешь повторять то что не доказано?

В личку уже приглашал, заканчивай бубнить одно и то же.


G>С другой стороны "достаточная производительность" явно вытекает из экономической целесообразности: нем смысла тратить на оптимизацию больше чем нужно.

Это в твоей уютной реальности заказного ПО.


V>>А в коробочном ПО в реальности бывает так, что профайлер показывает до 30% затрат на всего одну из самых затратных операций, но она никак не оптимизируема, всё, упёрлись в предел. Зато остальное можно подтянуть, то самое, которое 1-2% каждое в среднем, но примерно вдвое общую эффективность поднять, подняв каждую из мелочей многократно. Это из реальной практики... Для каждого такого случая нужны банально идеи, бо показания профайлера тебе код не напишут.
G>А ты вообще прочитал то что я процитировал? В 5 пункте fixable слово видел?

И?

V>>Есть еще момент: эффективность не всегда определяется пропускной способностью, зачастую идет требования минимизации latency (у нас по работе, например), а в этом деле, когда речь идет о единицах микросекунд, профайлерами уже и близко не пахнет.
G>А чем пахнет? ты ведь как-то меряешь этот самый latency или ты по коду пытаешься его угадать?

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

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

G>Не написано что должен, следовательно не должен. Элементарная логика.

Ну а я напишу что "должен" и хана твоей "элементарной логике"

G>Более того, не всегда приходится свой код оптимизировать.

Слышали уже. Охотно верим.

G>Счегобы? Многие умеют писать программы используя ленивость и асинхронность. Далеко не все могут предположить по внешнему виду время работы.

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


G>Пример на форуме показал это очень явно. Даже местные гуры перформанса не смогли сходу обнаружить проблему. Так в коде не было ни ленивости, ни асинхронности, ни десятка уровней косвенности.

Мноею пример еще не разбирался подробно, как это происходит в случае с кодом во время оптимизации. Но пару слабых мест указал при даже при чтении по диагонали. Но DarkGray разобрал подробно и все выкладки дал, ты невнимателен.

DG>>и на всякий случай напишу очевидные вещи:
DG>>1. через профайлер можно прогнать лишь ограниченное кол-во сценариев, которое много меньше, чем поддерживаемое программой кол-во сценариев
DG>>2. bottleneck необходимо уметь обнаруживать до того, как на него наткнутся в реальном применении (особенно это актуально для защиты от DDOS)
G>Еще раз читай то что я процитировал. Первый пункт.

Да подтереться им можно в среде с повышенными требованиями к надежности и отзывчивости. Увы и ах. Даже в разобранном примере рассматривался один и тот же сценарий, хотя там нужно было рассмотреть область как минимум по двум координатам. В общем случае показанный подход — это профанация, хотя потянет как вводный урок для новичков.

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

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

А если они неустранимы? Т.е. если самая затратная операция неоптимизируема никак? То уже всё или как?

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

S>В реальных программах всё гораздо хуже и запутаннее. Без измерений можно потратить месяц на вылизывание кусочка кода, который почти не повлияет на общую производительность.

Таки не надо смещать акценты, речь шла конкретно про профайлер. Даже если мы "тупо" замеряем "самый верхний цикл" и видим, что оптимизация некоего куска не приносит бенефитов, с чего бы тратить на него месяц?

DG>>потому что можно обойтись и без них

V>Для случая эффективной реализации требований/ограничений целостности — нельзя.

помнишь раньше говорилось про разделение и про монолиты...

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

из монолитной РА можно выделить два слоя:
РА с точки зрения корректности (и здесь еще нет индексов),
РА с точки зрения корректности + эффективности (и здесь уже есть индексы).
каждый из этих слоев используется для решения своих задач:
1. если хочется посчитать какой путь выполнения будет выигрышнее, то используется второй слой
2. если же хочется доказать, что преобразования используемые данным кодом верные, то достаточно использования первого слоя.

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

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

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

V>>Исследования для одного из случаев...
S>О да. "Обещали показать выступление камерного оркестра, а ограничились жалким частным случаем для K равного трём"...

Тем не менее, именно так. У нас проводятся исследования малость пошире. Где-то на полтора-два порядка. Хотя согласен, что исследование по ссылке потянет как учебное пособие для новичков.

S>В моём понимании, главная характеристика хорошего программиста — понимание собственной органиченности.

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

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

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

V>>>Это верно в той области ПО, для которой эффективность не является конкурентным преимуществом. Например, для заказного ПО, там же никакой конкуренции... Нужна лишь некая "достаточная" производительность.

G>>Да-да-да. Забавная байка. У тебя есть сведения о корреляции производительности и продаж для определенного класса программ?

V>Есть.

Показывай.

V>>>А в коробочном ПО в реальности бывает так, что профайлер показывает до 30% затрат на всего одну из самых затратных операций, но она никак не оптимизируема, всё, упёрлись в предел. Зато остальное можно подтянуть, то самое, которое 1-2% каждое в среднем, но примерно вдвое общую эффективность поднять, подняв каждую из мелочей многократно. Это из реальной практики... Для каждого такого случая нужны банально идеи, бо показания профайлера тебе код не напишут.
G>>А ты вообще прочитал то что я процитировал? В 5 пункте fixable слово видел?
V>И?
Прочитай еще раз

V>>>Есть еще момент: эффективность не всегда определяется пропускной способностью, зачастую идет требования минимизации latency (у нас по работе, например), а в этом деле, когда речь идет о единицах микросекунд, профайлерами уже и близко не пахнет.
G>>А чем пахнет? ты ведь как-то меряешь этот самый latency или ты по коду пытаешься его угадать?
V>Специальные тесты на производительность нужны, с максимальной изоляцией, чтобы минимизировать паразитную постоянную составляющую измерений.
То есть ты все равно меряешь.

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

DG>я говорю, что РА изначально рассматривает лишь корректность (и тут индексов еще нет), а ты же сразу к этому подцепляешь эффективность (и тут уже, конечно, индексы появляются). Твой подход приводит к монолитному рассмотрению корректности всегда в сцепке с эффективностью.

Ок, выкини эффективность оставь только проверку уникальности. Получишь некий "виртуальный" индекс, типа кластерного.
Какая разница-то? Нет ли здесь случайно путаницы "сущности" из мира ПО и банального физического формата хранения данных? Это будет та же сущность даже с тем же публичным интерфейсом, независимо от внутреннего устройства. Таблица в БД, это ведь тоже нихрена не монолит в реальности, это сложнейшая подсистема с кучей плюшек. Но мы рассматриваем маппинг отношения на таблицы и не потеем по поводу деталей.


DG>из монолитной РА можно выделить два слоя:
DG> РА с точки зрения корректности (и здесь еще нет индексов),
DG> РА с точки зрения корректности + эффективности (и здесь уже есть индексы).

Здесь исторически торчат уши подробностей храния, таки. Угу.
Есть два основных способа — по столбцам, и по строкам. Есть способ смешанный, через декомпозицию: сначала часть столбцов, где данные идут по строкам, потом остальные столбцы, но опять по строкам. Вот так индексы, собственно, и появились — это выделенная часть данных, над которыми совершается большинство операций. Короче, вопрос в силе: коль для целей хранения данных в некоем конкретном представлении мы провели стандартную декомпозицию, какие проблемы использовать аппарат реляционной теории над этой декомпозицией? Путь этот аппарат недоступен для прикладного программиста, которому виден только SQL, но уж разработчик СУБД просто обязан использовать все наработки из реляционной теории.

Вообще, я не считаю, что из РА что-то следует выделять, это же абстракция — уже всё выделено, что надо. Ты не в ту сторону стрелочки->зависимости ставишь. ИМХО, ровно наоборот: берем любую конкретную частность, и, если удается пренебречь деталями этой частности для достижения соответствия условиям знакомой абстракции, то нам становится доступен весь матаппарат сей абстракции.

Ведь СУБД не из реляционной теории выросли, право, а ровно наоборот: реляционная теория разрабатывалась уже на основе опыта эксплуатации существующих БД, и была разработана с целью иметь обслуживающий их формальный аппарат, как раз для понимания происходящего во всякого всякого рода частностях и их комбинациях. Это что-то вроде "паттернов" (тоже терминология + типовые задачи/операции), только с уклоном в специальную организацию данных, подчиняющуюся реляционной модели. Тебе не пофиг ли, на каком из слоев ты применяешь сии паттерны? Где подходят, там их и применяют.

DG>каждый из этих слоев используется для решения своих задач:

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

DG>1. если хочется посчитать какой путь выполнения будет выигрышнее, то используется второй слой
DG>2. если же хочется доказать, что преобразования используемые данным кодом верные, то достаточно использования первого слоя.

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


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

Ниче не надо, если модель работы твоих сущностей, реализованных поверх этой памяти, будет удовлетворять ограничениям реляционной модели. Можно будет использовать напрямую на любом из "слоев". Все слои — сугубо в твоей голове и артефактах документации, более нигде. А что если я заверчу что-нить покруче, например, многомерные таблицы? Хранение отношений прямо в доменах атрибутов? Не запрещено же... И так с произвольной вложенностью? Смог бы я для каждого нового уровня/слоя использовать один и тот же матаппарат? Да легко!