We study the data complexity of the modal query language MDatalog and its extension eMDatalog in basic modal logics. MDatalog is a modal extension of Datalog, while eMDatalog is the general modal Horn fragment with the allowedness condition. As the main results, we prove that the data complexity of MDatalog and eMDatalog in K4, KD4, and 54 is PSPACE-complete, in K is coNP-complete, and in KD, T, KB, KDB, and B is PTIME-complete.
展开▼
