Устройство для моделирования изменения объема сетевой базы данных Советский патент 1989 года по МПК G06G7/122 

1

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

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

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

изменений объема базы данных; на фиг.2 - функциональная схема регистратора вершины; на фиг.З - функциональная схема блока моделирования ак-. тивной вершины; на фиг.4 - функциональная схема блока контроля времени моделирования; на фиг.5 - функциональная схема блока формирования адреса; на фиг.6 - структура второго блока памяти; на фиг.7 - пример процесса изменения объема азы данных.

Устройство (фиг.1) содержит регистр 1 адреса, блок 2 контроля времени моделирования, блок 3 формирования адреса, первый блок 4 питания, дешифратор 5 номера активной вершины,второй блок 6 памяти, деЈь

СО СО 4 ЬО

шифратор 7 номера порождающей вершины, датчик 8 случайных чисел, блок 9 регистрации вершин, состоящий из п регистраторов вершин, блок 10 моделирования активной вершины, генератор 11 импульсов, блок 12 задержки

Блок 9 регистрации вершин предназначен для имитации процесса роста числа экземпляров вершин (сегментов) п типов и регистрации их количества в каждом поколении базы данных и состоит из п регистраторов вершин. Каждый регистратор (фиг.2) вершины содержит первый триггер 13 первый элемент НЕ 14, первую группу элементов И 15, сумматор 16, второй элемент НЕ 17, регистр 18, третью группу элементов И 19 и второй триггер 20.

Блок 10 моделирования активной вершины (фиг.З) предназначен--для реализации числа циклов моделирования процесса порождения новых экземпляров активной вершины (сегмента) в дйнном поколении базы данных и содержит триггер 21, счетчик 22 и элемент НЕ 23.

Блок 2 контроля времени моделирования (фиг.4) служит для задания и,контроля числа моделируемых поколений базы данных и состоит из счетчика 24 и группы элементов И 25.

Блок 3 формирования адреса (фиг.З служит для формирования следующего адреса ячейки памяти, в которой хранится информация о номерах порождающей и активной вершин (сегментов), моделируемых в данном поколении базы данных, и содержит триггер 26, формирователь 27 импульсов, счетчик 28 и элемент НЕ 29.

Регистр 1 адреса предназначен для хранения и выдачи максимального адреса ячейки первого блока 4 памяти.

Первый блок 4 памяти предназначен для хранения и выдачи номеров типов порождающей i и активной j вершин сегментов) базы данных. Пример заполнения первого блока 4 памяти для заданной логической модели базы данных приведен в таблице„

Дешифратор 5 номера активной вершины при поступлении на его вход кода номера активной вершины выдает на соответствующем выходе единичный сигнал.

Второй блок 6 памяти предназначен для хранения и выдачи при поступлении сигнала на его управляющий вход множестве значений вероятностей в соответствии с заданным адресом (ij) на адресном входе. Второй блок 6 памяти состоит из п страниц, 1-я страница соответствует i-и порож-

дающей вершине, каждая страница содержит п адресуемых областей, соответствующих j-й активной вершине. Каждая из областей содержит определенное число ячеек. Число запол5 ненных ячеек области и их содержимое определяется интервалом распределения случайной величины oi , и видом функции распределения F(cLJ ) соответственно.

Q На фиг.6 изображена структура второго блока памяти.

Датчик 8 случайных чисел формирует случайные числа oil (t) oi- . соответствующие числу экземпляров

5 сегмента типа Х в поколении t+1, порождаемых одним экземпляром сегмента типа X; в поколении t, с вероятностями |Poi, значения которых поступают с выхода второго блока 6 памяти.

Генератор 11 вырабатывает импульс с фиксированным периодом следования только при нулевом сигнале на входе. Блок 12 задержки задерживает прохождение единичного импульса с управляющего выхода блока 3 формирования адреса на временной интервал, достаточный для записи содержимого сумматора 16 накапливающего типа в регистре 18.

0

5

0

5

0

5

Формирователь 27 импульса генерирует единичный сигнал на выходе при перепаде сигнала на входе с нуля на единицу.

Ч

Для достижения указанной цели процесс изменения объема базы данных, содержащей конечное число типов Х, Хг...Хи взаимосвязанных информационных компонентов (сегментов), рассматривается как процесс смены поколений базы данных. Состояние базы данных описывается случайным вектором (u(t) fU,(t) ,..., (%(t), i-я компонента которого (Ч; (t) показывает, что в момент с имеется (U;(t) экземпляров типа X,. Процесс изменения объема базы данных я чается вероятностями перехода Р Дt ) .

5

равными вероятностям того, что один экземпляр сегмента типа X; за время t переходит (порождает) в совокупность экземпляров сегментов, соответствующую случайному вектору Ы (oij,... j& J,) где -oi - число экземпляров сегмента типа oij, - число экземпляров сегмента типа Х„.

При этом вероятность P(t) может быть представлена в виде P ,(t)

«,

П Poij, где - вероятность j-i J J

того, что один экземпляр сегмента типа X, порождает совокупность экземпляров сегмента типа Х, равную oij , где oij 0, 1,... .

В следующий момент времени t+1 каждый из имеющихся экземпляров сегмента Х, где i ,111, может породить случайное число (t) экземпляров сегмента Xj, для которого распределение вероятностей P{oi.Ht) oi РоЈ,, где oL 0,-1,..., и объем базы данных станет равным U (t+1) ( III, (t+1),..., J44(t+1)), где /u:(t + n Mt) . ,

+ о Z гд.е jk конкретное значение ы. порожденных экземпляров конкретным экземпля- .ром из fU|(t) .

На фиг.7 изображен пример процесса изменения объема базы данных для логической модели из таблицы для |U(0) (2,2,1,1).

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

неличин ot (t) и временем моделирования t.

0

Для определения характеристик случайного леса может быть использован ветвящийся случайный процесс с конечным числом частиц, которым и является ряд значений (U (t) .

При моделировании изменения объQ ема базы данных (фиг.7) устройство работает следующим образом. Перед началом моделирования содержимое регистров 18 регистраторов вершин равно начальному числу экземпляров

5 сегментов fU(t) (|U,(t), ) , Uh(t) типов X,, Xa,.«.,Xh соответственно в момент времени t 0. Содержимое регистра 1 адреса равно значению максимального адреса ячейки первого блока 4 памяти.

Триггеры 13, 20 и 21 находятся в нулевом, а триггер 26 в единичном состоянии. Содержимое счетчика 24 равно числу моделируемых поколе5 ний базы данных п, содержимое сумматоров 16 и счетчика 22 равно нулю, на первый управляющий вход счетчика 24 подан сигнал логической единицы.

° Так как на выходе счетчика 24 (фиг.4) присутствует сигнал 1, а триггер находится в единичном состоянии, то содержимое регистра 1 адреса будет записано в счетчик. 28

5 (фиг.5), после чего появившийся на его выходе сигнал О переведет триггер 26 в нулевое состояние и сигнал 1 с его нулевого выхода разрешит поступление информации на вы0 читающий вход счетчика 28. Содержимое счетчика 28 поступает на адресный вход первого блока 4 памяти и вызывает считывание из его ячейки памяти с адресом 7 кода номера по5 рождающей вершины 1 и кода номера активной вершины 1. Код номера активной вершины, поданный на вход дешифратора 5 (фиг.1), вызывает появление на первом информационном

0 входе регистратора вершин с номером 1 блока регистрации вершин сигнала 1, который переводит триггер 13 первого регистратора вершин в единичное состояние, а единичный сигнал

5 с единичного выхода триггера 13 разрешает запись информации всумматор 16 данного регистратора вершин.

Код номера порождающей вершины, поданный на вход дешифратора 7, вызывает появление на втором информационном входе регистратора вершин с номером 1 блока регистрации вершин сигнала Ч, который переводит триггер 20 первого регистратора в единичное состояние,а единичный сигнал с единичного выхода триггера 20 разешает считывание начального числа экземпляров W,(t) сегмента Х из ре- Q

гистра 18 в счетчик 22 блока моделиования активной вершины, после чего на выходе счетчика 22 появляется сигнал О, который переводит триггер 21 в единичное состояние, в ре- «г зультате чего разрешается поступление информации на вычитающий вход счетчика 22, запрещается прием инормации на информационные входы

счетчика 22 и запускается генератор 20 11 импульсов, единичные импульсы с выхода которого переводят в нулевое состояние триггеры 20 всех регистраторов вершин, что приводит к запреению считывания информации из ре- 25 гистров 18 в блок моделирования активной вершины. Каждый единичный импульс с выхода генератора 11 импульсов вызывает считывание из второго блока 6 памяти в соответствии с поданным на его вход адресом с

блока 4 памяти, множества вероят-

( с Pci| з в конкретном случае

{Poi}(5 которые подаются на вход датчика 8 случайных чисел, который вырабатывает случайное число oi , поступающее на вход сумматора 16 первого регистратора вершин. Этот же единичный сигнал уменьшает на единицу содержимое счетчика 22.

Как только содержимое счетчика 22 станет равным нулю, на его выходе появляется сигнал 1, появление которого разрешает прием информации на второй информационный вход счетчика 22, переводя триггер 21 в нуле вое состояние, запрещает работу генератора 11 импульсов и формирователь 27 импульсов в блоке формирования адреса генерирует единичный импульс, который уменьшает содержимое счетчика 28 на единицу. Таким образом заканчивается моделирование первой активной вершины, на фиг.7 это соответствует ситуации порождения новых экземпляров сегментов ти- 55 па X. экземплярами сегментов типа Х, данная ситуация задана в ячейке с адресом 7 блока 4 памяти.

30

35

40

45

50

Q

«г

20 25

55

30

35

40

45

50

После окончания моделирования всех порождающих ситуаций, заданных в блоке 4 памяти, т.е. как только со держимое счетчика 28 станет равным нулю, на его управляющем выходе появляется сигнал 1, который при поступлении на второй управляющий вход блока регистрации вершин разрешает считывание содержимого сумматоров 16 в регистры 18 всех регистраторов вершин, а пройдя через блок задержки 12, переводит триггеры 13 в нулевое состояние и обнуляет содержимое сумматоров 16. Этот же сигнал 1 с выхода счетчика 28 уменьшает на единицу содержимое счет чика 24, а также, переведя триггер 36 в единичное состояние, разрешает прием информации счетчиком 28 из регистра 1 адреса. На этом заканчивает ся моделирование первого поколения базы данных-, в результате в регистрах 18 регистраторов вершин содержится вектор U (t+1) ( (H,(t+1), (Uj(t+1) ,.. ., fUn(t+l)). Далее начинается моделирование следующего поколения базы данных. Описанная процедура повторяется до.тех пор, пока содержимое счетчика 24 не станет равным нулю, что приведет к сбросу на его выходе сигнала 1 и запрету очередное считывание адреса из регистра 1 адреса. На этом моделирование заканчивается, и в регистрах 18 блока регистрации вершин содержится вектор (U(t) (fU,(t+1), /U4(t), ..., (Un(t)), для t п,где п - число моделируемых поколений базы данных

Формула изобретения

1. Устройство для моделирования изменения объема сетевой базы данных, содержащее генератор импульсов, первый блок памяти и второй блок памяти, выходы которого соединены с входами настройки датчика случайных чисел, отличающееся тем, что, с целью расширения класса решаемых задач путем обеспечения возможности моделирования процесса изменения объема базы данных во времени, в него введены п регистраторов вершин, блок моделирования активной вершины, дешифратор номрр-i активной вершины, дешифратор ра порождающей вершины, б-юь s-irc-i 914

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

2. Устройство по п.1, отличающее ся тем, что каждый регистратор вершины содержит две группы элементов И, сумматор, регистр, два элемента НЕ и два триггера, группа информационных входов регистратора вершин соединена с первыми входами элементов И первой группы, выходы которых подключены jc входам

994210

сумматора, выходы которого соединены с входами данных регистра, выходы которого соединены с первыми входами

элементов И второй группы, выходы

5

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

IQ первый элемент НЕ к первому нулевому входу первого триггера, выход которого соединен с вторыми входами элементов И первой группы, второй информационный вход регистратора вер15 шины подключен к единичному входу второго триггера и через второй элемент НЕ к первому нулевому входу второго триггера, выход которого соединен с вторыми входами элементов И

2Q третьей группы, второй нулевой вход второго триггера является входом блокировки вершины регистратора вершины, вход записи которого подключен к входу синхронизации регистра, вход

25 сброса активности регистратора вершины соединен с вторым нулевым входом первого триггера и с входом сброса сумматора.

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

. с единичным входом триггера, единичный и нулевой выходы которого подключены соответственно к входу разрешения счета и к входу разрешения приема счетчика.

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

с единичным входом триггера и через элейент НЕ с нулевым входом триггера, единичный и нулевой выходы которого подключены соответственно к входу

35

45

50

55

11

разрешения приемам входу разрешения счета счетчика, входы данных которо го являются информационными входами блока.

5. Устройство по п.1, о т л и - чающееся тем, что блок контроля времени моделирования содержит счетчик и группу элементов И, выходы которых являются выходами

7994212

блока, вход счета времени которого

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

Изобретение относится к вычислительной технике. Цель изобретения - расширение класса решаемых задач. Для этого в устройство введены блок контроля времени моделирования, блок формирования адреса, регистраторы вершин, блок моделирования активной вершины. Процесс изменения объема базы данных рассматривается как процесс смены ее поколений. Блок контроля времени моделирования служит для задания и контроля числа моделируемых поколений базы данных. Моделирование осуществляют следующим образом. В блоке формирования адреса формируется следующий адрес ячейки памяти, определяющий порядок моделирования базы данных. Процесс порождения экземпляров сегментов задается в блоке моделирования активной вершины. Число порождаемых экземпляров случайно и характеристики распределений заданы в блоке памяти. 4 з.п. ф-лы, 7 ил., 1 табл.

От d/f, 12 От fa J От fa, 11 Фиг. 2

к fan

о-

От fa tO О-

27

От 6л. 2

О-

/7i

Л

f-Д

Д

Л « «

U

/&/

н5л.2,12.9 -О

нВл.4 -О

1JL

/

Ј0

фигЗ

ри&.6

«

ЈL

(М

3 в

Г

V MS

и

it

Ч