オブジェクト指向データベースにおける質問の型検査問題
スポンサーリンク
概要
- 論文の詳細を見る
オブジェクト指向データベース(OODB)における質問の型検査問題の計算複雑さについて述べる.OODBスキーマSとそのインスタンスXが与えられたとき,S中の各メソッドmの実行中に結合すべきメソッドが常に一意に定まるならば,XはSのもとで型整合性をもつという.本稿では,Hullらによって提案された更新スキーマをOODBスキーマのモデルとして採用し,与えられた再帰なし更新スキーマのもとで(1)型整合性をもたないインスタンスが存在するか否かおよび(2)型整合性をもたない無閉路インスタンスが存在するか否かを判定する問題がいずれも非決定性指数時間完全であることを示す.さらに,(3)与えられた任意の更新スキーマのもとで型整合性をもたない無閉路インスタンスが存在するか否かを判定する問題が決定不能であることを示す.
- 一般社団法人情報処理学会の論文
- 1995-11-30
著者
関連論文
- オンライン情報ボトルネックEMアルゴリズムによる正規化ガウス関数ネットワークのモデル学習
- ユーザ指定関係に基づいた情報保存を満たすXMLスキーマ進化
- 木埋め込み関係に基づくXMLスキーマ進化に応じたXPath問合せ変換(夏のデータベースワークショップ2007(データ工学,一般))
- 木の埋め込み関係に基づくXMLスキーマ進化に応じた文書変換器の生成法(夏のデータベースワークショップ2007(データ工学,一般))
- 木埋め込み関係に基づくXMLスキーマ進化に応じたXPath問合せ変換(XML (1),夏のデータベースワークショップ2007(データ工学,一般))
- 木の埋め込み関係に基づくXMLスキーマ進化に応じた文書変換器の生成法(XML (1),夏のデータベースワークショップ2007(データ工学,一般))
- XMLデータベースにおけるスキーマ進化のための更新操作群とそれらのスキーマ表現能力保存に関する性質(基礎理論,フォーマルアプローチ論文)
- XMLデータベースへの型推論を用いた攻撃に対する安全性検証(XML,夏のデータベースワークショップDBWS 2006)
- XMLデータベースへの型推論を用いた攻撃に対する安全性検証(XML)
- ペア確率多重文脈自由文法によるシュードノットつきRNA2次構造予測
- 束構造をもつセキュリティクラスに基づく再帰的プログラムに対する情報フロー解析法
- ラベル付き遷移システムに基づくアスペクト指向プログラムのモデル化
- 木オートマトンを用いたXML処理
- 実行履歴に基づくアクセス制御の形式モデルと検証(セキュリティ,フォーマルアプローチ論文)
- XML文書に対するアクセシビリティガイドライン適合性検証(ソフトウェア,フォーマルアプローチ論文)
- 信用管理における確率モデルに基づく利用者プレゼンスの推定(位置情報とRFID, ホームネットワーク, ヒューマンインタフェース, 情報家電, アクセシビリティ)
- 代数的仕様からのドュメント自動生成について
- 仮想機械デバイスドライバ検証の一考察
- 自己合成法を利用した再帰プログラムの情報流解析法について
- D-3-1 HBACプログラムのモデル検査の情報フロー解析への応用(D-3.ソフトウェアサイエンス,一般講演)
- 実行履歴に基づくアクセス制御付きプログラムのモデル検査法による情報フロー解析
- 実行履歴に基づくアクセス制御付きプログラムのモデル検査
- 実行履歴に基づくアクセス制御付き再帰プログラムの形式モデル
- プッシュダウンシステムの拡張およびそのモデル検査法
- 分散ポリシー制御の自動検証法について
- インタラクティブシステム設計法におけるタスク図の形式的定義と形式的検証への応用(ソフトウェア工学の基礎)
- インタラクティブシステム設計法におけるタスクモデルの形式的記述と検証
- 抽象的順序機械型代数的仕様からのドキュメント生成システム
- 抽象的順序機械型代数的仕様からのドキュメント生成システムの試作
- 情報流仕様に基づくアクセス制御文の自動生成
- ユーザの動作類似度に基づく共通鍵生成法(セッション6-B:セキュリティ理論)
- 生命の言語の理解をめざして(平成19年度論文賞の受賞論文紹介)
- タンパク質ベータシート予測 : 動的計画法と形式文法によるアプローチ(一般セッション3)
- 相互作用RNA2次構造予測 : 形式文法によるアプローチ
- 形式文法に基づくRNA2次構造予測(若手研究者のための講演会)
- 信用交渉における公開木戦略の計算量(計算機科学の理論とその応用)
- データフロー解析を用いた侵入検知法の提案
- アドホックネットワークにおけるPKI証明書連鎖発見問題について(セッション2:セキュリティ)
- 多重文脈自由文法とマクロ文法の生成能力について
- XMLデータベースへの推論攻撃による機密情報特定可能性の形式化とある前提条件のもとでの特定可能性検証法の提案
- XMLデｰタベｰスにおける表現能力を保存したスキｰマ更新操作
- XMLデータベースにおける表現能力を保存したスキーマ更新操作(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- XMLデータのスキーマ統合のための枠組の提案
- 異なる構造を持つXMLデータを統合するための構造間の関係について(実空間とサイバースペースの融合 : 感性, データベース, ロボティクスおよび一般)
- 関連性の高いアイテム集合のマイニングに要する計算量
- 検索および再帰なし無閉路スキーマに対する型検査問題の計算量
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- ユーザの動作類似度に基づく共通鍵生成法(セッション6-B:セキュリティ理論)
- ユーザプレゼンスを利用した信用管理方式
- 評価者間類似度計算の改善による汚染コンテンツダウンロード抑制効果向上
- The validity problem of positive XPath queries in the presence of DTDs (ソフトウェアサイエンス)
- 確率多重文脈自由文法によるRNAシュードノット構造予測(DNA・タンパク質構造)
- RNA2次構造記述向き形式文法の生成能力について(文字列アルゴリズム)
- 通信プロトコルのフェーズ連結法とそれに基づく検証法
- VAR-CCGの生成能力について
- 語彙機能文法のいくつかの部分クラスに対する一般認識問題の計算量について
- 自然語仕様から代数的仕様への変換における表現式の構文規則の生成
- メソッドスキーマにおける型整合性の解析アルゴリズム
- メソッドスキーマの型整合性の十分条件
- 有界到達可能性解析を用いた非有界通信プロトコルの解析法
- 自然語仕様から代数的仕様への変換における辞書項目生成の支援
- 多重文脈自由文法の認識問題について
- 拡張有限状態機械でモデル化したOSIセションプロトコルの検証
- 優先サービスを含む通信プロトコルの安全性の検証
- 多重文脈自由文法の所属問題に対する並列アルゴリズム(計算および計算量理論とその周辺)
- 通信プロトコルの自然語仕様から代数的仕様への変換における文章間の依存関係の解析
- 多重文脈自由文法のある部分クラスに対する効率の良い構文解析法について
- 自然語仕様から代数的仕様への,文脈を考慮した変換 : OSIセション層プロトコル仕様を例にして
- On Operational Semantics of Congruence Relation Defined in Algebraic Language ASL/$^\ast$
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- XMLスキーマで定義された型とXPath式との対応の解析手法
- ユーザ指定関係に基づいた情報保存を満たすXMLスキーマ進化
- XMLデータベースにおける表現能力を保存したスキーマ更新操作(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- XMLスキーマで定義された型と XPath 式との対応の解析手法
- 抽象的順序機械型代数的仕様からのドキュメント生成システム
- 空調機用マイコンソフトの形式的仕様記述と検証法について
- データマイニングに要する計算量に関する一考察
- タプル間の依存関係を表現できる確率的データベースモデルの提案
- 無閉路オブジェクト指向データベーススキーマにおける型検査問題の計算量
- オブジェクト指向データベースにおける型検査問題の計算量
- オブジェクト指向データベースにおける型検査問題の計算量
- マルチエージェント環境における時刻の前後関係に関する推論問題
- DTD存在下での否定を含まないXPathクエリの恒真性判定
- オブジェクト指向データベースにおけるインスタンスの内容に依存したアクセス権モデルの設計 (時空間データベースおよび一般)
- オブジェクト指向データベーススキーマにおけるセキュリティフロー検出の形式的手法
- オブジェクト指向データベースにおけるデータ漏洩検出問題に関する考察
- オブジェクト指向データベースにおけるアクセス権モデルの設計
- 仕事に対するエージェント集合割り当て問題の近似アルゴリズム
- 2本の時間軸間の時間的推論
- 仕事に対するエージェント集合割り当て問題の近似アルゴリズム
- オブジェクト指向データベースにおける質問のアクセス権分析
- Type Consistency Problems for Queries in Object-Oriented Databases
- オーエンス・ルイス : アンビエント環境制御を用いた知的オフィスチェアの提案(アンビエントインテリジェンス技術とその応用)
- オブジェクト指向データベースにおける質問の型検査問題
- オブジェクト指向データベースプログラムにおける型検査のアクセス制御への応用
- Combining the tractability of duplicate-free DTDs and disjunction-capsuled DTDs for XPath satisfiability with sibling axes (ソフトウェアサイエンス)
- 決定性線形トップダウン木変換器における問合せ保存の決定可能性 (ソフトウェアサイエンス)
- 兄弟軸をもつXPath充足可能性問題に対するduplicate-free DTDとdisjunction-capsuled DTDの多項式時間可解性の融合
- 決定性線形トップダウン木変換器における問合せ保存の決定可能性