图是数据结构中重要的组成部分。在图模型中,点代表事物,边代表事物之间的关系。图模型有着非常广泛的应用背景,如生物网络、web网络、计算机网络等。近几年来,随着互联网的发展,各种网络内容成指数级增长,对其进行快速有效地分析与查询是研究重点。其中许多问题都可以用图模型来解决,这使得图数据分析成为一个研究热点。在图数据分析中,可达性查询是一项基本的查询。而在众多的可达性查询方法中,区间标记索引近来备受关注。然而,当图发生更新时,传统的区间标记索引算法并不能迅速地更新索引。本文研究了基于区间标记索引的可达性查询,利用预留空间的思想提出了一种可以动态更新区间索引的方法,又结合了二进制索引树以使可达性查询代价降低。该方法能针对不同的图更新情形进行处理。实验部分验证了本文提出的动态更新算法能有效支持区间索引的更新。另外,目前企业的存储数据量迅速增长,一些中小型企业处理并非核心业务的数据代价太高,这时将数据库外包也成为企业的合理选择。随着图数据的发展与应用,图数据的外包查询验证成为一个研究热点。然而针对图数据的外包文献相对较少,主要集中在子图相似性查询等领域。截止到本文完稿,可达性查询尚无已发表的查询验证机制。本文针对区间索引方式的可达性查询设计了验证信息及查询验证方案,使得用户能够在外包数据库的背景下验证数据的正确性及完整性。本文结合了MB-tree等验证索引方式,简化了验证对象的大小,降低了验证数据量。本文的验证索引数据结构能够合理的应用于外包数据库中。实验评估部分显示该方案的代价较小,能够适用于可达性查询量较大的应用背景。