Many database applications face the problem of querying incomplete data. In such scenarios, certain answers are a principled semantics of query answering. Unfortunately, the computation of certain query answers is a coNP-hard problem. To make query answering feasible in practice, recent research has focused on developing polynomial time algorithms computing a sound (but possibly incomplete) set of certain answers. In this paper we present a system prototype implementing a suite of algorithms to compute sound sets of certain answers. The central tools used by our system are conditional tables and the conditional evaluation of relation algebra. Di erent evaluation strategies can be applied, with more accurate ones having higher complexity, but returning more certain answers, thereby enabling users to choose the technique that best meets their needs in terms of balance between e ciency and quality of the results.
Incomplete information arises in many database applications, such as ontological
reasoning [
A principled semantics of query answering over incomplete databases are
certain answers, which are query answers that are obtained from all the
complete databases represented by an incomplete database [
Example 1. Consider the database D consisting of the three unary relations P (Person), S (Student) and E (Employee) reported below, where ? is a null value.
P john mary
E john ?
S mary bob Copyright c 2019 for the individual papers by the papers authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy. Under the missing value interpretation of nulls (i.e., a value for ? exists but is unknown), D represents all the databases obtained by replacing ? with an actual value.
A certain answer to a query is a tuple that is an answer to the query for every database represented by D. For instance, consider the query asking for the people who are not employees and students, which can be expressed in relational algebra as P (E \ S). The certain answers to the query are fhjohnig, because no matter how ? is replaced, hjohni is always a query answer.
For databases containing (labeled) nulls, certain answers to positive queries can be easily computed in polynomial time as follows: rst a \standard" evaluation (that is, treating nulls as standard constants) is applied; then tuples with nulls in the result of the rst step are discarded and the remaining tuples are the certain answers to the query. However, for more general queries with negation the problem of computing certain answers becomes coNP-hard.
To make query answering feasible in practice, one might resort to SQL's evaluation, but unfortunately, the way SQL behaves in the presence of nulls may result in wrong answers.
Speci cally, as evidenced in [
The experimental analysis in [
Example 2. Consider again the database D of Example 1. There are no certain answers to the query P E, as the query answers are the empty set when ? is replaced with mary.
Assuming that P and E's attribute is called name, the same query can be expressed in SQL as follows:
SELECT P.name FROM P WHERE NOT EXISTS (
SELECT * FROM E
WHERE P.name = E.name )
The evaluation of the SQL query above returns hmaryi, which is not a certain answer. The problem with the SQL semantics is that every comparison involving at least one null evaluates to the truth value unknown, then 3-valued logic is used to evaluate the classical logical connectives (AND, OR, NOT ), and eventually only those tuples whose condition evaluates to true are kept.
Going back to the query above, for the rst tuple of P, namely john, the nested subquery nds the same tuple in E, and thus john is not returned.
For the second tuple of P, namely mary, the nested subquery gives the empty set and thus hmaryi is returned by the overall query. The reason why the nested subquery returns the empty set when mary is considered is that mary is compared with john and the comparison evaluates to false, and mary is compared with ? and the comparison evaluates to unknown (because a null is involved). Thus, there is no tuple of E for which the comparison evaluates to true and the nested subquery returns the empty set.
Thus, on the one hand, SQL's evaluation is e cient but awed, on the other
hand, certain answers are a principled semantics but with high complexity. To
deal with this issue, there has been recent work on evaluation algorithms with
correctness guarantees, that is, techniques providing a sound but possibly
incomplete set of certain answers [
We have developed novel evaluation algorithms with correctness guarantees
leveraging conditional tables and the conditional evaluation of relational
algebra [
The basic idea is illustrated in the following example.
Example 3. Consider again the database and the query of Example 1. The conditional evaluation of the query is carried out by applying the \conditional" counterpart of each relational algebra operator. Rather than returning a set of tuples, the conditional evaluation of a relational algebra operator returns \conditional tuples", that is, pairs of the form ht; 'i, where t is a regular tuple and ' is an expression stating under which conditions t can be derived.
Regarding the query of Example 1, rst the conditional evaluation of E \ S is performed, which gives the conditional tuples h?; '1i and h?; '2i, where '1 is the condition (? = mary) and '2 is the condition (? = bob). This intuitively means that the tuple h?i is derived when ? is mary or bob.
Then, the conditional evaluation of the di erence operator is carried out, yielding the conditional tuples hjohn; '0i and hmary; '00i where '0 and '00 are the following conditions: '0 = :((john = ?) ^ (? = mary)) ^ :((john = ?) ^ (? = bob)); '00 = :((mary = ?) ^ (? = mary)) ^ :((mary = ?) ^ (? = bob)): This is the result of the conditional evaluation of the whole query.
Conditions are valuable information that can be exploited to determine which tuples are certain answers. As already mentioned, for a conditional tuple ht; 'i, Query
DB Evalua0on Algorithm
(Approximate)
Certain Query Answers
Evalua0on Algorithms’ Engine Naive
Semi-Naive
Lazy
Aware
DB the expression ' says under which condition t can be derived. By condition evaluation we mean a way of associating ' with a truth value (true, false, or unknown). The aim is to ensure that if ' evaluates to true, then t is a certain answer. For instance, from an analysis of '0 in Example 3 above, one can realize that the condition is always true (i.e., it holds for every possible value ? stands for), and thus hjohni is a certain answer.
Tuples' conditions can be evaluated in di erent ways: for instance, an eager strategy consists in evaluating conditions right after each relational algebra operator has been evaluated, while an opposite approach consists in evaluating conditions at the very end, that is, after the entire relational algebra query has been evaluated.
We have developed four di erent strategies leading to di erent evaluation
algorithms, called naive, semi-naive, lazy, and aware evaluations. They have been
implemented in the ACID system [
The ACID system has been implemented in Java. The system architecture is depicted in Figure 1.
There are three main components: a graphical user interface (GUI), the evaluation algorithms' engine, and the database.
The GUI allows user to specify the query to be evaluated, the database, and the type of evaluation to be performed, that is, the approximation algorithm to be applied. The GUI displays the result of evaluating the speci ed query over the provided database according to the chosen evaluation algorithm. Di erent lters can be applied to the result (more details are discussed in the next section).
The system's engine supports the four evaluation algorithms mentioned in the previous section, with the naive algorithm being the most e cient but the least accurate one, and the aware algorithm being the most accurate but the least e cient one. The basic ideas of the approximation algorithms are as follows: { The naive evaluation evaluates tuples' conditions right after each relational algebra operator has been applied, using three-valued logic. { The semi-naive evaluation behaves like the naive one, but it better exploits equalities in conditions (by propagating values into tuples and conditions) to provide more accurate results. { The lazy evaluation improves upon the semi-naive one by postponing conditions' evaluation until the set di erence operator is encountered in the query. { The aware evaluation provides even more accurate results and behaves as follows: it performs the conditional evaluation of the entire query, then it uses a set of axioms to \simplify" conditions, and eventually it evaluates (simpli ed) tuples' conditions.
The ACID system manages relational databases possibly containing labeled
nulls (in the literature, they have been called naive tables, V-tables, and
etables [
The GUI provides information on the query, the database, and the evaluation strategy to the engine, which computes the approximate certain answers accessing the database. After the evaluation has been carried out, the engine returns the result to the GUI.
The ACID system provides also an API which allow third party applications to interact with the system.
We now go into the details of how to interact with the ACID system (cf. Figure 2).
A typical interaction with the system involves the following steps: 1. The user speci es the input databases. Speci cally, for each table in the database, its location in the le system is provided. Tables are supposed to be in csv format. 2. The user speci es the query to be evaluated using standard SQL syntax.
Queries can be loaded from and saved to les. 3. The user speci es the evaluation strategy that has to be applied to evaluate the query (indeed, the system supports also the \standard" evaluation mentioned in the introduction and the conditional evaluation of a query). 4. After the evaluation has been launched and has nished, the result and statistics are displayed. Speci cally, the result is a set of a tuples, where each tuple is associated with a condition that is either true or unknown. Tuples associated with true are guaranteed to be certain answers to the input query. The result can be ltered with respect to the truth value of the tuples, thus displaying only true or only unknown tuples. The total number of true (resp. unknown) tuples is displayed as well as the execution time. Results can be saved to les. With the same query and database, moving to more accurate strategie, that is, from the naive (resp. semi-naive, lazy) evaluation to the semi-naive (lazy, aware) one, users can see better results, that is, more tuples with condition true (i.e., more certain answers), but running times might get higher.
In general, using the system and analyzing the query syntax, users can gure out the strategy that is best suited for their purposes.
As an example, Table 1 reports the execution time, the number of true and unknown answers for three sample queries over a database with the same schema of the one in Example 1, with 1000 tuples per relation and 10% of nulls (randomly generated).
The queries are: { Qsn = E { Qlazy = P $1=c(S), (E \ ( $16=c(S))), and where c is a value randomly chosen from those in S.
The purpose of the rst scenario is to exhibit a query (namely, Qsn ) that shows the bene ts of going from the naive to the semi-naive evaluation|notice that, in this case, there is no bene t in applying the lazy or aware evaluation, as the structure of the query does not have features that can be exploited by them.
Likewise, the purpose of the second and third scenarios is to show the advantage of using the lazy (resp. aware) evaluation rather than the semi-naive (resp. lazy) one. 4
Certain answers are a principled manner to answer queries on incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on developing polynomial time algorithms providing under-approximations. Leveraging conditional tables, we have developed a suite of novel approximation algorithms.
We have implemented them in the ACID system, which allows users to query incomplete information and get approximate answers with the exibility of choosing the technique that best meets their needs in terms of balance between e ciency and quality of the result's approximation.