Single-view determinacy and rewriting completeness for a fragment of XPath queries

Lixiao Zheng, Shuai Ma, Xiangyu Luo, Tiejun Ma

Abstract

XPath 查询语句的视图确定性和重写完全性问题。 证明出该类 XPath 语句的视图确定性问题是 coNP 难的, 并且该类语句是重写不完全的。 进而从语义和语法两个角度给出视图 V 确定查询 Q 的一系列必要条件, 以及一个判定视图确定性问题的非完全算法。 证明出对于一类特殊的 XPath 子类, 即只含有通配符和分支操作的 XPath 子类, 视图确定性问题可以在多项式时间内判定。 同时指出该子类的重写完全语言, 并给出一个从视图中计算查询结果的有效方法。
BibTeX
@article{zheng2016single,
  author = {Lixiao Zheng and Shuai Ma and Xiangyu Luo and Tiejun Ma},
  title = {{Single-view determinacy and rewriting completeness for a fragment of XPath queries}},
  journal = {Science China Information Sciences},
  year = {2016},
  doi = {10.1007/s11432-016-5603-z},
}

Loading related content...

Figure