Нотация
Мы используем символы R (с нижним регистром или без него) для обозначения отношений, ? (с нижним регистром или без него) для обозначения предикатов, E (с нижним регистром или без него) для обозначения реляционных выражений, attrs(E) для обозначения атрибутов результата E и a для обозначения кортежа атрибутов. В соответствии с семантикой SQL мы трактуем отношения как мультимножества кортежей и используем мультимножественный вариант реляционной алгебры [DGK82]. Мы предполагаем знакомство читателей с этой алгеброй и описываем только операцию группирования/агрегации и мультимножественную операцию ?-полусоединения. Мы используем операцию группирования/агрегации g? f , где g обозначает атрибуты группирования, а f – агрегатные операции, которые выполняются над группами, определяемыми атрибутами группирования. (Эта нотация заимствована из [EN94, Klu82]; такая операция требуется для работы с группировкой и агрегированием в стиле SQL.)
