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

.,ЯО 14 ЗО 9 1) 4 Г 06 Р 15/38 БРЕТЕНИ ПИСАНИЕ МУ СВИДЕТЕГ селевскии, И,М.ФоменСУДАРСТВЕНКЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ(56) Авторское свидетельство СССР 11 р 7800 11, кл, С 06 Р 15/38, 1978..Авторское свидетельство СССР У 1129623, кл. С 06 Р 15/38, 198 (54) УСТРОЙСТВО УИНОЖЕНИЯ РЕЛЯЦИОННЫХ ОТНОШЕНИЙ(57) Изобретение относится к вычисли тельной технике и может быть использовано в системах управления реляционными базами данных; Дель изобретения - расширение области применения за счет выполнения операции умножения реляционной алгебры и отношений.Поставленная цель достигается тем,что устройство содержит первый счетчик 1, первый дешифратор 2, первыйблок 3 памяти, служебный разряд 4блока 3 памяти, первый регистр 5,служебный разряд 6 регистра 5, вруппу 7 иэ р элементов И, где р- разрядность реляционного отношения, второйрегистр 8, второй и третий счетчики9 и 10. со второго по четвертый деши 4 раторы 11-13, первый и второй коммутаторы 14 и 15, узел 16 сравнения,первый и второй триггеры 17 и 18, спервого по четвертый элементы И 19 а22, с первого по девятый элементы Йили 28-31, первый и второй блоки 32 вкви 33 памяти, блок 34 управления,2 ил. С:Изобретение относится к вычислительной технике и может быть использовано в системах управления реляционными базами данных,Цель изобретения - расширение области применения устройства за счетвыполнения и операций реляционногоумножения, где и ) 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,Расширенное декартово произведение и отношений задается формулой где с 11, Й д и - строки - кортежиотношений.В блоке 32 памяти заранее записаны адреса отношений, которые необходимо перемножить, в блоке 3 памяти записаны элементы каждого отношения.По импульсу на входе 55 устройст-. ва счетчики 9 и 1 О устанавливаются в нулевое состояние, обнуляется триггер 69 и запускается генератор 68 импульсов (с определенной задержкой). Адрес первой микрокоманды из 5 10 15 20 25 30 35 40 45 50 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 памяти считывается адрес предыдущего отношения (Э , ), 11 о следующей микрокоманде выдается сигнал с выхода 43 блока 34 управления, по которому открываЕтся группа 19 элементов И и ацрес отношения (если это не определенный код, указывающий на окончание поля адресов отношения) поступает на счетчик 1. Далее следуют микрокоманды, по которым поступают сигналы: с выхода 44 блока 34 управления, по которому содержимое счетчика 1 уменьшается на единицу (т.е. формируется адре.; второй строки - кортежа множества), с выхода 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 устройства может быть считана первая строка произведения В, О+ 00, а также анализируется последний служебный разряд 6 регистра 5 и, если 16 он равен единице (последняя строка - кортеж отношения Р), адрес следующей микрокоманды увеличивается на единицу сигналом с выхода элемента И 21 через элемент ИЛИ 31, а если ра вен нулю, то выполняется следующая микрокоманда, по которой выдается сигнал с выхода 38 блока 34 управления, По этому. сигналу содержимое счетчика 1 увеличивается на единицу 25 (теперь он содержит адрес второй строки - кортежа отношения В ) и изо блока 3 памяти в регистр 5 принимается вторая строка - кортеж отношения В, Затем снова считывается очеред-. Э 0 ная микрокоманда, выдающая сигнал на выходе 39 блока 34 управления, вследствие чего в регистр 8 записывается вторая строка - кортеж отношения П. По следующей микрокоманде с выхода 40 блока 34 управления поступает сигнал, по которому с регистра 8 на выходе устройства может быть считана вторая строка произведения П (Р Э 31). В том случае, если последний служебный разряд 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 управления,Устройство прекращает работу, когда с выхода дешифратора 11 появится сигнал, т.е. содержимое счетчика 9 будет равно нулю, и следующим импульсом генератора 68 триггер 69 установится и единичное состояние, в результате чего генератор 68 прекратит работу. Формула изобретения Устройство умножения реляционных отношений, содержащее первый и второй регистры, первый блок памяти, первый дешифратор, первый счетчик, блок управления и группу из р элементов И, где р - разрядность реляционного отношения, причем выход первого счетчика подключен к входу первого дешифратора, выход которого подключен к адресному входу первого блока памяти, выход которого подключен к информационному входу первого регистра, выходы которого с первого по р-й подключены соответственно к первым входам элементов И с первого по р-й группы, выходы которых подключены соответственно к информационным входам с первого по р-й второго регистра, выход которого подключен к информационному выходу устройства, о т л ич а ю щ е е с я тем, что, с целью расширения области применения за счет выполнения и операций реляционного умножения, где и 7 2, оно содержит второй и третий счетчики, второй и третий блоки памяти, первый и второй коммутаторы, второй, третий и четвертый дешифраторы, узел сравнения, первый и второй триггеры, четыре элемента И и девять элементов ИЛИ, причем вход запуска устройства подключен к входу запуска блока управления, первый выход которого подключен к суммирующему входу второго счетчика, к первым входам первого, второго и третьего элементов ИЛИ, выходы которых подключены соответственно к суммирующему входу третьего счетчика, единич" ному входу первого триггера и к единичному входу второго триггера, вто 50 5 143096на счетчик 63 и адрес микрокомандыувеличивается на единицу, По этоймикрокоманде поступает сигналс выхода 40 блока 34 управления и далее устройство работает аналогичновышеописанной последовательности сигналов с выходов 38 - 40 блока 34 управления.Если по сигналу с выхода 41 блока34 управления с узла 16 сравнениясигнал,не поступает, то выполняетсяследующая микрокоманда, по которойпоявляется сигнал с выхода 49 блока34 управления. По этому сигналу триггеры 17 и 18 устанавливаются в нулевое состояние и коммутаторы 14 и 15коммутируют вторые входы, содержимоесчетчика 10 уменьшается на единицуи из блока 33 памяти считывается адрес строки предыдущего отношения, Последующей микрокоманде появляетсясигнал с выхода 50 блока 34 управления и адрес строки " кортежа отношения поступает на счетчик 1, а на ресгистр 5 - содержимое этой строки.После этого считывается следующаямикрокоманда, которая формирует сигнал на выходе 51 блока 34 управления,который поступает через элемент ИЛИ ЗО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 элемента И, выход которого подключен к первым входам четвертого и пятого элементов ИЛИ и к первому входу третьего элемента И, выход которого подключен к первому входу шестого элеЪ мента ИЛИ, выход которого подключен к вычитающему входу второго счетчика, шестой и седьмой выходы блока управления подключены к первому входу седь. мого элемента ИЛИ, выход которого подключен к входу синхронизации третьего дешифратора, восьмой, девятый и десятый выходы блока управления объединены с помощью монтажного ИЛИ и подключены к счетному входу перво- д 0 го счетчика, информационный вход которого подключен к выходу первого элемента И, одиннадцатый выход блока управления подключен к первому входу восьмого элемента ИЛИ и к входу счи тывания второго регистра, двенадцатый выход блока управления подключен к стробирующему входу узла сравнения, выход которого подключен к второму входу четвертого элемента ИЛИ,67выход которого подключен к входу признака режима блока управления, тринадцатый выход которого подключен квторым входам второго и третьегоэлементов ИЛИ, и к второму входу шестого элемента ИЛИ, четырнадцатый,пятнадцатый и шестнадцатый выходыблока управления подключены к второму входу седьмого элемента ИЛИ и квходу записи третьего блока памяти,семнадцатый выход блока управленияподключен к второму входу первогоэлемента ИЛИ и к первому входу девятого элемента ИЛИ, выход которогоподключен к входу установки в "0" первого триггера, прямой выход которогоподключен к второму входу третьегоэлемента И и к первому управляющемувходу первого коммутатора, восемнадцатый выход блока управления подключен к входу установки в "0" второготриггера, к второму входу девятогоэлемента ИЛИ и к второму входу пятогоэлемента ИЛИ, выход которого подключен к вычитающему входу третьего счетчика, выход которого подключен к вторым информационным входам первогокоммутатора и узла сравнения, выходвторого блока памяти подключен к второму информационному входу второгокоммутатора, (р + 1)-й выход первогорегистра подключен к первому входучетвертого элемента И, выход которого подключен к третьему входу четвертого элемента ИЛИ, инверсный выходпервого триггера, прямой выход второго триггера и инверсный выход второго триггера подключены соответственно к второму управляющему входу первого коммутатора, к первому управляющему и к второму управляющему входамвторого коммутатора, девятнадцатыйвыход блока управления подключен квторому входу восьмого элемента ИЛИ,выход которого подключен к второмувходу четвертого элемента И, выходвторого дешифратора подключен к входу останова блока управления,-35, Рауш а венно-полиграфическое предприятие, г. Ужгород, ул оектная,оиз Тир ВНИИПИ Гос по делам 13035, Москв