Erich Grädel
Yuri Gurevich
- 1.E. Gr~idel and Y. Gurevich, Metafinite Model Theory, Information and Computation 140 (1998), 26-81. Google Scholar
Digital Library
- 2.G. Hirseh, The Reliability of Queries, Diploma Thesis (P~WTH-Aaehen, 1998).Google Scholar
- 3.D. Johnson, A Catalo9 of Complexly Classes, in: J. van Leeuven (Ed.), Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, Elseviex/MIT Press (1990), 67-161. Google ScholarDigital Library
- 4.tL Karp and M. Luby, Monte Carlo algorithms for enumeration and reliability problems, Proceedings of the 24th Symposium on Foundations of Computer Science FOCS 1983, 56-64.Google Scholar
- 5.V. Lakshmanan and F. Sadri, Probabilistic deductive databases, Proceedings of the international Logic Programming Symposium, MIT Press (1994), 197-207. Google ScholarDigital Library
- 6.V. Lakshmanan and V. Subrahmanian, Probview, A flexible probabilistie database system, ACM Transactions on Database Systems 22 (1997), 419-469. Google ScholarDigital Library
- 7.C. Papadimitriou, Computational Complexity, Addison-Wesley (1994).Google Scholar
- 8.K. Regan and T. Schwentick, On the Power of One Bit of a #P Function, Proceedings of the Fourth Italian Conference on Theoretical Computer Science (1992), 317-329.Google Scholar
- 9.M. de Rougemont, The reliability of queries, Proc. 14th ACM Syrup. on Principles of Database Systems PODS (1995), 286-29~. Google ScholarDigital Library
- 10.V. Subrahmanian, Stable semantics for probabilistic deductive databases, information and Computation 110(1) (1994), 42-83. Google ScholarDigital Library
- 11.L. Valiant, The complexity of enumeration and reliabil. ity problems, SIAM J. Computing 8 (1979), 410-421.Google ScholarDigital Library
- 12.K. Wagner, Some observations on the connection between counting and recursion, Theoretical Computer Science 47' (1986),131-147. Google ScholarDigital Library
- 13.E. Zim~nyi, Query evaluation on probabilistic relational databases, Theoretical Computer Science 171 (1997), 179-219. Google ScholarDigital Library
Index Terms
- The complexity of query reliability
Recommendations
Data complexity of query answering in description logics
KR'06: Proceedings of the Tenth International Conference on Principles of Knowledge Representation and ReasoningIn this paper we study data complexity of answering conjunctive queries over Description Logic knowledge bases constituted by an ABox and a TBox. In particular, we are interested in characterizing the FOL-reducibility and the polynomial tractability ...
Data complexity of query answering in description logics
In this paper we study data complexity of answering conjunctive queries over description logic (DL) knowledge bases constituted by a TBox and an ABox. In particular, we are interested in characterizing the FOL-rewritability and the polynomial ...
View-based query containment
PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsQuery containment is the problem of checking whether for all databases the answer to a query is a subset of the answer to a second query. In several data management tasks, such as data integration, mobile computing, etc., the data of interest are only ...
Comments