Dan Olteanu
ABSTRACT
We introduce a representation system for relational data based on algebraic factorisation using distributivity of product over union and commutativity of product and union.
We give two characterisations of conjunctive queries based on factorisations of their results whose nesting structure is defined by so-called factorisation trees.
The first characterisation concerns sizes of factorised representations. For any query, we derive a size bound that is asymptotically tight within our class of factorisations.
We also characterise the queries by tight bounds on the readability of the provenance of result tuples and define syntactically the class of queries with bounded readability.
- A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. In Foundations of Computer Science (FOCS), 2008. Google Scholar
Digital Library
- N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. VLDB Journal, 16(4), 2007. Google ScholarDigital Library
- K. M. Elbassioni, K. Makino, and I. Rauf. On the readability of monotone boolean formulae. In International Computing and Combinatorics Conference (COCOON), 2009. Google ScholarDigital Library
- M. C. Golumbic, A. Mintz, and U. Rotics. An improvement on the complexity of factoring read-once boolean functions. Discrete Applied Mathematics, 156(10), 2008. Google ScholarDigital Library
- M. C. Golumbic, U. N. Peled, and U. Rotics. Chain graphs have unbounded readability. Technical report, University of Haifa, 2006.Google Scholar
- G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Principles of Database Systems (PODS), 1999. Google ScholarDigital Library
- G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive queries. Journal of ACM, 48, 2001. Google ScholarDigital Library
- T. J. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In Principles of Database Systems (PODS), 2007. Google ScholarDigital Library
- M. Grohe, Y. Gurevich, D. Leinders, N. Schweikardt, J. Tyszkiewicz, and J. V. den Bussche. Database query processing using finite cursor machines. Theory of Computing Systems, 44(4), 2009. Google ScholarDigital Library
- M. Grohe and D. Marx. Constraint solving via fractional edge covers. In Symposium on Discrete Algorithms (SODA), 2006. Google ScholarDigital Library
- M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive queries tractable? In Symposium on Theory of Computing (STOC), 2001. Google ScholarDigital Library
- T. Imielinski and W. Lipski. Incomplete information in relational databases. Journal of ACM, 31(4), 1984. Google ScholarDigital Library
- P. Koutris and D. Suciu. Parallel evaluation of conjunctive queries. In Principles of Database Systems (PODS), 2011. Google ScholarDigital Library
- D. Marx. Approximating fractional hypertree width. In Symposium on Discrete Algorithms (SODA), 2009. Google ScholarDigital Library
- D. Olteanu and J. Huang. Using obdds for efficient query evaluation on probabilistic databases. In Scalable Uncertainty Management (SUM), 2008. Google ScholarDigital Library
- D. Olteanu, C. Koch, and L. Antova. World-set decompositions: Expressiveness and efficient algorithms. Theoretical Computer Science, 403(2--3), 2008. Google ScholarDigital Library
- D. Olteanu and J. Závodný. Factorised representations of query results. Technical report, Oxford, April 2011. http://arxiv.org/abs/1104.0867.Google Scholar
- D. Olteanu and J. Závodný. On factorisation of provenance polynomials. In Theory and Practice of Provenance (TaPP), 2011.Google Scholar
- N. Robertson and P. Seymour. Graph minors, i. excluding a forest. Journal of Combinatorial Theory, Series B, 35(1), 1983.Google ScholarCross Ref
- D. Suciu, D. Olteanu, C. Ré, and C. Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. Google ScholarDigital Library
- S. Vadhan. The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM Journal on Computing, 32(2), 2001. Google ScholarDigital Library
Index Terms
- Factorised representations of query results: size bounds and readability
Recommendations
Size Bounds for Factorised Representations of Query Results
We study two succinct representation systems for relational data based on relational algebra expressions with unions, Cartesian products, and singleton relations: f-representations, which employ algebraic factorisation using distributivity of product ...
Size and treewidth bounds for conjunctive queries
PODS '09: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsThis paper provides new worst-case bounds for the size and treewith of the result Q(D) of a conjunctive query Q to a database D. We derive bounds for the result size |Q(D)| in terms of structural properties of Q, both in the absence and in the presence ...
Efficient approximations of conjunctive queries
PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database SystemsWhen finding exact answers to a query over a large database is infeasible, it is natural to approximate the query by a more efficient one that comes from a class with good bounds on the complexity of query evaluation. In this paper we study such ...
Comments