Межвузовский сборник научых трудов «Математическое и программное обеспечение вычислительных систем». Рязань, РГРТА, 2001.

 

УДК 681.3.06:519.688

С.В.Аникеев, А.В.Маркин

г.Рязань, Рязанская государственная радиотехническая академия

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

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

Реляционная модель данных, впервые предложенная Коддом [1], а затем развитая и дополненная другими авторами [2], является основой современных технологий баз данных, так как подавляющее большинство известных СУБД, таких, например, как Oracle, Interbase, MS SQL, DB2, являются реляционными. В свою очередь любую из реляционных СУБД можно рассматривать как компонент некоторой информационно-вычислительной системы, используемой для решения задач автоматизации различных областей человеческой деятельности.

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

  • размера платы за пользование газом;
  • объема расходуемого газа;
  • стоимости планового профилактического обслуживания газового оборудования;
  • пени за просрочку платежей;
  • сальдо в связи с возможными изменениями характеристик за прошлые учетные периоды.

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

Для повышения скорости предлагается использовать способ организации вычислений, основанный на групповом выполнении вычислительных операций над реляционной моделью данных посредством языка реляционной алгебры. Каждая вышеназванная вычислительная операция при таком способе должна быть сведена к одному или нескольким выражениям реляционной алгебры, преобразующим набор отношений с исходными данными в отношение, содержащее результат вычислений необходимого значения для каждого абонента. Возможность такого подхода основывается на том факте, что для каждого абонента вычисление требуемой величины можно свести к расчету соответствующих значений одной и той же функции, но с различными значениями аргументов [3,4].

Известно, что в современных РСУБД операциями над отношениями (таблицами) выполняются посредством высокоуровневого декларативного языка обработки данных. Один из таких языков – язык структурированных запросов SQL, который, согласно Дейту, “является стандартным реляционным языком и в настоящее время поддерживается практически всеми продуктами, представленными на рынке” [2]. SQL является реляционно-полным языком. Это означает что любому выражению реляционной алгебры можно поставить в соответствие одно или несколько семантически эквивалентных выражений SQL. Таким образом, с практической точки зрения, выполнение последовательности выражений реляционной алгебры будет представлять собой последовательность операций, записанных на SQL. В дальнейшем такую последовательность мы будем называть запросом.

Предположим, что существует отношение R со схемой, состоящей из конечного множества атрибутов {L, K1, K2, …, Kr, A1, A2, …, Ak}. Здесь L – уникальный номер, однозначно идентифицирующий каждого абонента, например, лицевой счет; K1, K2, …, Kr – атрибуты, функционально определяющие A1, A2, …, Ak; A1, A2, …, Ak – атрибуты, каждый из которых является конечным множеством всех значений характеристик одного типа для всех абонентов. В данном отношении L является первичным ключом. Предположим также, что существует отношение q со схемой {L, N}, каждый элемент атрибута N которого является значением n для соответствующего абонента, рассчитанным как скалярная функция f от скалярных значений A1, A2, …, Ak. Очевидно, что получение отношения q полностью решает поставленную задачу, так как q содержит значения n для каждого из абонентов. Таким образом, справедлива запись:

q = F(R), (1)

где F – выражение реляционной алгебры, преобразующее R в q.

Пусть формальный синтаксис реляционной алгебры задан нормальной формой Бэкуса-Науэра [5], скалярное выражение в которой может быть константой, атрибутом или функцией, параметры которой – список скалярных выражений. В качестве функции может выступать любая известная арифметическая функция (сложение, вычитание, умножение, деление и др.), а также специальные операции.

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

q = ( EXTEND R ADD f(A1, A2, …, Ak) AS N) [ L, N ] (2)

Результатом вычисления будет требуемое множество q.

Следует отметить, что непременным условием вычисления q по формуле (2) является наличие атрибутов A1, A2, …, Ak в одном отношении. Однако, в случае если атрибут Ai зависит не только от ключа отношения L, но и от другого атрибута или набора атрибутов, или зависит от L транзитивно, то отношение R характеризуется некоторой избыточностью, которые, согласно теории баз данных [6], приводят к аномалиям обновления. Согласно той же теории, для решения этой проблемы такое отношение должно быть нормализовано, т.е. проективно разбито на несколько отношений с целью исключения приводимых функциональных зависимостей. В нашем случае нормализация приводит к тому, что исходные данные для расчета q могут находиться не в одном, а в нескольких результирующих отношениях.

Пусть r1, r2, … rs - набор отношений, полученных после нормализации R. Тогда, с учетом вышесказанного, выражение для вычисления q примет вид:

q = F’ (r1, r2, … rs) (3)

Здесь F’ – выражение реляционной алгебры, преобразующее набор нормализованных отношений r1, r2, … rs в отношение q.

В силу того, что основным свойством нормализация является возможность выполнения обратного преобразования, вычисление q по формуле (3) должно проводиться в два этапа:

- получение из набора отношений r1, r2, … rs исходного отношения R;

- вычисление q по формуле (2).

В теории баз данных известно, что исходное отношение может быть получено из набора соответствующих ему нормализованных путем их естественного соединения [6]. Причем, в силу коммутативности и ассоциативности операции соединения, порядок их соединения не имеет значения.

Таким образом, (3) примет вид:

q = (EXTEND (r1 JOIN r2, JOIN … JOIN rs) ADD f(A1, A2, …, Ak) AS N) [ L, N ] (4)

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

 

Кортеж 1
 
...
страница 1
кортеж pR
 
...
...
кортеж N-pR+1
 
...
Страница N/pR
Кортеж N
 

Рис.1 Отношение q.

 

Пусть расчет соотношения q производится по формуле (2), то есть в качестве исходного выступает одно отношение R. Пусть количество кортежей или кардинальное число отношений равно N. Предположим также, что отношения хранятся на диске по страницам и на одной странице помещается pR кортежей для отношения q (рис.1) и pR1 кортежей для отношения R (рис.2).

Кортеж 1
 
...
страница 1
кортеж pR1
 
...
...
кортеж N-pR1+1
 
...
Страница N/pR1
Кортеж N
 

Рис.2 Отношение R

При последовательном вычислении, в худшем случае СУБД должна выполнить N операций чтения (для каждого кортежа отношения R) и N операций записи (для каждого кортежа отношения q). В лучшем случае, когда СУБД анализирует наличие страницы в оперативной памяти, будет произведено N/pR1 операций чтения и N/pR операций записи. Количество операций чтения и записи здесь зависит от количества операторов языка манипулирования данными. Очевидно, что последовательный расчет величины n для всех абонентов предполагает также последовательное чтение исходных данных и запись результатов для каждого из них. Кроме того, при таком подходе логика операции оказывается сосредоточенной в алгоритме, представленным, как правило, последовательностью операторов языка высокого уровня, что существенно снижает возможности по оптимизации запроса.

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

Аналогичные рассуждения справедливы, если исходные данные представляют собой не одно отношение, а их набор r1, r2, … rs , и q вычисляется по выражению (4). Для этого случая, также как и для (2), наличие логики запроса в самом выражении позволяет выбрать более эффективную стратегию его выполнения.

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

В качестве примера рассмотрим расчет размера платы за природный газ группе абонентов ГРО, не имеющих приборы учета [3]. Воспользуемся упрощенным вариантом расчета, т.е. без учета льгот, домашних животных, нежилой площади и т.д..

Пусть, размер ежемесячной платы абонентов за газ без учета льгот рассчитывается по формуле:

N = P*T1 + M*T2, где

T1 - стоимость потребления газа, расходуемого на приготовление пищи и горячей воды из расчета на одного человека (руб./ чел.);

T2 - стоимость потребления газа, расходуемого на отопление жилой площади (руб./m2);

P - количество членов семьи абонента (чел.);

M – размер жилой площади, отапливаемой от газовых отопительных приборов (m2).

Схема отношения R в этом случае будет выглядеть как {L, P, M, R1, R2, T1, T2 }. Здесь:

L - лицевой счет абонента;

R1 - код режима потребления газа на приготовление пищи и горячей воды;

R2 - код режима потребления газа на отопление.

Очевидно, что отношение R не находится в третьей нормальной форме, так как имеют место транзитивные зависимости L ® R1 ® T1 и L ® R2 ® T2. Для исключения зависимостей разобьем данное отношение на три: r1{ L, P, M, R1, R2 }, r2{ R1, T1} и r3{R2, T2 }. Так как каждый из атрибутов полученных отношений неприводимо зависит от ключа (в r1 – L, в r2 – R1, в r3 - R2), все они находятся в НФБК.

Таким образом, выражение для вычисления q, включающего в себя множество начислений группе абонентов, примет вид:

q = EXTEND (r1 JOIN r2, JOIN r3) ADD (P*T1 + M*T2) AS N) [ L, N ].

На языке SQL приведенное выше выражение может быть записано следующим образом:

SELECT r1.L AS L, r1.P*r2.T1+r1.M*r3.T2 AS N;

FROM r1, r2, r3;

WHERE r1.R1 = r2.R1 AND r1.R2 = r3.R2

На рис.3 представлены графики, отражающие зависимость времени вычисления q различными способами от количества абонентов. Расчеты проводились с использованием СУБД FoxPro 2.6.

Рис.3. Зависимость времени вычисления от количества абонентов для последовательного
расчета и расчета средствами целевого языка РСУБД.

В рассматриваемом примере средний выигрыш в скорости вычислений, наблюдаемый на графике, составляет 35%.

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

Предлагаемый способ реализован в автоматизированной системе расчетов с населением за услуги газоснабжения “АБОНЕНТ ГРО” [7,8], использующейся в 25 газораспределительных организациях РФ. Система позволяет автоматизировать деятельность различных отделов ГРО, связанных с обслуживанием населения, накапливать и хранить данные о различных аспектах взаимоотношений ГРО и абонента, получать необходимую справочную и статистическую информацию.

Библиографический список
  1. Codd E.F. A Relational Model of Data for Large Shared Data Banks // CACM. – 1970. – 13, № 6.
  2. Дейт, К., Дж. Введение в системы баз данных, 6-е издание: Пер.с англ - К.; М.; СПб.; Издательский дом «Вильямс», 1999. – 848 с.
  3. С.В.Аникеев, А.В.Маркин. Методика расчета размера платы за газ населением при наличии льгот. Межвузовский сборник научных трудов «Вычислительные машины, комплексы и сети», c.53-57. Рязань, 1999.
  4. С.В.Аникеев, А.В.Маркин. Математическое обеспечение системы расчетов с населением за услуги газоснабжения. Материалы международного научно-технического семинара «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань, 1999.
  5. Грэй П. Логика, алгебра и базы данных. М.: Машиностроение, 1989. – 368 с.
  6. Мейер Д. Теория реляционных баз данных: М.: Мир, 1987. – 608 с.
  7. Маркин А.В., Евстефеев А.С., Аникеев С.В. «Технологии и системы сбора, обработки и представления информации об абонентах городской газовой службы». Тезисы доклада Международной конференции «Технологии и системы сбора, обработки и представления информации». Рязань, РГРТА, сентябрь, 1995 г.
  8. Маркин А.В., Аникеев С.В. Автоматизированная система «Абонент». Межвузовский сборник научных трудов «Алгоритмическое и аппаратное обеспечение систем автоматизации научных исследований». Рязань, РГРГА, 1996 г.