Устройство умножения реляционных отношений

 

Изобретение относится к вычислительной технике и может быть использовано в системах управления реляционными базами данных. Цель изобретения расширение области применения за счет выполнения операции умножения реляционной алгебры п отношений. Поставленная цель достигается тем, что устройство содержит первый счетчик 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 (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (51)4 Г 06 Р 15/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ /

М АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕНКЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4191977/24-24 (22) 04.02.87 (46) 15.10.88. Бюл. У 38 (72) А.А.Баранник, Н.А.Киселевский, В.Т.Лобко, Д.И.Поливанов, И.N.Фоменко и В.П.Ткачев (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 7800 11, кл, С 06 F 15/38, 1978.

-Авторское свидетельство СССР

Р 1129623, кл. С 06 Р 15/38, 1984. (54) УСТРОЙСТВО УИНОЖЕНИЯ РЕЛЯЦИОНHbK ОТНОШЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в системах управления реляционными базами данных; Дель изобретения — расширение области применения за счет выполнения операции умножения реляционной алгебры и отношений.

Поставленная цель достигается тем, что устройство содержит первый счетчик 1, первый дешифратор 2, первый блок 3 памяти, служебный разряд 4 блок а 3 памяти, первый регистр 5, служебный разряд 6 регистра 5, вруппу 7 иэ р элементов И, где р- разрядность реляционного отношения, второй регистр 8, второй и третий счетчики

9 и 10. со второго ro четвертый дешифраторы 11-13, первый и второй коммутаторы !4 и 15, узел 16 сравнения, первый и второй триггеры 17 и 18, с первого по четвертый элементы И 19а

22, с первого по девятый элементы 6

ИЛИ 28-31, первый и второй блоки 32 и 33 памяти, блок 34 управления.

2 ил.

143096 7

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

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

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

Устройство содержит первый счетчик 1, первый дешифратор 2, первый блок 3 памяти, служебный разряд 4 блока 3 памяти, первый регистр 5, служебный разряд 6 регистра 5, группу 7 из р элементов И, второй регистр 8, второй 9 и третий 10 счетчики, второй 11, третий 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, узел бб памяти, адресное поле 67 узла 66 памяти, генератор 68 импульсов, триггер 69 и элемент И 70, Расширенное декартово произведение п отношений задается формулой

1® 2® ®

: d E D, h dye D h...hd, D„3, где с1,й,...,d h - строки — кортежи отношений.

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

IIo импульсу на входе 55 устройст-. ва счетчики 9 и 10 устанавливаются. в нулевое состояние, обнуляется триггер 69 и запускается генератор

68 импульсов (с определенной задержкой). Адрес первой микрокоманды из

55 регистра 57 проходит на входы дешифратора 64, в результате чего из узла

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

17 и 18 поступает на коммутаторы 14 и 15 и приводит к коммутации их первых входов, в результате чего содержимое счетчиков 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 управления открываются элеменуправления по которому содержимое счетчиков 9 и 10 уменьшается на единицу и с блока 32 памяти считывается адрес предыдущего отношения (D „, ), По следующей микрокоманде выдается сигнал с выхода 43 блока 34 управления, по которому открываЕтся группа

19 элементов И и ацрес отношения (если это не определенный код, указывающий на окончание поля адресов отношения) поступает на счетчик 1. Далее следуют микрокоманды, по которым поступают сигналы: с выхода 44 блока 34 управления, по которому содержимое счетчика 1 уменьшается на единицу (т.е. формируется appc.- второй строки — кортежа множества), с выхода 45 блока 34 управления, по которому происходит запись содержимого счетчика

1 в блок 33 памяти и вторая строка— кортеж множества переписывается из регистра 5 в регистр 8 по адресу, сформированному дешифратором 13, с выхода 46 блока 34 управления, по которому триггер 17 устанавливаешься в нулевое состояние, коммутатор 14 коммутирует нижние входы, содержимое счетчика 10 увеличивается на единицу и из блока 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 поступает

40 з 143096 ты И 20 и 22, в результате чето содержимое счетчиков 9 и 10 уменьшается на единицу, а адрес следующей микрокоманды увеличивается на единицу с сигналом с выхода элемента И 20 через элемент ИЛИ 31. В этом случае на регистр 58 из узла 66 памяти считывается микрокоманда, выдающая сигнал на выходе 40 блока 34 управления, по которому с регистра 8 на выходе 71 устройства может быть считана первая строка произведения D(O D ®... 0 и а также анализируется пбследний служебный разряд 6 регистра 5 и, если 1 он равен единице (последняя строка— кортеж отношения D„), адрес следующей микрокоманды увеличивается на единицу сигналом с выхода элемента

И 21 через элемент ИЛИ 31, а если ра- 20 вен нулю, то выполняется следующая микрокоманда, по которой выдается сигнал с выхода 38 блока 34 управления. По этому. сигналу содержимое счетчика l увеличивается на единицу 25 (теперь он содержит адрес второй строки — кортежа отношения D ) и из

tl блока 3 памяти в регистр 5 принимается вторая строка — кортеж отношения

D Затем снова считывается очеред-. 30 ная микрокоманда, выдающая сигнал на выходе 39 блока 34 управления, вследствие чего в регистр 8 записывается вторая строка — кортеж отношения D„.

По следующей микрокоманде с выхода

40 блока 34 управления поступает сигнал, по которому с регистра 8 на выхбде устройства может быть считана вторая строка произведения

П Ю D> З ... 0„. В том случае, если последний служебный разряд 6 регистра 5 равен единице, то появляется сигнал с выхода элемента И 21 через элемент ИЛИ 31 и адрес следующей микрокоманды увеличивается на единицу. 45

При этом из регистра 58 считывается микрокоманда, по которой появляется сигнал с выхода 41 блока 34 управления. По этому сигналу узел 16 сравнения сравнивает содержимое счетчиков

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

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

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

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

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

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

Если по сигналу с выхода 41 блока

34 управления с узла 16 сравнения сигнал,не поступает, то выполняется следующая микрокоманда, по которой появляется сигнал с выхода 49 блока

34 управления. По этому сигналу триг- 15 геры 17 и 18 устанавливаются в нулевое состояние и коммутаторы 14 и 15 коммутируют вторые входы, содержимое счетчика IO уменьшается на единицу и из блока 33 памяти считывается ад- 2р рес строки предыдущего отношения. По следующей микрокоманде появляется сигнал с выхода 50 блока 34 управления и адрес строки " кортежа отношения поступает на счетчик 1, а на ре- 25 с гистр 5 — содержимое этой строки.

После этого считывается следующая микрокоманда, которая формирует сигнал на выходе 51 блока 34 управления, который поступает через элемент ИЛИ 3п

30 на вход элемента И 21 а если в регистре 5 записана последняя строка отношения, то со служебного разряда б поступает сигнал на второй вход элемента И 21, в результате чего он открывается. Через элемент ИЛИ 31 сигнал поступает на счетчик 63 и адрес следующей микрокоманды увеличивается на единицу. По этой микрокоманде появляется сигнал с выхода 41 4О блока 34 управления и далее устройство работает (как описано выше) по появлению этого сигнала, Если при наличии сигнала на выходе 51 блока 34 управления в регистре

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

14309 рой, третий, четвертый и пятый выходы блока управления соединены с первыми входами первого и второго элементов И, выход второго счетчика подключен к входу второго дешифратора и к первому информационному входу первого коммутатора, выход которого подключен к адресным входам второго и третьего блоков памяти, к первому 10 информационному входу узла сравнения и к информационному входу третьего дешифратора, выходы с первого по р-й которого подключены соответственно к вторым входам элементов И с первого 15 по р-й группы, выход первого счетчика подключен к информационному входу третьего блока памяти, выход которого подключен к первому информационному входу второго коммутатора, выход 20 которого подключен к второму входу первого элемента И и к входу четвертого дешифратора, выход которого подключен к третьему входу первого элемента И и к второму входу второго 25 элемента И, выход которого подключен к первым входам четвертого и пятого элементов ИЛИ и к первому входу третьего элемента И, выход которого подключен к первому входу шестого эле- 30

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

ro счетчика, информационный вход которого подключен к выходу первого элемента И, одиннадцатый выход блока управления подключен к первому входу восьмого элемента ИЛИ и к входу считывания второго регистра, двенадцатый выход блока управления подключен к стробирующему входу узла сравнения, выход которого подключен к второму входу четвертого элемента ИЛИ, 67 выход которого подключен к входу признака режима блока управления, тринадцатый выход которого подключен к вторым входам второго и третьего элементов ИЛИ, и к второму входу шестого элемента ИЛИ, четырнадцатый, пятнадцатый и шестнадцатый выходы блока управления подключены к второму входу седьмого элемента ИЛИ и к входу записи третьего блока памяти, семнадцатый выход блока управления подключен к второму входу первого элемента ИЛИ и к первому входу девятого элемента ИЛИ, выход которого подключен к входу установки в 0" первого триггера, прямой выход которого подключен к второму входу третьего элемента И и к первому управляющему входу первого коммутатора, восемнадцатый выход блока управления подключен к входу установки в "0" второго триггера, к второму входу девятого элемента ИЛИ и к второму входу пятого элемента ИЛИ, выход которого подключен к вычитающему входу третьего счетчика, выход которого подключен к вторым информационным входам первого коммутатора и узла сравнения, выход второго блока памяти подключен к второму информационному входу второго коммутатора, (р + 1)-й выход первого регистра подключен к первому входу четвертого элемента И, выход которого подключен к третьему входу четвертого элемента ИЛИ, инверсный выход первого триггера, прямой выход второго триггера и инверсный выход второго триггера подключены соответственно к второму управляющему входу первого коммутатора, к первому управляющему и к второму управляющему входам второго коммутатора, девятнадцатый выход блока управления подключен к второму входу восьмого элемента ИЛИ, выход котороrо подключен к второму входу четвертого элемента И, выход второго дешифратора подключен к входу останова блока управления, !

4309б7

Редактор А.Ренин

Заказ 5344/5!

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

Ь

Ъс

М

ФЬ

Ф

Мь а

3 Ф

4в

%ф

Cty п

4b

Ю

Составитель В.Смирнов

Техред Л.Сердюкова Корректор Э. Лончакова

Тираж 704 Подписное

В!!ИИПИ Государственного комитета СССР по делам изобретений и открытий!

13035, Москва, Ж-35, Раушская наб., д, 4/5