Abstract

Most of the previously known evaluation methods for deductive databases are either breadth-first or depth-first (and recursive). There are cases when these strategies are not the best ones. It is desirable to have an evaluation framework for stratified DatalogN that is goal-driven, set-at-a-time (as opposed to tuple-at-a-time) and adjustable w.r.t. flow-of-control strategies. These properties are important for efficient query evaluation on large and complex deductive databases. In this paper, by incorporating stratified negation into so-called query-subquery nets, we develop an evaluation framework, called QSQNSTR, with such properties for evaluating queries to stratified DatalogN databases. A variety of flow-of-control strategies can be used for QSQNSTR. The generic evaluation method QSQNSTR for stratified DatalogN is sound, complete and has a PTIME data complexity.

Keywords

MSC

68N17

Cite this article

@article{cai-3249,
  author  = {Son Thanh Cao and Linh Anh Nguyen},
  title   = {Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases},
  journal = {Computing and Informatics},
  volume  = {38},
  number  = {1},
  pages   = {19--56},
  year    = {2019},
  issn    = {1335-9150},
  doi     = {10.31577/cai_2019_1_19}
}
Download .bib