Querying data sources that export infinite sets of views (Q639847)

The authors study querying data sources, e.g. on the Web, with restricted query capabilities, typically equivalent to a subset of conjunctive queries. Such queries accepted by a source are called views in the paper. More complex views can be generated by a DATALOG program, even in a recursive way. A program is said to generate these views. Two problems are interesting here: if a query \(Q\) is expressible by the program \(P\), i.e. it is equivalent to some view generated by \(P\), and if \(Q\) is supported by \(P\), i.e. if it has an equivalent rewriting \(R\) using some finite set of views generated by \(P\). Both problems were shown to be decidable in [\textit{A. Z. Levy}, \textit{A. Rajaraman} and \textit{J. D. Ullman}, J. Comput. Syst. Sci. 58, No. 1, 69--82 (1999; Zbl 0938.68031)] without considering any constraints satisfied by the source. The work [\textit{V. Vassalos} and \textit{Y. Papakonstantinou}, J. Log. Program. 43, No. 1, 75--122 (2000; Zbl 0949.68064)] improves results achieved in [Levy et al., loc. cit.]. Here the authors investigate the effect of source constraints for both problems. Section 2 contains notions and definitions. As constraints, well-known embedded dependencies are considered. Section 3 is devoted to the relationship between expressibility and support. The authors prove that these notions are inter-reducible in PTIME in both the absence and presence of constraints. Section 4 shows restrictions under which the problems of expressibility and support are decidable under constraints. Particularly, the notion of weakly acyclic set of embedded dependencies, explained in Appendix A, is needed here. In practice it means decidability in situations where we use weakly acyclic sets of keys and foreign keys. Unfortunately, even slight relaxations to these restrictions lead to undecidability. The fact that the two studied problems are in general undecidable is shown in Section 6. Section 5 contains a sound algorithm for testing support in the case of general constraints. Section 6 maps boundaries of decidability for the problem of expressibility and support. In Section 7, these solutions are extended to the case when sources implement parameterized queries. In Section 8, the authors shortly summarize related works and in Section 9 they present some conclusions.