Computing explanations for unlively queries in databases

ABSTRACT

A query is unlively if it always returns an empty answer. Debugging a database schema requires not only determining unlively queries, but also fixing them. To the best of our knowledge, the existing methods do not provide the designer with an explanation of why a query is not lively. In this paper, we propose a method for computing explanations that is independent of the particular method used to determine liveliness. It provides three levels of search: one explanation, a maximal set of non-overlapping explanations, and all explanations. The first two levels require only a linear number of calls to the underlying method. We also propose a filter to reduce the number of these calls, and experimentally compare our method with the best known method for finding unsatisfiable subsets of constraints.

REFERENCES

• 1: James Bailey, Peter J. Stuckey: Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization. Practical Aspects of Declarative Languages (PADL) 2005: 174--186.
• 2: Hendrik Decker , Ernest Teniente , Toni Urpí, How to Tackle Schema Validation by View Updating, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.535-549, March 25-29, 1996
• 3: Carles Farré , Ernest Teniente , Toni Urpí, Checking query containment with the CQC method, Data & Knowledge Engineering, v.53 n.2, p.163-223, May 2005 [doi>10.1016/j.datak.2004.08.002]
• 4: Alon Y. Halevy , Inderpal Singh Mumick , Yehoshua Sagiv , Oded Shmueli, Static analysis in datalog extensions, Journal of the ACM (JACM), v.48 n.5, p.971-1012, September 2001 [doi>10.1145/502102.502104]
• 5: The Mondial database http://www.dbis.informatik.uni-goettingen.de/Mondial/.
• 6: Stefan Schlobach, Ronald Cornet: Non-Standard Reasoning Services for the Debugging of Description Logic Terminologies. International Joint Conference on Artificial Intelligence (IJCAI) 2003: 355--362.
• 7: Ernest Teniente , Carles Farré , Toni Urpí , Carlos Beltrán , David Gañán, SVT: schema validation tool for microsoft SQL-server, Proceedings of the Thirtieth international conference on Very large data bases, p.1349-1352, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Verification

Keywords:
database schema validation, query liveliness