Name
Title | ||
|---|---|---|
On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database Systems |
Abstract | ||
|---|---|---|
Satisfiability, equivalence, and implication problems involving conjunctive queries are important and widely encountered problems in database management systems. These problems need to be efficiently and effectively solved. In this paper, we consider queries which are conjunctions of the inequalities of the form (XopC), (XopY), and/or (XopY + C), where X and Y are two attributes, C is a constant, and op驴 {, 驴}. These types of inequalities are widely used in database systems, since the first type is a selection, the second type is a 驴-join, and the third type is a very popular clause in a deductive database system. The satisfiability, equivalence, and implication problems in the integer domain (for attributes and constants) have been shown to be NP-hard [20], [24]. However, we show that these problems can be solved efficiently in the real domain. The incorporation of the real domain is significant, because the real domain is practically and widely used in a database. Necessary and sufficient conditions and algorithms are presented. A novel concept of the "modulo closure" and a set of sound and complete axioms with respect to the "modulo closure" are also proposed to infer all correct and necessary inequalities from a given query. The proposed axioms generalize Ullman's axioms [27] where queries only consist of 驴-joins. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1109/69.536253 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
real domain,deductive database system,modulo closure,implication problems involving conjunctive,database system,database systems,proposed axiom,database management system,integer domain,complete axiom,necessary inequality,implication problem,cost function,computability,distributed databases,equivalence,conjunctive queries,relational databases,application software,computational complexity,arithmetic,database,np hard,satisfiability,helium | Integer,Discrete mathematics,Data mining,Conjunctive query,Relational database,Deductive database,Computer science,Axiom,Satisfiability,Equivalence (measure theory),Database,Computational complexity theory | Journal |
Volume | Issue | ISSN |
8 | 4 | 1041-4347 |
Citations | PageRank | References |
40 | 54.43 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sha Guo | 1 | 40 | 54.43 |
| Wei Sun | 2 | 40 | 54.43 |
| Mark A. Weiss | 3 | 99 | 131.43 |