Небезопасные выражения для исчисления кортежей
Рассмотрим отношение R1 (бросок №, отметки). Предположим, что записи в R1 равны (1,20) и (2,25), и пусть область с номерами броска и метками будет всеми натуральными числами.
Теперь выражение для исчисления кортежей типа { t | ~ (t принадлежит R1) } небезопасно, так как мы можем иметь бесконечное число возможных кортежей. Предположим, что я ограничиваю область значений roll no и помечает как положительные целые числа от 1 до 50. Теперь будет ли указанное выше выражение по-прежнему оставаться небезопасным? Я думаю, что это не должно быть небезопасно, поскольку у нас есть конечная область.
1 ответ
Конечный против бесконечного играет определенную роль в том, является ли запрос безопасным. Но это не значит, что запрос безопасен, когда ни один домен не является бесконечным.
Безопасные запросы - это те, синтаксис которых гарантирует независимость от домена. Независимый от домена запрос - это тот, чей результат можно вычислить с помощью операторов реляционной алгебры на базовых отношениях. Реляционные операторы не могут (по замыслу) вычислить отношение кортежей, которые имеют заголовок базового отношения, но не находятся в нем. За R то есть { t | t NOT IN R }, Я бы дал эквивалентное реляционное выражение, но его нет, и в этом суть. Другой способ это сделать - независимый от домена запрос возвращает один и тот же результат независимо от того, какие у него домены. (Отсюда и название.) Бесконечные домены используются в примерах, потому что зависимый от домена запрос с бесконечным доменом будет иметь бесконечное число строк в своем результате, и ожидается, что этот бесконечный результат делает очевидным, что он не может быть вычислен. В любом случае, эти определения независимости от домена просто не говорят о том, что запрос не зависит от домена / безопасен, когда нет бесконечного домена.
Операторы реляционной алгебры ограничиваются вычислением наборов кортежей, выражаемых в исчислении, где каждое НЕ следует после И, и все такие И НЕ и все ИЛИ имеют операнды с одинаковыми атрибутами. Первые рассчитываются через МИНУС, а последние - через СОЮЗ. Вычисление зависимых от домена / небезопасных результатов запроса для конечных доменов является простым. (В конце концов, мы знаем, какие кортежи не находятся в отношении.) Но необходимые дополнительные реляционные операторы имеют вычислительную сложность, основанную на произведении мощностей областей базовых отношений, а не на основе гораздо меньшего числа кортежей в базовые отношения. Конкретные операторы реляционной алгебры специально выбраны, чтобы избежать этих запросов / вычислений.
(Убедительное доказательство / объяснение основано на выводе с помощью действительных правил рассуждения из принятых допущений и теорем. Если вы хотите найти недостаток в своих рассуждениях, вам нужно дать его в соответствии с рекомендацией, которую вы принимаете и разделяете.)
PS Если вы детально проработаете свой пример с доменами и данными, то обнаружите, что даже с конечными доменами трудно найти выражение реляционной алгебры, возвращающее его значение. Потому что нет ни одного. (Использование "реляционной алгебры" в том же смысле, что и независимость / безопасность домена).