RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Main page
About this project
Software
Classifications
Links
Terms of Use

Search papers
Search references

RSS
Current issues
Archive issues
What is RSS






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


CEUR Workshop Proceedings, 2013, Volume 1014, Pages 316–327 (Mi ceur2)  

Query Rewriting over Shallow Ontologies

S. Kikota, R. Kontchakova, V. Podolskiib, M. Zakharyascheva

a Department of Computer Science and Information Systems, Birkbeck, University of London, United Kingdom
b Steklov Mathematical Institute, Moscow, Russian Federation

Abstract: We investigate the size of rewritings of conjunctive queries over $OWL2QL$ ontologies of depth 1 and 2 by means of a new hypergraph formalism for computing Boolean functions. Both positive and negative results are obtained. All conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; treeshaped queries have polynomial-size positive existential rewritings; however, for some queries and ontologies of depth 1, positive existential rewritings can only be of superpolynomial size. Both positive existential and nonrecursive datalog rewritings of conjunctive queries and ontologies of depth 2 suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless $\mathrm{NP \subseteq P/poly}$.

Language:

Linking options:
  • http://mi.mathnet.ru/eng/ceur2

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:64

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020