Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases
Keywords:Deductive databases, datalog with negation, query processing
AbstractMost 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.
Download data is not yet available.
How to Cite
Cao, S. T., & Nguyen, L. A. (2019). Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases. COMPUTING AND INFORMATICS, 38(1), 19–56. https://doi.org/10.31577/cai_2019_1_19