Вычислительное устройство

 

Изобретение относится к вычислительной технике и может быть использовано в системах управления реляционными базами данных. Цель изобретения - расширение функциональных возможностей за счет реализации операции проекции реляционной алгебры. Для достижения указанной цели в устройство дополнительно введены регистр 1 сдвига, элемент НЕ 3, элементы ИЛИ 4 - 6, дешифратор 9, блок 12 памяти, счетчики 14 и 15, блок 16 сравнения и блок 17 управления. Введение указанных элементов позволяет реализовать указанные преимущества. 6 ил.

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

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

РЕСПУБЛИН (19) (11) (5y)5 G 06 F 15/38

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

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ HOMHTET

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4430504/24-24 (22) 26.05.86 (46) 23.03.90. Бюл. (72) А.А. Баранник, Н,А. Киселевский и В.Т. Лобко (53) 681.325(088.8) (56) Авторское свидетельство СССР

М - 631931,, кл. G 06 F 15/38, 1977.

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

11 780011, кл. G 06 F 15/38, 1978. (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО (57) Изобретение относится к вычисли2 тельной технике и, мо кет быть использовано в системах управления реляционными базами данных ° Цель изобретения— ,расширение функциональных возможнос:eA за счет реализации операции проекции реляционной алгебры. Для дости.лсения указанной цели в устройство дополнительно введены регистр 1 сдвига, элемент КЕ 3, элементы ИЛИ 4-6, дешифратор 9, блок 12 памяти, счетчики 14 и 15, блок 16 сравнения и блок 17 управления. Введение указанных элементов позволяет реализовать указанные преимущества. 6 ил .

1552202

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

Цель изобретения — расширение функциональных возможностей за счет реализации операции проекции реля1 и онной алгебры, На фиг. 1 представлена структур- !О ная схема устройства; на фиг. 2— схема блока управления; на фиг. 3 схема регистра сдвига; на фиг. 4 временные диаграммы работы устройства, на фиг. 5 — временные диаграммы рабо- !5 ты блока управления, на фиг. 6 — временные диаграммы работы регистра сдвига, Устройство содержит регистр 1 сдвига, группу 2 элементов ИЛИ эле9 20 мент НЕ 3, элементы ИЛИ 4-6, группы

7 и 8 элементов И, дешифратор 9, блок 10 памяти, дополнительный банк

11 блока 10 памяти, блок 12 памяти, счетчики 13-15, блок 16 сравнения, . 25 блок 17 управления, выходы 18-25 блока 17 управления, управляющие входы 26-28 блока 17 управления, информационные входы 29 и 30 устройства, вход 31 запуска, вход 32 начального адреса микропрограмм, информационный

30 вход 33 регистра 1 сдвига, управляющие входы 34-36 регистра 1 сдвига, выход 37 регистра 1 сдвига, информационный выход 38.

Блок 17 управления (микропро- .. 35 граммного типа) содержит регистры 39 и 40, причем вторая группа разрядов регистра 40 обозначена позицией 4 1, счетчик 42, дешифратор 43, группы

44. и 45 элементов И, группу 46 эле- 40 ментов ИЛИ, блок 47 памяти, вторая группа разрядов которого обозначена позицией 48, генератор 49 импульсов, элементы ИЛИ 50 и 51, элемент И 52, триггер 53 и элементы 54 и 55 задержки. б !

Регистр 1 сцвига содержит группу

D-триггеров 56, группу элементов

2И-ИЛИ 57 и группу элементов И 58.

Yа фиг. 4 обозначены: а — адрес первого кортежа отношения, поступающего на вход 29 устройства б — сигнал на входе 31 запуска устройства, в изменение информации на адресной шине блока 10 памяти, г — изменение инфор"

55 мации на выходе регистра 1 сдвига; д,е. — сигналы на входах 35 и 36 соответственно р егистра 1 сдвига, ж,з,и, к,л,м,н,о — сигналы на выходах 18-25 блока 17 управления соответственно1 п,р — сигналы на входах 27 и 28 бло- ка 17 управления соответственно; с,т — изменение информации на выходах счетчиков 14 и 15 соответственно, у — изменение информации на выходе блока 12 памяти, ф — информация на выходе 38 устройства ЗП вЂ” блок 12 памяти находится в режиме записи.

На фиг. 5 обозначены: а - сигнал на входе 31 запуска устройства, б— сигнал на выходе генератора 49 импульсов; в . — сигнал на выходе триггера 53 г - изменение информации на адресной шине блока 47 памяти, д— изменение информации на выходе ре-! гистра 40, е — изменение информации на выходе счетчика 42; ж,з,и,к,л,м, н,о — сигналы.на выходах 18-25 блока

17 управления соответственно, и— сигнал на входе 28 блока 17 управления, р — сигнал на входе 27 блока

17 управления ", с — сигнал на последнем выходе дешифратора 43 блока 17 управления. На временных диаграммах представлены два фрагмента работы блока 17 управления. Первый фрагмент поясняет работу блока при появлении сигнала на его входах 27 и 28 . Второй фрагмент поясняет окончание работы блока 17 управления.

На фиг. 6:представлены временные диаграммы изменения состояния регистра 1 сдвига, его входных и выходных сигналов в момент появления сигнала на выходе 19 блока 17 управления (сигнала, переводящего регистр 1 в режим сдвига), где: a,б — сигналы на выходах 18 и 19 блока 17 управления соответственно; в, г — сигналы на входах 35 и 36 регистры 1 сдвига соответственно, д,е,ж,з,и,к,л,м - информация на входе 34 регистра 1 сдвига, . н,о,п,р,с,т,у,ф вЂ,изменение информа-i . ции на выхода 37 регистра 1 сдвига.

На диаграммах д и н позиции соответ-. ствуют младшему разряду входа 34 регистра 1 сдвига и младшему разряду выхода 37 соответственно.

По определению проекции отношения

R на список атрибутов А определяется по формуле

R (А)= (г (А):г б Rf где r — строка-кортеж отношения R.

1 1

Операция проекции предусматривает исключение из отношения части атрибу1552 тов, кроме А, а если в оставшейся части отношения существуют повторяющиеся строки-кортежи, то из них оставляют по единственному представителю.

Устройство работает следуюшим образом.

При включении питания счетчика 14 и 15 регистр и 40 обнуляются, а генера- тор 49 импульсов устанавливается в 10 запертое состояние-(не показано) .

Каждая ячейка блока 10 памяти соответствует строке-кортежу отношения.

Один разряд входов 29 и 32 является атробом записи в счетчик 13 и ре- 16 гистр 39 соответственно. Адрес первой строки-кортежа с входа 29 устройства записывается в счетчик 13, на выходе блока 10 памяти появляется содержимое первой строки-кортежа. На вход 30 устройства поступает код проекции, указывающий на атрибут, который необходимо исключить из строкикортежа. Адрес первой микрокоманды с входа 32 записывается" в регистр 39 26 блока 17 управления.

По импульсу на входе 31 устройства запускается генератор 49 импульсов (с определенной задержкой), сигнал, поступающий с выхода элемента З0

ИЛИ 5 на счетный вход +1 счетчика

14, увеличивает его содержимое на 1, сигнал с выхода элемента ИЛИ 6 разрешает запись информации с выхода счетчика 14 в счетчик 15, Одновременно с этим обнуляется триггер 53 и адрес

ЗБ первой микрокоманды из регистра 39 проходит на адресный вход блока 47 памяти. По сигналу управления с выхода элемента 54 задержки на регистр

40 считывается первая микрокоманда, которая содержит код микрооперации и адрес следующей микрокоманды (разряды 41). Первая микрокоманда расшиф-, ровывается дешифратором 43, который выдает сигнал на выход 18 блока 17.

По нему на вход 34 регистра 1 сдвига поступает единичный сигнал, а на вход 35 — нулевой, регистр 1 сдвига устанавливается в режим параллельной записи. По сигналу управления с выхо- б0 да элемента 55 задержки адрес следующей микрокоманды записывается в счетчик 42.

По приходу сигнала-строб на вход

36 в регистр 1 с выхода блока 10 памяти считывается содержимое первой строки-кортежа отношения. По первому импульсу с выхода генератора 49 откры202 ь вается группа 45 элементов И и адрес второй микрокоманды с выхода счетчика 42 поступает на адресные входы блока 47 памяти. При этом на регистр

40 считывается код второй микрокоманды, в результате чего сигнал появляется на выходе 19 блока 17. По этому сигналу открывается группа 7 элементов И, на входах 35 и 36 регистра 1 сдвига устанавливаются единичные сигналы, которые переводят регистр в режим сдвига, и с входа 30 устройства код проекции поступает на первые входы группы элементов И 58, на выходах которых появляется либо единичный сигнал, разрешающий сдвиг информации с данного D-триггера на следующий, либо нулевой запрещающий сигнал . Так, например, если регистр восьмиразрядный и на первые входы группы элементов И 58 поступает код проекции 11110000, то происходит сдвиг вправо содержимого D-триггеров с четвертого по седьмой (считаем крайний первый триггер нулевым), содержимое D-триггеров с нулевого по второй не изменяется, причем в седьмой D-триггер записывается нуль, а содержимое третьего D-триггера теряется, т .е. исключается из строки-кортежа данный атрибут. Если это не последняя строка отношения, то последний разряд (банк 11) блока 10 памяти содержит нуль, в противном случае единицу. При этом по импульсу триггер

53 устанавливается в единичное состояние. По следующему импульсу с выхода генератора 49 появляется сигнал на выходе 20 блока 17, по которому .содержимое счетчиков 14 и 15 увеличивается на единицу. По импульсу на выходе .21 блока 17 содержимое счетчика 15 уменьшается на единицу и на его выходе устанавливается предыдущий адрес, по которому на выходе ° блока 12 памяти устанавливается содержимое данной ячейки. Если этот адрес не равен нулю, то на выходе дешифратора 9 будет нулевой сигнал, в противном случае — единичный. По импульсу на выходе 22 блока 17 управления в блоке 16 сравнения сравниваются строки-кортежи из регистра сдвига и блока памяти. При сравнении на. выходе блока 16 сравнения устанавливается единичный сигнал, в противном случае — нулевой, и следующим будет сигнал на выходе 21 блока 17 уйравления, по которому содержимое

1552202 счетчика 15 уменьшается на единицу

Приведенный цикл работы продолжается до тех пор, пока не появится единич- :. ный сигнал на выходе дешифратора 9, означающий отсутствие строки-кортежа из регистра 1 сдвига в блоке 12 памяти, или на выходе блока 16 сравнения, что означает наличие строки-кортежа в блоке 12 памяти. По импульсу с выхо10 да 21 блока 17 управления единичный сигнал на выходе дешифратора 9 увеличивает содержимое счетчика 42 на единицу. По следующему импульсу с выхода генератора 49 появляется сигнал на выходе 23 блока 17 управления, 15 по которому адрес из счетчика 14 записывается в счетчик 15. По сигналу на выходе 24 блока 17 управления блок 12 памяти переводится в режим записи, строка-кортеж из регистра 1

20 сдвига записывается по указанному адресу и через элементы И группы 8 поступает на выход 38 устройства. По сигналу на выходе 25 содержимое счет- 25 чика 13 увеличивается на единицу, и работа устройства продолжается аналогично. По сигналу с выхода 22 блока 17 управления единичный сигнал с выхода блока 16 сравнения увеличивает на единицу содержимое счетчика 42.

По импульсу с выхода генератора 49 появляется сигнал на выходе 25 блок

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

49 появляется сигнал на последнем выходе дешифратора 43, вследствие че-. го генератор 49 устанавливается и запертое состояние и работа устройства прекращается, Ф о р м у л а и з о б р е т е н и я

Вычислительное устройство, содержащее первый счетчик, первый блок памяти, две группы элементов И и группу элементов ИЛИ, причем информационный вход первого счетчика является .первым информационным входом устрой ства, первые входы элементов И первой группы образуют второй информацион- ный вход устройства, выходы элементов И первой группы соединены с первыми входами элементов ИЛИ группы, выход первого счетчика соединен с адресным входом первого блока памяти, выходы элементов И второй групгы являются выходом устройства, о т л и— ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет реализации операции про екции реляционной алгебры, в него введены второй и третий счетчики, де" шифратор, второй блок памяти, блок сравнения, регистр сдвига, три эле- >: мента ИЛИ и элемент НЕ, причем первый вход блока управления является входом запуска устройства и соединен с первым входом первого элемента ИЛИ, выход которого подключен к счетному входу второго счетчика и первому входу второго элемента ИЛИ, выход которого подключен к суммирующему входу третьего счетчика, информационный вход которого соединен с выходом второго счетчика, выход третьего счет-, чика подключен к входу дешифратора и к адресному входу второго блока памяти, выход которого соединен с первым информационным входом блока сравнения, выход которого соединен с вторым входом блока управления, третий вход которого является входом начального адреса микропрограмм устройства, четвертый и пятый входы блока уп авуправления соединены с первым выходом пе ервого блока памяти и выходом дешифратора соответственно, второй выход первого блока памяти соединен с информационным входом регистра сдвига, выходы которого соединены с инфо маор ационными входами второго блока памяти, вторыми информационными входами блока сравнения и первыми входами элементов И второй группы, вторые входы которых подключены к первому выходу блока управления и стробирующему входу второго блока памяти, второй выход блока управления подключен к стробирующему входу блока сравнения, третий выход блока управления соединен с вычитающим входом третьего счетчика, четвертый и пятый выходы блока управления соединены с вторыми входами первого н второго элементов ИЛИ соответственно, счетный вход первого счетчика соединен с шестым выходом блока управления„ седь мой выход блока управления соединен

1552202

10 с вторыми входами элементов ИЛИ группы, входом элемента НЕ и первым входом третьего элемента ИЛИ, выходы которых соединены с первым, вторым и третьим управляющими входами регистра сдвига соответственно, восьмой ,выход блока управления соедийен с 1 вторыми входами элементов И первой

S группы и вторым входом третьего элемента ИЛИ.!

8 19 8021 2823ß25

1552202

1552202

Редактор О.Юрковецкая

Заказ 332 Тираж 564 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

8 д

С

f77

Составитель И.Поливода

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