Dynamic Query Optimization under Access Limitations and Dependencies

J. of Universal Computer Science. 15(1):33--62 2009.

Unlike relational tables in a database, data sources on the Web typically can only be accessed in limited ways. In particular, some of the source fields may be required as input and thus need to be mandatorily filled in order to access the source. Answering queries over sources with access limitations is a complex task that requires a possibly recursive evaluation even when the query is non-recursive. After reviewing the main techniques for query answering in this context, in this article we consider the impact of functional and inclusion dependencies on dynamic query optimization under access limitations. In particular, we address the implication problem for functional dependencies and simple full-width inclusion dependencies, and prove that it can be decided in polynomial time. Then we provide necessary and sufficient conditions, based on the dependencies together with the data retrieved at a certain step of the query answering process, that allow avoiding unnecessary accesses to the sources.

@article{JUCS-2009,
   title = "Dynamic Query Optimization under Access Limitations and
Dependencies",
   year = "2009",
   author = "Andrea Calì and Diego Calvanese and Davide
Martinenghi",
   journal = "J. of Universal Computer Science",
   pages = "33--62",
   number = "1",
   volume = "15",
   doi = "10.3217/jucs-015-01-0033",
}