Querying data sources that export infinite sets of views
type: Item
instance of: scholarly article
title: Querying data sources that export infinite sets of views
zbMATH Open document ID: 1263.68048
author: Bogdan Cautis
author: Alin Deutsch
author: Nicola Onose
published in: Theory of Computing Systems
publication date: 2011-10-11T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
review text: 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…
reviewed by: Jaroslav Pokorný
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5956665
zbMATH Keywords: quering data sources
zbMATH Keywords: conjunctive queries
zbMATH Keywords: DATALOG
zbMATH Keywords: integrity constraints
zbMATH Keywords: expressibility
zbMATH Keywords: support
MaRDI profile type: Publication
OpenAlex ID: W1989045705
cites work: Q4864249
cites work: Rewriting queries using views in the presence of arithmetic comparisons
cites work: Q4414537
cites work: Database Theory - ICDT 2005
cites work: Q4414536
cites work: Undecidable optimization problems for database logic programs
cites work: Answering queries using limited external query processors
cites work: Semantic query optimization in the presence of types
cites work: Q3862379
cites work: Expressive capabilities description languages and query rewriting algorithms
DOI: 10.1007/S00224-010-9293-4
description: scientific article; zbMATH DE number 5956665