Устройство умножения реляционных отношений Советский патент 1988 года по МПК G06F17/27 

41ь

О9

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

Цели изобретения - расширение области применения устройства за счет выполнения п операций реляционного умножения, где .

На фиг,1 изображена схема предла- гаемого устройства, на фиг.2 - пример реализации блока управления.

Устройство содержит первый счетчик 1 , первый дешифратор 2, первый блок 3 памяти, служебный разряд 4 блока 3 памяти, первый регистр 5, служебный разряд 6 регистра 5, группу 7 из р элементов И, второй регистр 8, второй 9 и третий 10 счетчики, второй П, третий 12 и четвертый 13 дешифраторы, первый 14 и второй 15 коммутаторы, узел 16 сравнения, первый 17 и второй 18 триггеры, с первого по четвертый элементы И 19 - 22, с первого по девятый элементы ИЛИ 23 - 31, первый 32 и второй 33 блоки памяти, блок 34 управления, с первого по девятнадцатый здыходы 35 - 53-блока управления, вход 54 признака режима блока управления, вход 55 за- пуска устройства и вход 56 останова блока управления.

Блок 34 управления содержит два регистра 57 и 58, выход (разряды) 59 адресного поля регистра 58, две груп- пы 60 и 61 элементов И, группу 62 элементов ИЛИ, счетчик 63, два депмф- ратора 64 и 65, узел 66 памяти, адресное поле 67 узла 66 памяти, генератор 68 импульсов, триггер 69 и эле- мент И 70.

Расширенное декартово произведение п отношений задается формулой

D, ® D2® ,... , ® 0„ t(d,d...d)

: D, Л . ..AdjE Dp ,

где d,,d,...,dn - строки - кортежи

отношений.

В блоке 32 памяти заранее записаны адреса отношений, которые необхо- . димо перемножить, в блоке 3 памяти записаны элементы каждого отношения.

По импульсу на входе 55 устройства счетчики 9 и 10 устанавливаются- в нулевое состояние, обнуляется триггер 69 и запускается генератор 68 импульсов (с определенной задержкой) . Адрес первой микрокоманды из

0 5 О

д

5

0

5

регистра 57 проходит на входы дешифратора 64, в результате чего из узла 66 памяти на регистр 58 считывается первая микрокоманда, которая содержит код микрооперации и адрес следующей микрокомандь: (разряды 59). Дешифратор 65 дешифрирует первую микрокоманду и выдает сигнал на выходе 35 блока 34 управления. Этот сигнал через элементы ИЛИ 26 и 28 и триггеры 17 и 18 поступает на коммутаторы 14 и I5 и приводит к коммутации их первых входов, в результате чего содержимое счетчиков 9 и 10 увеличивается на единицу и из блока 32 памяти считывается адрес первого отношения (в одной ячейке памяти хранится только один адрес отношения).

Адрес следующей микрокоманды с разрядов 59 регистра 58 заносится в счетчик 63. По первому импульсу с выхода генератора 68 открывается группа 60 элементов И и адрес второй микрокоманды поступает на входы дешифратора 64. При этом на регистр 58 из узла 66 памяти считывается код второй микрокоманды, в результате чего появляется сигнал на выходе 36 блока управления. По этому сигналу, если , дешифратор 12 сигнала не выдает, открывается группа 19 элементов И и адрес первого отношения записывается в счетчик 1. Каждая ячейка блока 3 памяти соответствует строке - кортежу отношения. Содержимое ячейки памяти указанного адреса записывается в регистр 5. По следующему импульсу с выхода генератора 68 появляется сигнал на выходе 37 блока 34 управления. По этому сигналу через элемент ИЛИ 29 подается сигнал разрешения на дешифратор 13, который разрешает первой строке - кортежа первого отношения из регистра 5 через выбранную группу 7 элементов И поступить в регистр 8. По следуищему импульсу гене-- ратора 68 появляется сигнал на выходе 35 блока 34, по которому из блока 32 памяти считывается адрес второго отношения и в дальнейшем устройство работает аналогично до тех пор, пока с дешифратора 12 на появится сигнал, который означает, что с блока 32 памяти считан определенный код свидетельствующий о том, что адреса первых строк - кортежей всех- отношений считаны. По сигналу на выходе 36 блока 34 управления открываются элементы И 20 и 22, в результате чего содержимое счетчиков 9 и 10 уменьшается на единицу, а адрес следующей микрокоманды увеличивается на единицу сигналом с выхода элемента И 20 через элемент ИЛИ 31. В этом случае на регистр 58 .из узла 66 памяти считывается микрокоманда, выдающая сигнал на выходе 40 блока ЗА управления, по которому с регистра 8 на выходе 71 устройства может быть считана первая строка произведения Dj@ D ®... D, а также анализируется последний служебный разряд 6 регистра 5 и, если он равен единице (последняя строка - кортеж отношения D,) адрес следующей микрокомандьг увеличивается на единицу сигналом с выхода элемента И 2 через элемент ИЛИ 31, а если равен нулю, то выполняется следующая микрокоманда, по которой выдается сигнал с выхода 38 блока 34 управления. По этому, сигналу содержимое счетчика 1 увеличивается на единицу (теперь он содержит адрес второй строки - кортежа отношения D) и из блока 3 памяти в регистр 5 принимается вторая строка - кортеж отношения Df,. Затем снова считывается очередная микрокоманда, выдающая сигнал на выходе 39 блока 34 управления, вследствие чего в регистр В записывается вторая строка - кортеж отношения D,. По следунядей микрокоманде с выхода 40 блока 34 управления поступает сигнал, по которому с регистра 8 на выходе устройства может быть считана вторая строка произведения

D ® Dj ® . . .

D. В том случае, если

последний служебный разряд 6 регистра 5 равен единице, то появляется сигнал с выхода элемента И 21 через элемент ИЛИ 31 и адрес следующей микрокоманды увеличивается на единицу. При этом из регистра 58 считывается микрокоманда, по которой появляется сигнал с выхода 41 блока 34 управления. По этому сигналу узел 16 сравнения сравнивает содержимое счетчиков 9 и 10, и если они равны (т.е. необходимо изменить строку - кортеж пре дьщущего отношения, адрес которого хранится в счетчике 9), то с зыхода узла 16 через элемент ИЛИ 31 сигнал поступает на счетчик 63 и адрес сле- дующей микрокоманды увеличивается на единицу. По этой микрокоманде появляется сигнал на выходе 42 блока 34,

0

0

управления по которому содержимое счетчиков 9 и 10 уменьшается на единицу и с блока 32 памяти считывается адрес предыдущего отношения (Dn-i)- По следующей микрокоманде выдается сигнал с выхода 43 блока 34 управления, по которому открывается группа 19 элементов И и ацрес отношения (если это не Определенный код, указывающий на окончание поля адресов отношения) поступает на счетчик 1. Далее следуют микрокоманды, по которым поступают сигналы: с выхода 44 блока 34

5 управления, по которому содержимое счетчика 1 уменьшается на единицу (т.е. формируется адрес второй строки - кортежа множества), с вьтхода 45 блока 34 управления, по которому происходит запись содержимого счетчика 1 в блок 33 памяти и .вторая строка - кортеж множества переписывается из регистра 5 в регистр 8 по адресу, сформированному дешифратором 13, с

5 выхода 46 блока 34 управления, по которому триггер 17 устанавливае Уся в нулевое состояние, коммутатор 14 коммутирует нижние входы, содержимое счетчика 10 увеличивается на единицу

0 и из блока 32 памяти считывается ад- рее следующего отношения. По следующей микрокоманде появляется сигнал с выхода 47 блока 34 управления, по которому открывается группа элементов И 19 и адрес отношения записывается в счетчик 1, если с дешифратора нет запрещающего сигнала. По следующему сигналу с выхо да 48 блока 34 управления происходит запись адреса отношения в блок 33 памяти по адресу, определенному счетчиком 10, и с регистра 5 строка - кортеж данного множества записывается в разряды регистра 8, указанные дешифратором 13. Следукяцая микрокоманда формирует сигнал с выхода 46 блока 34 и в дальнейшем устрой ство работает аналогичным образом по циклу сигналов с выходов 46 - 48 бло- ка 34 до тех пор, пока не перепишутся адреса отношения в блок 33 памяти, а их первые строки - кортежи - в регистр 8 и на выходе не появится уникальный код, по которому сработает дешифратор 12. Тогда по сигналу с выхода 47 блока 34 открывается группа элементов И 20, в результате чего содержимое счетчика 10 уменьшается на единицу, сигнал с выхода элемента И 20 через элемент ИЛИ 31 nocTyna&f

5

0

5

0

5

на счетчик 63 и адрес микрокоманды увеличивается на единицу. По этой микрокоманде поступает сигнал с выхода 40 блока 34 управления и далее устройство работает аналогично вьшхеописанной последовательности сигналов с выходов 38 - До блока 34 управления.

Если по сигналу с выхода 41 блока 34 управления с узла сигнал.не поступает.

16 сравнения то выполняется

следующая микрокоманда, по которой появляется сигнал с выхода А9 блока 34 управления. По этому сигналу триг геры 17 и 18 устанавливаются в нулевое состояние и коммутаторы 14 и 15 коммутируют вторые входы, содержимое счетчика 10 уменьшается на единицу и из блока 33 памяти считывается адрес строки предыд тцего отношения. По следующей микрокоманде появляется сигнал с выхода 50 блока 34 управления и адрес строки - кортежа отношения поступает на счетчик 1, а на регистр 5 - содержимое этой строки. После этого считывается следующая микрокоманда, которая формирует сигнал на выходе 51 блока 34 управления который поступает через элемент ИЛИ 30 на вход элемента И 21, а если в регистре 5 записана последняя строка отношения, то со служебного разряда 6 поступает сигнал на второй вход элемента И 21, в результате чего он открывается. Через элемент ИЛИ 31 сигнал поступает на счетчик 63 и адрес следующей микрокоманды увеличивается на единицу. По этой микрокоманде появляется сигнал с выхода 41 блока 34 управления и далее устройство ра ботает (как описано выше) по появлению этого сигнала.

Если при наличии сигнала на выходе 51 блока 34 управления в регистре 5 записана не последняя строка отношения, то на контрольном разряде будет О. В этом случае счетчик 63 указывает адрес следующей микрокоманды, по которой появляется сигнал на выходе 52 блока 34 управления. По . этому сигналу содержимое счетчика 1 увеличивается на единицу. Следующая микрокоманда формирует сигнал на выходе 53 блока 34 управления, по кот о рому содержимое счетчика 1 записывается в .блок 33 памяти и из регистра содержимое строки - кортежа переписывается через соответствующий элемен

15 зультате 09676

И группы 7, выбранный дешифратором, в регистр 8. По следующей микрокоманде появляется сигнал на выходе 46 блока 34 управления и далее устройство работает аналогично вьппеописанному режиму последовательности сигналов с выходов 46 - 48 блока 34 управления.

Устройство прекращает работу, ког- 10 да с выхода дешифратора П появится сигнал, т.е. содержимое счетчика 9 будет равно нулю, и следугопшм импульсом генератора 68 триггер 69 установится в единичное состояние, в речего генератор 68 прекратит

работу. Формула

зультате

изобретения

зультате

Устройство умножения реляционных отношений, содержащее первый и второй регистры, первый 6jiOK памяти, первый дешифратор, первый счетчик, блок управления и группу из р элементов И, где р - разрядность реляционного отношения, причем выход первого счетчика подключен к входу первого дешифратора, выход которого подключен к адресному входу первого блока памяти, выход которого подключен к информационному входу первого регистра, выходы которого с первого по р-й подключены соответственно к первым входам элементов И с первого по р-й группы, выходы которых подключены соответственно к информационным входам с первого по р-й второго регистра, выход которого подключен к информационному выходу устройства, отличающееся тем, что, с целью расширения области применения за счет выполнения п операций реляционного умножения, где п 2, оно содержит второй и третий счетчики, второй и тре- тий блоки памяти, первый и второй коммутаторы, второй, третий и четвертый дешифраторы, узел сравнения, первый и второй триггеры, четыре элемента И и девять элементов ИЛИ, причем вход запуска устройства подключен к входу запуска блока управления, первый выход которого подключен к суммирующему входу второго счетчика, к первым входам первого, второго и третьего элементов ИЛИ, выходы которых подключены соответственно к суммирую щему входу третьего счетчика, единичному входу первого триггера и к единичному входу второго триггера, вто

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

8

5

0

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

5 элемента ИЛИ, выход Которого подключен к вычитающему входу третьего счетчика, выход которого подключен к вторым информационным входам первого коммутатора и узла сравнения, выход второго блока памяти подключен к вто- рому информационному входу второго коммутатора, (р + 1)-й выход первого регистра подключен к первому входу четвертого элемента И, выход которого подключен к третьему входу четвертого элемента ИЛИ, инверсный выход первого триггера, прямой выход второго триггера и инверсный выход второго триггера подключены соответственно к второму управлягацему входу первого коммутатора, к первому управляющему и к второму управляющему входам второго коммутатора, девятнадцатый выход блока управления подключен к

5 второму входу восьмого элемента ИЛИ, выход которого подключен к второму входу четвертого элемента И, выход второго дешифратора подключен к входу останова блока управления.

0

5

0

Изобретение относится к вычислительной технике и может быть использовано в системах управления реляционными базами данных. Цель изобретения расширение области применения за счет выполнения операции умножения реляционной алгебры п отношений. Поставленная цель достигается тем, что устройство содержит первый счетчик 1, первый дешифратор 2, первый блок 3 памяти, служебный разряд 4 блока. 3 памяти, первый -регистр 5, служебньм разряд 6 регистра 5, вруп- пу 7 из р элементов И, где р- разрядность реляционного отношения, второй регистр 8, второй и третий счетчики 9 и 10, со второго по четвертый дешифраторы 11-13, первый и второй коммутаторы 4 и 15, узел 16 сравнения, первый и второй триггеры 17 и 18, с первого по четвертый элементы И 19- 22, с первого по девятый элементы ИЛИ 28-31, первый и Второй блоки 32 и 33 памяти, блок 34 управления. 2 ил. i (Л