Lossless Regular Views

Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2002). 2002.

If the only information we have on a certain database is through a set of views, the question arises of whether this is sufficient to answer completely a given query. We say that the set of views is lossless with respect to the query, if, no matter what the database is, we can answer the query by solely relying on the content of the views. The question of losslessness has various applications, for example in query optimization, mobile computing, data warehousing, and data integration. We study this problem in a context where the database is semistructured, and both the query and the views are expressed as regular path queries. The form of recursion present in this class prevents us from applying known results to our case. We first address the problem of checking losslessness in the case where the views are materialized. The fact that we have the view extensions available makes this case solvable by extending known techniques. We then study a more complex version of the problem, namely the one where we abstract from the specific view extension. More precisely, we address the problem of checking whether, for every database, the answer to the query over such a database can be obtained by relying only on the view extensions. We show that the problem is solvable by utilizing, via automata-theoretic techniques, the known connection between view-based query answering and constraint satisfaction. We also investigate the computational complexity of both versions of the problem.

@inproceedings{PODS-2002,
   title = "Lossless Regular Views",
   year = "2002",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   booktitle = "Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on
Principles of Database Systems (PODS 2002)",
   pages = "247--258",
   doi = "10.1145/543613.543646",
}