Как показать, что что-то увеличивает реляционную выразительную силу?

Question

Как мне показать, что что-то увеличивает выразительную силу отношений? Например, мне дали задачу, в которой мне нужно показать, увеличивает ли выразительность мощь добавления некоторых определенных функций в запросы SQL select-project-join. Я приведу пример и покажу, что это невозможно выразить?

Answer 1

Сначала вы должны решить, что это выражается двумя обозначениями. (То есть то, что они выражают, то есть выражают, то есть обозначают.) В противном случае проблема не имеет большого смысла.

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

Когда нам говорят, что выражают наши две нотации, нам обычно дают для каждого:

• некоторые примитивные выражения
• некоторые правила генерации выражений
• некоторые примитивные вещи
• некоторые правила для генерации вещей
• сопоставление выражений с вещами

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

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

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

Смотрите обсуждения в книге Алисы или в книге Майера. Они касаются языков запросов к базе данных. Например, выразительно эквивалентные версии реляционной алгебры, реляционного исчисления кортежей и реляционного исчисления предметной области, а также другие языки, такие как логика предикатов и версии Datalog.