Yolanda García Ruiz Facultad de Informática - UCM

The purpose of this thesis is to design and develop techniques for detecting and diagnosing errors in the field of databases, and in particular in the case of queries to databases. In order to help in the task of detecting errors, we develop techniques for automatically generating test cases. These test cases are considered as valid database instances which allow to the user easily checking the correctness of the query results. We propose to apply techniques related to declarative debugging for diagnosing errors. These techniques are based on the exploration of a suitable structure that represent the erroneous computation. This structure contains information about the final result and also the information about all intermediate results. For locating the cause of the error, the debugger asks to an oracle about the expected results.

In the field of databases, we have focused on deductive databases, relational databases and semistructured databases. The main contributions of this thesis can be summarized as follows:

• Firstly, we apply declarative debugging to Datalog programs. The debugger detects incorrect fragments of code starting from an unexpected answer. During the theoretical study of Datalog, its semantics and its computation mechanism, we have found that the traditional errors considered usually in logic programming are not enough in the case of Datalog where a new kind of error, the incomplete sets of predicates, can occur. Due to the set-oriented nature of Datalog computations, the declarative debugging schema used traditionally in logic programs is not appropriate for Datalog Programs. Therefore, we define a new instance based on a suitable structure for representing the computation mechanism of Datalog. This is a novelty w.r.t. others works related to declarative debugging of logic programs. In particular we have found that recursive computations (and thus computations associated to incomplete sets of predicates) are not easily represented by computations trees, the structure employed usually in declarative debugging. Thus, we propose to use graphs for representing the computations. In our proposed computation graphs incomplete set of predicates are represented naturally, given raise to buggy circuits.

  The theoretical ideas propose solid foundations for the debugging of Datalog programs and have been set in practice by developing a declarative debugger for the Datalog system DES. The debugger allows diagnosing both missing and wrong answers, which constitute all the possible errors symptoms of a Datalog program.

• Next, we discuss the problem of checking correlated SQL queries. Firstly we present a general framework for generating SQL query test cases using Constraint Logic Programming. Given a database schema and a SQL view defined in terms of other views and schema tables, our technique generates automatically a set of finite domain constraints whose solutions constitute the test database instances. We have formally defined the algorithm for producing the constraints, and we have proven the soundness and correctness of the technique w.r.t. the semantics of Extended Relational Algebra. Regarding the coverage criteria for testing SQL queries, we have considered a simple criterion namely the predicate coverage criterium. A prototype of generator has been implemented in an available tool covering a wide range of SQL queries, including views, subqueries, aggregates and set operations.

  Secondly, we propose using algorithmic debugging for finding errors in systems involving several SQL views and we present two techniques: The first one is based on the navigation of a suitable computation tree corresponding to some view returning some unexpected result. This tree contains the computed answer associated with every intermediate relation, asking the user whether this answer is expected or not. The debugger ends when a buggy node, i.e., a nonvalid node with valid children, is found. We prove formally that every buggy node corresponds to an erroneous relation, and that every computation tree with a nonvalid root contains some buggy node. The results are established in the context of the Extended Relational Algebra. The main criticism that can be leveled at this proposal is that it can be difficult for the user to check the validity of the intermediate results. Indeed, the results returned by SQL views can contain hundreds or thousands of tuples. The second technique for debugging SQL views refines the first one by taking into account a more detailed information; the process allows the user to provide information about the type of the error and the debugger is guided by this information. Using a technique similar to dynamic slicing, we concentrate only in those tuples produced by the intermediate relations that are relevant for the error. The proposed technique does not use computation trees explicitly. Instead, the logical relations among the nodes of the tree are represented by logic clauses that also contain the information extracted from the specific questions provided by the user. We use a dynamic Prolog program in order to represent both the computation tree and the user information. The atoms in the body of the clauses correspond to questions that the user must answer in order to detect an incorrect relation. The resulting logic program is executed by selecting at each step the unsolved atom that yields the simplest question, repeating the process until an erroneous relation is detected. We have proven the correctness and the completeness of the proposal.

  Both proposals have been implemented in a working prototype included in the Datalog system DES.

• Finally, we show a framework that allows the user testing XPath and XQuery queries. In this case, we have chosen to represent both languages in the funcional-logic language Toy. The effort for embedding XPath and XQuery in Toy is rewarded due to the simplicity for generating test cases automatically when possible, which is useful for testing the query, or even for helping to find the error in the query. In the case of XPath, queries are represented in this setting by non-deterministic higher-order expressions, thus becoming first-class citizens of the language that can be readily extended and adapted by the programmer. The possibility of including higher-orderpatterns in Toy allow us to consider expressions that are not yet reducible as patterns. This means in our case that XPath expressions can be considered at the same time executable code (when applied to an input XML document), or data structures when considered as higher-order patterns. This powerful characteristic of the language is heavily used in our proposals for debugging wrong and missing answers. The use of non-deterministicfunctions in Toy allow us to define easily the XPath framework, and are also useful for tracing wrong answers, where only those parts of the computation that produce a particular fragment of the answer are required. The use of logic variables, specially when used in generate and testexpressions are very suitable for obtaining the values of intermediate computations, and in our case also for guessing values in the debugging of missing answers. In the case of XQuery, although only a small subset of XQuery consisting of for, where/ifand returnstatements has been considered, the users of Toy can now perform simple queries typical of database queries such as joinoperations. The embedding has respected the declarative nature of Toy, and we have provided the soundness of the approach with respect to the operational semantics of XQuery.