Weitere Artikel dieser Ausgabe durch Wischen aufrufen
This work has been partially funded by the NSF awards IIS-1247469 and IIS-0911036, European Research Council under the FP7, ERC grant MoDaS, agreement 291071 and by the Israel Ministry of Science.
In this paper, we study the complexity of answering conjunctive queries (CQ) with inequalities (≠). In particular, we are interested in comparing the complexity of the query with and without inequalities. The main contribution of our work is a novel combinatorial technique that enables us to use any Select-Project-Join query plan for a given CQ without inequalities in answering the CQ with inequalities, with an additional factor in running time that only depends on the query. The key idea is to define a new projection operator, which keeps a small representation (independent of the size of the database) of the set of input tuples that map to each tuple in the output of the projection; this representation is used to evaluate all the inequalities in the query. Second, we generalize a result by Papadimitriou and Yannakakis (1997) and give an alternative algorithm based on the color-coding technique (2008) to evaluate a CQ with inequalities by using an algorithm for the CQ without inequalities. Third, we investigate the structure of the query graph, inequality graph, and the augmented query graph with inequalities, and show that even if the query and the inequality graphs have bounded treewidth, the augmented graph not only can have an unbounded treewidth but can also be NP-hard to evaluate. Further, we illustrate classes of queries and inequalities where the augmented graphs have unbounded treewidth, but the CQ with inequalities can be evaluated in poly-time. Finally, we give necessary properties and sufficient properties that allow a class of CQs to have poly-time combined complexity with respect to any inequality pattern. We also illustrate classes of queries where our query-plan-based technique outperforms the alternative approaches discussed in the paper.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases Addison-Wesley, 1995.
Afrati, F., Li, C., Mitra, P.: Answering Queries Using Views with Arithmetic Comparisons. PODS, 209–220 (2002).
Alon, N., Yuster, R., Zwick, U.: Color Coding. Encyclopedia of Algorithms. Edited by: Kao, M.Y. Springer (2008).
Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. FOCS 739–748, 2008.
Durand, A., Grandjean, E.: The complexity of acyclic conjunctive queries revisited coRR abs/cs/0605008, 2006.
Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions and Tractable Queries. PODS, 21–32 (1999).
Graham, M.: On the Universal Relation. Technical Report. University of Toronto, Ontario (1979).
Grohe, M., Marx, D.: Constraint Solving via Fractional Edge Covers. SODA, 289–298 (2006).
Khayyat, Z., Lucia, W., Singh, M., Ouzzani, M., Papotti, P., Quiané-Ruiz, J., Tang, N., Kalnis, P.: Lightning fast and space efficient inequality joins. PVLDB. 8 (13), 2074–2085 (2015). http://www.vldb.org/pvldb/vol8/p2074-khayyat.pdf.
Kolaitis, P.G., Martin, D.L., Thakur, M.N.: On the Complexity of the Containment Problem for Conjunctive Queries with Built-In Predicates. PODS, 197–204 (1998).
Koutris, P., Milo, T., Roy, S., Suciu, D.: Answering Conjunctive Queries with Inequalities. ICDT, 76–93 (2015).
Monien, B.: How to Find Long Paths Efficiently. Analysis and Design of Algorithms for Combinatorial Problems, North-Holland Mathematics Studies, vol. 109, pp. 239–254. North-Holland. Edited by: Ausiello, G., Lucertini, M. (1985).
Ngo, H.Q., Porat, E., Ré, C., Rudra, A.: Worst-Case Optimal Join Algorithms: [Extended Abstract]. PODS, 37–48 (2012).
Papadimitriou, C.H., Yannakakis, M.: On the Complexity of Database Queries. PODS, 12–19 (1997).
Veldhuizen, T.L.: Triejoin: a Simple, Worst-Case Optimal Join Algorithm. ICDT, 96–106 (2014).
Yannakakis, M.: Algorithms for Acyclic Database Schemes. VLDB, 82–94 (1981).
Yu, C., Ozsoyoglu, M.Z.: An Algorithm for Tree-Query Membership of a Distributed Query. COMPSAC, 306–312 (1979).
- Answering Conjunctive Queries with Inequalities
- Springer US
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia