JPH0559468B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、図形データをデータベースとして
記憶管理し、データベースに図形データを入力し
たり、図形データを検索したりするデータベース
装置、特に図形データ検索装置に関するものであ
る。

〔従来の技術〕

第１３図は、例えば情報処理学会研究報告85−
DB−50−１「図形データベースの特性と管理方
式の考案」の４ページのシステム構成図に見るよ
うな従来のデータベース装置を示すブロツク構成
図である。図において、１は図形データを入力す
る図形データ入力手段、２は図形データを記憶す
る図形データメモリ、３は図形データの定義情報
を入力する図形定義データ入力手段、４は図形デ
ータの定義情報を記憶する図形定義データメモ
リ、５は検索条件を入力する検索条件入力手段、
６はこの検索条件に従い図形定義データメモリ４
に記憶された図形データの定義情報を参照しなが
ら図形データメモリ２から指定された図形データ
を検索して読出す図形データ読出し手段、７は読
出された図形データを表示して確認するための図
形表示装置である。

このように構成された従来のデータベース装置
について、図形データを入力し、これに対して図
形データを検索する例を用いてその動作を説明す
る。

第２図は説明に用いる図形データを示す。外枠
の数字はｘ（横方向）ｙ（縦方向）の座標値であ
る。閉領域は家屋を、２本の平行線は道路を示
す。ここで、図形の定義を次のように行う。

即ち、ベクトルは２点で決定される直線、線は
途中に分岐点を持たないベクトルのつながり、線
群は互いに共有点を持ち一つの意味図形を構成す
る線の集合である。同図で、○内の数字は家屋番
号を、（ ）内の数字は線番号を示す。

通常、図形データはこのように図形の意味レベ
ルで階層的に定義することにより、データの重複
を避け、処理の内容に応じたレベルの図形データ
を選択して処理を行うことができる。

第３図は、このように図形を定義した場合の第
２図の図形データの内容を示している。各テーブ
ルの１行はその図形レベルの１図形に対応する。
また、各テーブル内での行番号はその図形レベル
での図形データの一意番号を示している。被参照
テーブルへのポインタを与えるスタートおよび数
は、その図形データが参照する被参照テーブルの
行番号およびその行番号から連続して参照する行
数を示す。

例として、家屋１は線群１を参照し、線群１は
線５、線１、線２、線３、および線６を参照す
る。また、線１はベクトル１、ベクトル２、およ
びベクトル３を参照する。中間テーブルは線群か
ら線へのポインタがスタートと数で与えられない
ため便宜上設けた仮想テーブルである。このよう
に、家屋１は８本のベクトルから構成される。

第４図ａ，ｂは第３図に見る図形データの定義
構造の情報である。個々の図形テーブルのデータ
構造を定義する図形定義テーブル（同図ａ）およ
び各図形テーブル間の参照構造を定義する参照定
義テーブル（同図ｂ）から成る。

図形定義テーブルにおいて、図形タイプはその
図形データが座標データを持つ（図形タイプ＝
２）が持たない（図形タイプ＝１）かの区別を表
す。例として、家屋テーブルは図形タイプ＝１
（座標データを持たない）で、カラム数は３、行
数（図形データ数）は２である。

参照定義テーブルにおいて、参照タイプは被参
照テーブルへのポインタがスタートと数より与え
られる（参照タイプ＝１）か被参照テーブルの行
番号で与えられる（参照タイプ＝２）かの区別を
表す。参照ポインタのカラム番号は、参照テーブ
ルにおける参照ポインタのカラム番号を表す。例
として、家屋テーブルから線群テーブルへの参照
タイプは１（ポインタはスタートと数で与えられ
る）で、そのポインタは家屋テーブルの２カラム
目から始まる（同定義テーブルの１行目）。

まず、図形定義データ入力手段３は、第４図の
図形定義テーブルおよび参照定義テーブルの情報
を入力し、図形定義データメモリ４に格納する。
また、図形データ入力手段１は第３図の図形デー
タを入力し、図形データメモリ２に格納する。

次に、このような図形データのデータベースに
対して検索を行うため、検索条件入力手段５から
検索条件を入力する。第１４図はこの説明で用い
る検索条件の内容を示す。即ち、家屋テーブル
（指定テーブル）についてこれが参照するベクト
ルテーブル（目的テーブル）の図形データを検索
して読出す。

図形データ読出し手段６は、第１４図の検索条
件に従い図形定義データメモリ４に記憶された第
４図の定義情報を参照しながら、図形データメモ
リ２に記憶された第３図の図形データに対して検
索を行う。まず第４図の参照定義テーブルから、
家屋テーブル→線群テーブル→中間テーブル→線
テーブル→ベクトルテーブルの順にデータをアク
セスすればよいこと、被参照テーブルをアクセス
するための参照のタイプ、ポインタのあるカラム
番号がわかる。

これにより、図形データ読出し手段６は家屋１
から始めて線群へのポインタにより線群１をアク
セスする。次に線群１の中間ポインタへのポイン
タにより中間テーブルの１〜５行をアクセスす
る。さらに、その線へのポインタにより線テーブ
ルの行番号５，１，２，３，６の各行をアクセス
する。最後にそのベクトルへのポインタによりベ
クトルの行番号８，１〜３，４〜５，６，９の各
行をアクセスする。

このようにして、家屋１に対して読出されたベ
クトルデータを示したのが第６図である。家屋２
に対しても同様にベクトルデータが読出される。
読出されたベクトルデータの座標値をもとに図形
表示装置７に表示された図形が第７図である。

〔発明が解決しようとする課題〕

ところで上記のような従来のデータベース装置
では、説明で用いた検索の例、即ち検索で指定す
る図形テーブル（指定テーブル）と、データを読
出すべき図形テーブル（目的テーブル）との間に
１つ以上の図形テーブルが定義されている場合で
は、目的テーブルのデータをアクセスするのに毎
回必ず指定テーブルから順に目的テーブルまでの
各図形テーブルのポインタをアクセスする必要が
ある。

従つて、目的テーブルに至るまでのテーブル数
が多くなるにつれて、アクセスすべきデータ量が
増大するため、図形データの検索に要する時間が
多大になる等、性能上の問題点があつた。

この発明は上記のような問題点を解消するため
になされたもので、図形データの検索を高速に行
うことができる図形データ検索装置を得ることを
目的とする。

〔課題を解決するための手段〕

この発明に係る図形データ検索装置は、図形デ
ータ読出し手段６により読出された目的テーブル
の図形データに含まれる一意番号、すなわち行番
号を一時的に記憶する図形データ一時記憶手段８
と、記憶された行番号をソートするソート手段９
と、ソートされた行番号に連続しない箇所がある
場合にその不連続箇所を検出する不連続検出手段
１０と、ソート手段９と不連続検出手段１０によ
り得られたデータをもとに指定テーブルの図形デ
ータからの目的テーブルの図形データへの直接の
参照ポインタを生成するポインタ生成手段１１と
を付加したものである。

〔作用〕

この発明における図形データ一時記憶手段８
は、図形データ読出し手段６により読出された目
的テーブルの図形データの行番号を一時的に記憶
する。ソート手段９は、図形データ一時記憶手段
８に記憶された行番号をソートする。不連続検出
手段１０は、ソートされた行番号において番号が
不連続の箇所を検出する。ポインタ生成手段１１
は、ソートされた行番号およびその不連続箇所の
情報をもとに指定テーブルの図形データからの目
的テーブルの図形データへの直接の参照ポインタ
を生成する。

図形データ入力手段１及び図形定義データ入力
手段３はこうして生成されたポインタ及びその定
義情報を図形データ記憶手段２及び図形定義デー
タ記憶手段４に追加入力する。これにより、図形
データ読出し手段６は、以降上記と同じ指定テー
ブルから目的テーブルへの検索が要求された時は
このポインタをアクセスして目的テーブルの図形
データを高速に読出す。

〔実施例〕

第１図は、この発明の一実施例であるデータベ
ース装置を示すブロツク構成図で、図中、第１３
図従来例と同一符号は同一または相当部分を示し
ており、その説明は省略する。

図において、８は図形データ読出し手段６によ
り読出された図形データの行番号を一時的に記憶
するバツフアメモリ、９はバツフアメモリ８に記
憶された行番号を昇順にソートするソー手段、１
０はソート手段９によりソートされた行番号にお
いて番号が不連続の箇所を検出する不連続検出手
段、１１はソートされた行番号およびその不連続
箇所の情報をもとに指定テーブルの図形データか
ら目的テーブルの図形データへの直接の参照ポイ
ンタを生成するポインタ生成手段である。

次に、第１図のデータベース装置の動作例を従
来のデータベース装置の動作例で用いたのと同じ
第２図の図形データを用いて説明する。

従来のデータベース装置と同様に図形定義デー
タ入力手段３は第４図に示す図形データの定義情
報を入力し、図形定義データメモリ４に格納す
る。また図形データ入力手段１は第３図の図形デ
ータを入力し、図形データメモリ２に格納する。

次に、このような図形データのデータベースに
対して検索を行うため、検索条件入力手段５から
検索条件を入力する。第５図はこの検索条件の内
容を示す。検索条件は、家屋テーブル（指定テー
ブル）についてこれが参照するベクトルテーブル
（目的テーブル）の図形データを読出すことを示
す。但しこの時、家屋テーブルからベクトルテー
ブルへの直接の参照ポインタ（インデツクス）を
生成する（検索タイプ＝１）ことを指定してい
る。

図形データ読出し手段６は、第５図の検索条件
に従い図形定義データメモリ４に記憶された第４
図の定義情報を参照しながら、図形データメモリ
２に記憶された第３図の図形データに対して検索
を行う。

従来のデータベース装置と同様にして家屋１に
対して読出されたベクトルデータを示したのが第
６図である。家屋２に対しても同様にベクトルデ
ータが読出される。

次に、家屋テーブルからベクトルテーブルへの
直接の参照ポインタを生成するため、図形データ
読出し手段６は家屋１について読出されたベクト
ルデータの行番号をバツフアメモリ８に入力す
る。第８図ａはバツフアメモリ８の内容である。
ソート手段９はこの行番号を昇順にソートする。
ソートされた結果が第８図ｂである。さらに、不
連続検出手段１０は、ソートされた結果に対し行
番号が連続しない箇所を検出する。第８図ｃは検
出された不連続箇所に示している。これにより、
家屋１はベクトル１〜６とベクトル８〜９を参照
していることがわかる。従つて、ポインタ生成手
段１１は第８図ｄに示すポインタを生成し、生成
されたポインタは図形データ入力手段１により図
形データメモリ２に追加入力される。家屋２につ
いても同様にベクトルテーブルへのポインタが生
成され、図形データメモリ２に入力される。第９
図のフローチヤートはポインタが生成される上記
手順を第８図ａ〜ｄに対応して示している。第１
０図は、こうして図形データメモリ２に作成され
た結果を示している。同図で、家屋テーブル中の
インデツクスへのポインタ、インデツクステーブ
ルのベクトルへのポインタが、生成して入力され
た部分である。

一方、図形定義データ入力手段３は、こうして
作成された家屋テーブルからベクトルテーブルへ
の直接の参照ポインタをこの後の検索時に利用可
能とするため、インデツクステーブルの定義情報
およびインデツクステーブルと家屋、ベクトルテ
ーブルとの参照定義情報をそれぞれ図形定義デー
タメモリ４の図形定義テーブルおよび参照定義テ
ーブルに追加入力する。第１１図ａ，ｂは追加入
力後の図形定義データメモリ４の内容を示す。

次に、こうして生成されたインデツクスを使用
して検索する例を説明する。検索条件入力手段５
から第１２図に示す検索条件が入力される。検索
条件は、家屋テーブル（指定テーブル）につい
て、これが参照するベクトルテーブル（目的テー
ブル）の図形データを読出すことを示す。但し、
この時、インデツクスを使用する（検索タイプ＝
２）ことを指定している。図形データ読出し手段
６は、第１２図の検索条件に従い図形定義データ
メモリ４に記憶された第１１図の定義情報を参照
しながら、図形データメモリ２に記憶された図形
データに対して検索を行う。まず、第１２図の検
索条件と第１１図の参照定義テーブルから、家屋
テーブル→インデツクステーブル→ベクトルテー
ブルの順にポインタに従いデータをアクセスすれ
ばよいこと、被参照テーブルをアクセスするため
の参照ポインタのタイプ、ポインタのあるカラム
番号がわかる。

これにより、図形データ読出し手段６は、家屋
１から始めてインデツクスへのポインタに従いイ
ンデツクステーブルの１〜２行をアクセスする。
さらにそのベクトルへのポインタに従いベクトル
テーブルの行番号１〜６および８〜９の各行の図
形データを読出す。

このようにして、家屋１に対して第６図に示し
たので同じベクトルデータが高速に読出される。
家屋２に対しても同様にベクトルデータが高速に
読出される。そして、読出されたベクトルデータ
の座標値をもとに第７図に示す図形が図形表示装
置７に表示される。

従つて、ある指定した図形テーブルの図形デー
タが参照する他の図形テーブル（目的テーブル）
の図形データを検索して読出す処理を高速に行う
ことができる。これは、上記実施例で示したよう
に、インデツクスがない場合に家屋１が参照する
ベクトルデータを検索して読出すのにアクセスす
べき図形テーブルの総行数が20（家屋テーブルで
１行、線群テーブルで１行、中間テーブルで５
行、線テーブルで５行、ベクトルテーブルで８行
アクセスする）であるのに対し、インデツクスを
使用して家屋１が参照するベクトルデータを検索
して読出すのにアクセスすべき図形テーブルの総
行数が１１（家屋テーブルで１行、インデツクス
テーブルで２行、ベクトルテーブルで８行アクセ
スする）で済むことから明らかである。

また、インデツクスを作成する前にポインタに
従い指定テーブルから目的テーブルへ至るまでに
アクセスすべき図形テーブルの個数（実施例では
３個）が多いほど、この発明による効果は大き
い。

〔発明の効果〕

以上のように、この発明によれば、図形データ
読出し手段により読出された図形データに含まれ
る一意番号を一時的に記憶する図形データ一時記
憶手段と、記憶された一意番号をソートするソー
ト手段と、ソートされた一意番号に連続しない箇
所がある場合にその不連続箇所を検出する不連続
検出手段と、ソート手段と不連続検出手段により
得られたデータをもとに上記指定テーブルの図形
データからの目的テーブルの図形テーブルをの直
接指すポインタを生成するポインタ生成手段とを
付加し生成されたポインタとその定義情報を図形
データ記憶手段と図形定義データ記憶手段に追加
入力し、以降の同一検索は上記ポインタを用いて
行うようにしたので、図形データの検索を高速に
行える効果が得られる。

【図面の簡単な説明】

第１図はこの発明の一実施例を示すブロツク構
成図、第２図は図形データ入力手段から入力する
図形データの模式図、第３図および第１０図はそ
の図形データの内容を示す図、第４図ａ，ｂおよ
び第１１図ａ，ｂはそれぞれ第３図および第１０
図で示される図形データについてデータ構造の定
義情報を示す図、第５図と第１２図は実施例にお
いて検索条件入力手段から入力される検索条件の
内容を示す図、第６図は図形データ読出し手段に
より図形データメモリから検索して読出された図
形データを示す図、第７図は検索して読出された
図形データの座標値をもとに図形表示装置に表示
した結果を示す図、第８図ａ〜ｄは指定テーブル
から目的テーブルへの直接参照ポインタを生成す
るために、バツフアメモリ内のデータが処理され
ていく様子を示す図、第９図はこの直接参照ポイ
ンタを生成する処理の流れを示すフローチヤー
ト、第１３図は従来のデータベース装置のブロツ
ク構成図、第１４図は従来例において検索条件入
力手段から入力される検索条件の内容を示す図で
ある。 図中、１は図形データ入力手段、２は図形デー
タメモリ（図形データ記憶手段）、３は図形定義
データ入力手段、４は図形定義データメモリ（図
形定義データ記憶手段）、５は検索条件入力手段、
６は図形データ読出し手段、７は図形表示装置、
８はバツフアメモリ（図形データ一時記憶手段）、
９はソート手段、１０は不連続検出手段、１１は
ポインタ生成手段である。尚、図中、同一符号は
同一または相当部分を示す。

Claims (1)

【特許請求の範囲】
1. １ 同一のデータ構造をもつ１以上の図形データ
   からなる個々の図形テーブルのデータ構造を定義
   する情報および各図形テーブル間の参照構造を定
   義する情報を入力する図形定義データ入力手段
   と、図形定義データ入力手段から入力されたデー
   タを記憶する図形定義データ記憶手段と、図形テ
   ーブル内での一意番号と座標データ又は他の図形
   テーブルの図形データへの参照ポインタからなる
   図形データを入力する図形データ入力手段と、図
   形データ入力手段から入力された図形データを記
   憶する図形データ記憶手段と、検索条件を入力す
   る検索条件入力手段と、この検索条件に従い図形
   定義データ記憶手段に記憶された定義情報を参照
   しながら図形データ記憶手段から検索条件で示さ
   れた指定テーブルの図形データよりポインタに従
   つて目的テーブルの図形データを検索して読出す
   図形データ読出し手段と、図形データ読出し手段
   により読出された図形データに含まれる一意番号
   を一時的に記憶する図形データ一時記憶手段と、
   記憶された一意番号をソートするソート手段と、
   ソートされた一意番号に連続しない箇所がある場
   合にその不連続箇所を検出する不連続検出手段
   と、ソート手段と不連続検出手段により得られた
   データをもとに上記指定テーブルの図形データか
   ら目的テーブルの図形データを直接指すポインタ
   を生成するポインタ生成手段とを備え、生成され
   たポインタとその定義情報を図形データ記憶手段
   と図形定義データ記憶手段に追加入力し、以降の
   同一検索は上記ポインタを用いて行うようにした
   ことを特徴とする図形データ検索装置。