Устройство для выполнения операций редактирования записей таблиц Советский патент 1990 года по МПК G06F17/24 

установочным входом устройства, четвертый выход блока микропро раммно- ifo управления соединен с вторыми входами элементов И второй группы и с вторым входом элемента ИЛИ, пятый выход соединен с запускающим входом решающего блока, выход элемента И Соединен с синхронизирующим входом Третьего регистра, выход которого Является выходом устройства, шестой и седьмой выходы блока микропрограммного управления,соединены соответственно с первым входом элемента И и Счетным входом второго счетчика, Отличающееся тем, что, с целью расширения функциональных возможностей 31 счет обеспечения соединения строк таблиц в зависимости от выполнения заданного отношения срав- йения между несколькими элементами Строк различных таблиц, в решающий флок введены с второго по пятый элементы И, две группы элементов И, генератор прямоугольных импульсов, риггер, элемент задержки, с второго ito шестой элементы ИЛИ, два элемен- ta НЕ и два распределителя нмпуль- Сов, причем выходы разрядов второго и третьего регистров решающего блока соединены соответственно с первыми входами элементов И первой и второй групп, выходы которых соединены Соответственно с управляющими входами первого и второго коммутаторов и с входами второго и третьего элементов ИЛИ, выходы которых соединены Соответственно с входами первого и йторого элементов НЕ и с первым и

вторым входами второго элемента И, выход которого соединен с входом элемента задержки, выходы которого соединены с первым входом третьего элемента И и вторым входом первого элемента И, выход которого соединен с нулевым входом триггера, выход которого соединен с выходом решающего

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

5 ИЛИ соединены соответственно с тактны- ми входами первого и второго распределителей импульсов, выходы которых с первого по m-й соединены соот.ветст- венно с вторыми входами элементов И

0 первой и второй групп, (т-Н)-е выходы первого и второго распределителей импульсов соединены соответственно с входами шестого элемента ИЛИ, выход которого соединен с установочными

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

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

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

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

На фиг.1 приведена схема устройства; на фиг„2 - схема решающего блока; на фиг.З - схема блока микропрограммного управления; на фиг.4

временная диаграмма работы устройст- вао,

Устройство содержит счетчики 1 и 2, блок 3 памяти, регистры 4-7, группы 8 и 9 элементов И„ группу 10 элементов ИЛИ, элемент ИЛИ 11, элемент И 12, дешифратор 13 признака, блок 14 микропрограммного управления, выходы 15-21 блока 14, вход 22 блока 14, решающий блок 23, входы 24 - 26 и выход 27 блока 23, информационные входы 28 и 29 устройства, вход

30кода отношения устройства, входы

31и 32, вход 33 запуска, установоч-i ный вход 34 и выход 35 устройства,

51

элемент ИЛИ 36, узлы 37 сравнения, коммутаторы 38 и 39, дешифратор 40, регистры 41 - 43, элементы И 44 - 48 группы 49 и 50 элементов И, генерато 51 прямоугольных импульсов, триггер 52, элемент 53 задержки, элементы ИЛИ 54 - 58, элементы НЕ 59 и 60, распределители 61 и 62 импульсов, счетчик 63, узел 64 памяти, группу 65 разрядов .узла 64, регистр 66 микрокоманд, группу 67 разрядов регистра 66, элемент 68 задержки, дешифратор 69, группу 70 элементов И, генератор 71 тактовых импульсов и элемен ты И 72 я 73.

На временной диаграмме работы устройства (фиг.4) приняты следующие обозначения: в левой части каждого блока указаны выполняемые устройст- вом микрооперации под действием импульсов с выходов блока микропрограммного управления, позиции которых размещены в правой части блока диаграммы; узлы на временной диаграмме обозначены их позициями, проставленными на фиг.1-3; если номер позиции заключен в скобки, то это означает содержимое соответствующего узла или сигнал на его выходе, стрелка обозна чает пересылку информации.

Отношения между объектами в реляционной базе данных представляются в виде таблицы. Строка таблицы определяется общепринятым способом. Столб- цы таблицы называются доменами. Значение домена в каждой строке таблицы называют компонентом строки. Таблицы хранятся в блоке 3 памяти, причем каждая строка таблицы, состоящая из компонентов, занимает одну ячейку памяти. В ячейку, непосредственно следующую за последней строкой таблицы, записывается уникальный код, который расшифровывается дешиф- ратором 13.

Операция соединения дает возможность соединить в результирующей таблице строки, принадлежащие различ ным исходным таблицам. Домены А и В одной и той же или различных таблиц называются 8-сравнимыми ( 0- одно из следующих отношений: ,7Ь,; , , , ,, если для любого компонента а е А и любого компонента b е В выражение а э b - ложь или ист тина, но не неопределенность.

Списки доменов А (,,.., A k) и В « (В,, ,Ва,. Р . ,Вр) называют

.« ;

20 25 30

, 0 45

50

5

ся 9 -сравнимыми, если и А, и Bj б-сравнимы |i 1 ,2, ,..,k I; в этом случае под критерием сравнения авЬ понимают, (, )И(а1 в1 Ь)/ Л... (%б Ь,,)0

Пусть А и В - списки доменов одинаковой длины отношений (таблиц) R и S соответственно и пусть А и В 9-сравнимы. Тогда соединением отношений R и S при условии называется отношение R A6B7S е

(rs) jr eR Л-s €S f (r CB7)}, где r - строка отношения R; s - строка отношения S; p X - компоненты X строки p.

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

При включении питания генераторы 51 и 57 устанавливаются в запертое, распределители 61 и 62 - в исходное состояние (при этом ни на одном из их выходов сигнал не появляется), а счетчик 68 обнуляется (цепи установки устройства в исходное состояние на схеме не показаны). В счетчик 1 по пходу 28 при синхронизации импульсом на входе 34 записывается адрес первого отношения (R), а регистр 7 по входу 29 - адрес второго отношения (S). Каждому домену отношений в регистрах 42 и 43 соответствует по одному разряду. По входу 31 в разряды регистра 42, соответствующие списку доменов А, записываются единицы. Аналогично в разряды регистра 43, соответствующие списку доменов В, по входу 32 записываются единицы, По входу 30 в регистр 4 J записцва- ется код отношения R. Он расшифровывается дешифратором 40, который выдает разрешающий потенциал на один из узлов 37 сравнения, проверяющий принадлежность двух кодов данному отно шенню R,Только избранный узел 37 Е последующем выдает сигнал на своем выходе в случае ложности выражения , устройство готово к рабо- те..

Запуск устройства в работу осуществляется импульсом по входу 33, по которому запускается генератор 7. По нулевому адресу в узле 64 памяти находится первая микрокоманда мккро программы работы устройства. Каждая микрокоманда состоит из операционной части (задает микрооперацию, которую нужно выполнить по данной микрокомандф) и адресной части (опоеделяет адрес следующей микрокоманды микропрограммы) о Адресная часть расподага- е рся в группе 65 разрядов узла 64 . Ей соответствует группа 67 разрядов регистра 66, По первому им- пульсу с выхода генератора 71 пер- вЈя микрокоманда принимается в регистр 66. Операционная часть растиф- рфвьыается дешифратором 69, который выдает сигнал на своем первом выхо- дф. Затем импульс появляется на выходе элемента 68 задержки. При этом адрес следующей микрокоманды прини- м4ется в счетчик 63. Кроме того, этот импульс через группу 70 элементов И пйоходит на выход 15 блока 14, в результате чего открывается группа 8 элементов И и разрешается запись ин- фс| рмации в счетчик 2. Адрес первой ( дальнейшем - очередной) строки отношения из счетчика переписывается в счетчик 2. По этому адресу из бЛока 3 памяти считывается первая (л дальнейшем - очередная) строка от- нс)шения R (считывание из блока 3 идет непрерывно по адресу, заданному на счетчике 2). Но второму импульсу с

10

15434198

манды находится первая (в дальнейшем - очередная) строка отношения R.

Четвертая микрокоманда ведет к появлению импульса на выходе 18 блока 14, по которому адрес первой строки отношения S из регистра 7 записывается в счетчик 2, так как открывается группа 9 элементов И разрешается запись информации в счетчик 2.

По пятой микрокоманде появляется импульс на выходе 16 блока 14. При этом первая (в дальнейшем - очередная) строка отношения принимается в регистр 4„ Если в регистре 4 находится не очередная строка отношения S, а признак конца отношения, то появляется сигнал на выходе дешифратора 13.

В результате выполнения шестой микрокоманды выдается импульс на выходе 19 блока 14. Но этому импульсу запускается блок 23. Триггер 52 устанавливается в единичное состояние, а генератор 51 начинает выдавать импульсы. На выходах элементов И 49 и 50 г присутствуют нулевые потенциалы а следовательно, на выходах элементов ИЛИ 54, 55 также имеются нулевые по - тенциалы. В результате этого на вы15

20

25

выхода генератора 71 на регистр 66 из 30 ходе элемента И 45 находится О,

64 памяти (который также считы- непрерывно) принимается вторая макрокоманда; адрес третьей микро- кйманды заносится в счетчик 63 и по- яйляется импульс на выходе 16 блока 14, вследствие чего первая (в даль- нфйшем - очередная) строка отно- R записывается в регистр 4t Если в регистре 4 находится код конца отношения, то появляется сигнал на выходе дешиф- р«1тора 13, который проходит на эле- мйнты И 73 и 72. После считывания в регистр 66 третьей микрокоманды появляется импульс на выходе 17 блока 140 По этому импульсу содержимое регистра 4 переписывается в регистр 5, а содержимое счетчика увеличивается н.1 единицу формируется адрес слецую- строки отношения R. Кроме того, в регистре 4 находится код кон- ц.| отношения, срабатывает элемент И 72, в результате чего генератор 71 останавливается„ а счетчик 63 обнуляется, Устройство прекращает свою работу. Если отношение R не исчерпано, то устройство продолжает работат О Рметим, что в этом случае в регистр 5 после выполнения третьей микрокоэлементы И 44 и 45 закрыты„ На выходах элементов НЕ 59 и 60 присутст - вуют единичные потенциалы. Следовательно, элементы И 47, 48 открыты.

5 Л

0

5

Первый импульс с выхода генератора 5 проходит через эти элементы И и через элементы ИЛИ 56 и 57 и поступает на входы распределителей 61 и 62, Они выдают потенциалы на своих первых выходах, которые открывают первые элементы И групп 49 и 50. При этом анализируются первые разряды регистров 42 и 43, соответствующие первым доменам отношений R и S. По второму импульсу с выхода генератора 51 аналогичным образом анализируются вторые разряды регистров 42 и 43, соответствующие вторым доменам отношений R и S, и ТоД. до тех пор, пока на выходе одного из элементов И группы 49 и/или одного из элементов И группы 50 не появится сигнал, т.е. до тех пор, пока не будет отыскана первая (начиная с первого разряда) 5 единица в регистре 42 и/или 43. При появлении сигнала на выходе одного из элементов И группы 49 и/или одного из элементов И группы 50 возникают сигналы на выходах элементов

0

91

ИЛИ 54 и/или 55. Предположим, что первым возник сигнал на выходе элемента ИЛИ 54. В результате этого подготавливается к срабатыванию элемент И 45, а на выходе элемента НЕ 59 появляется низкий уровень, закрывающий элемент И 47. Поступление импульсов на вход распределителей 61 временно блокируется. Этот распределитель под- держивает сигнал на том же выходе, который соответствует разряду регистра 42, содержащему первую единицу. Код с выходов элементов И 49 постоянно подается на адресные входы комму- татора 38, который выделяет из строки отношения R, хранящейся в регистре 5, компоненту, соответствующую пер BOMV домену из списка А, т.е домену А. После отыскания первой едини- цы в регистре 43 элемент И 48 закрывается, коммутатор 39 выделяет из строки отношения, находящейся в регистре 4, компоненту, принадлежащую первому домену из списка В, т.е. до- мену В, и срабатывает элемент И 45 (на его выходе появляется сигнал). Избранный узел 37 выдает сигнал, если выражение r..g В,} принимает ложное значение, где j - номер строки отношения R, хранящейся в регистре 5; 1 - номер строки отношения 8, находящейся на регистре 4. Этот сигнал (при его возникновении) поступает на элемент И 44. С задержкой, необходимой для протекания переходных процессов в одном из узлов 37, сигнал с выхода элемента 45 появляется на выходе элемента 53 и проходит через него, устанавливая триггер 52 в нулевое состояние, если выражение гДА,©я еСН,} принимает значение Ложь (а если Истина, то триггер 52 остается в единичном состоянии). Этот же сигнал открывает элемент И 46, в результате чего следующий импульс с выхода генератора 51 проходит через этот элемент и через элементы ИЛИ 56 и 57 на входы распределителей 61 и 62, которые снимают сиг- налы с очередных своих выходов и выдают сигналы на следующих выходах. Элемент И 45 закрывается, а элементы И 47 и 48 открываются (этого может и не произойти, если следую- щие разряды регистров 42 и 43 также содержат единицы; в этом случае снова срабатывает элемент И 45). Следующие импульсы с выхода генератора

19Ю

51 начинают вновь проходить через элементы И 47 и 48 на входы распреде лителей 61 и 62. В дальнейшем по отысканию компонент, соответствующих доменам А, и В,- блок 23 работает аналогично, В случае, когда один из регистров 42 и 43 просмотрен полностью, появляется сигнал на (т+1)-м выходе распределителя 61 или 62, который проходит на выход элемента ИЛИ 58, останавливая генератор 51 и устанавливая в исходное состояние распределители 61 и 62. Ждать окончания просмотра другого регистра не следует, так как число доменов в списках А и В совпадает. Таким образом, если выражение

AJes Bj/irj-rAJes BjA ... о о. Л rjCAv ese Bv

принимает значение Истина, то триггер 52 остается в единичном состоянии, открывая элемент И 12. В противном случае триггер 52 в процессе работы блока 23 обнуляется.

Адрес следующей микрокоманды при выполнении шестой микрокоманды определяется следующим образом. Как и ранее, адресная часть микрокоманды записывается в счетчик 63. Однако если в регистре 4 находится код конца отношения S (в этом случае результат работы блока 23 является заведомо неверным), то импульс с выхода С блока 14 через элемент И 73 проходит на суммирующий вход счетчика 63, увеличивая его содержимое на единицу Таким образом, осуществляется разветвление в микропрограмме. Если отношение S исчерпано, то осуществляется переход к первой микрокоманде ( после увеличения содержимого счетчика 63 на единицу выбирается фиктивная микрокоманда, не расшифровываемая дешифратором 69, но содержащая в адресной части адрес первой i микрокоманды). Если отношение S не исчерпано, то результат работы блока 23 является верным. На регистр 66 принимается седьмая микрокоманда, по которой появляется импульс на выходе 20 блока 14. Он проходит через элемент И 12 только в том случае если выражение

Г| ГА,© SjCB /lrj/lfAjeSjCBjA ...

и

...Л г. A. Jes.CB. J

истинно, в результате чего очередная строка r,Sg отношения R A6B7S записывается в регистр б п выпается ) э rfa выход 35 устройства„

По восьмой микрокоманде появляется импульс на выходе 21 блока 14,

154341912

по которому содержимое счетчика 2 увеличивается на единицу, Т0е0 в счетчике 2 формируется адрес следующей строки отношения.

Следующей выбирается пятая микрокоманда,

В дальнейшем устройство работает аналогично описанному.

3/

Фиг. 2

16 П

2Q г/

J -

нГбГТ

- -----аЛтавтамр

31

63

54

23

3

СНачалоj

( Конец

Фиг.%