Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM / IEEE Symposium on Logic in Computer Science (LICS)
This volume contains the proceedings of the Joint Meeting of the Twenty-Third Annual EACSL Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/ IEEE Symposium on Logic in Computer Science (LICS). CSL is the annual meeting of the European Association for Computer Science Logic (EACSL) intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science. LICS is an annual international forum on theoretical and practical topics in computer science that relate to logic. Every 3--4 years, LICS has been part of the Federated Logic Conference (FLoC). Given that FLoC was to be held as part of the Vienna Summer of Logic (VSL) during July 2014, the organizers of CSL and LICS have chosen to merge the 2014 editions of these meetings into a single event within FLoC and VSL. Thus, in 2014, the joint meeting had one program committee, one program, and one proceedings.
We investigate the succinctness problem for conjunctive query rewritings over OWL 2QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. We show that, over ontologies of depth 1, conjunctive queries have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, in the worst case, positive existential rewritings can be superpolynomial. Over ontologies of depth 2, positive existential and nonrecursive datalog rewritings of conjunctive queries can suffer an exponential blowup, while first-order rewritings can be superpolynomial unless NP ⊆ P/poly. We also analyse rewritings of tree-shaped queries over arbitrary ontologies and note that query entailment for such queries is fixed-parameter tractable.
Full 20-page version is available here: