Rewriting Conjunctive Queries over Description Logic Knowledge Bases View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Héctor Pérez-Urbina , Boris Motik , Ian Horrocks

ABSTRACT

We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for DL-Lite + ontologies, and use it to show that query answering in this setting is NLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language DL-Lite. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging from LogSpace to PTime-complete. More... »

PAGES

199-214

Book

TITLE

Semantics in Data and Knowledge Bases

ISBN

978-3-540-88593-1
978-3-540-88594-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-88594-8_11

DOI

http://dx.doi.org/10.1007/978-3-540-88594-8_11

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1014157585


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computing Laboratory, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Computing Laboratory, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "P\u00e9rez-Urbina", 
        "givenName": "H\u00e9ctor", 
        "id": "sg:person.013656450361.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013656450361.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computing Laboratory, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Computing Laboratory, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Motik", 
        "givenName": "Boris", 
        "id": "sg:person.07401076267.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computing Laboratory, University of Oxford, Oxford, UK", 
          "id": "http://www.grid.ac/institutes/grid.4991.5", 
          "name": [
            "Computing Laboratory, University of Oxford, Oxford, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Horrocks", 
        "givenName": "Ian", 
        "id": "sg:person.013100561643.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013100561643.19"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for DL-Lite\u2009+\u2009 ontologies, and use it to show that query answering in this setting is NLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language DL-Lite. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging from LogSpace to PTime-complete.", 
    "editor": [
      {
        "familyName": "Schewe", 
        "givenName": "Klaus-Dieter", 
        "type": "Person"
      }, 
      {
        "familyName": "Thalheim", 
        "givenName": "Bernhard", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-88594-8_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-88593-1", 
        "978-3-540-88594-8"
      ], 
      "name": "Semantics in Data and Knowledge Bases", 
      "type": "Book"
    }, 
    "keywords": [
      "DL-Lite", 
      "conjunctive queries", 
      "data complexity", 
      "information integration system", 
      "description logic knowledge bases", 
      "logic knowledge bases", 
      "description logic ontologies", 
      "query answering", 
      "input ontologies", 
      "DL language", 
      "knowledge bases", 
      "queries", 
      "integration system", 
      "ontology", 
      "algorithm", 
      "global view", 
      "extended version", 
      "complexity", 
      "answering", 
      "logspace", 
      "language", 
      "version", 
      "system", 
      "view", 
      "data", 
      "setting", 
      "respect", 
      "basis", 
      "problem", 
      "Logic ontology", 
      "resolution-based query", 
      "language DL-Lite"
    ], 
    "name": "Rewriting Conjunctive Queries over Description Logic Knowledge Bases", 
    "pagination": "199-214", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014157585"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-88594-8_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-88594-8_11", 
      "https://app.dimensions.ai/details/publication/pub.1014157585"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_85.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-88594-8_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88594-8_11'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88594-8_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88594-8_11'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88594-8_11'


 

This table displays all metadata directly associated to this object as RDF triples.

111 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-88594-8_11 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Ne58d9403e16c4258a9e51ba3ced01a28
4 schema:datePublished 2008
5 schema:datePublishedReg 2008-01-01
6 schema:description We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for DL-Lite +  ontologies, and use it to show that query answering in this setting is NLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language DL-Lite. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging from LogSpace to PTime-complete.
7 schema:editor N6d5db2ff458941d0beb2e4a2d386d959
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9d7295503c654742ac8863c592f48c91
12 schema:keywords DL language
13 DL-Lite
14 Logic ontology
15 algorithm
16 answering
17 basis
18 complexity
19 conjunctive queries
20 data
21 data complexity
22 description logic knowledge bases
23 description logic ontologies
24 extended version
25 global view
26 information integration system
27 input ontologies
28 integration system
29 knowledge bases
30 language
31 language DL-Lite
32 logic knowledge bases
33 logspace
34 ontology
35 problem
36 queries
37 query answering
38 resolution-based query
39 respect
40 setting
41 system
42 version
43 view
44 schema:name Rewriting Conjunctive Queries over Description Logic Knowledge Bases
45 schema:pagination 199-214
46 schema:productId N3975f3f0d09e4d99ac9e8dbcf56702c0
47 N5b8028f7794c4cf4acd8d04cf3a2a807
48 schema:publisher N803f8a2ea63c4a66b170675925599f5a
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014157585
50 https://doi.org/10.1007/978-3-540-88594-8_11
51 schema:sdDatePublished 2022-01-01T19:28
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N46fa03c2725940998c299a6df9b59bce
54 schema:url https://doi.org/10.1007/978-3-540-88594-8_11
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N3975f3f0d09e4d99ac9e8dbcf56702c0 schema:name doi
59 schema:value 10.1007/978-3-540-88594-8_11
60 rdf:type schema:PropertyValue
61 N46fa03c2725940998c299a6df9b59bce schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N4bc3c48371964b5c8484b7166492d446 rdf:first N59efa8821b614e6d80c8258c27afea07
64 rdf:rest rdf:nil
65 N59efa8821b614e6d80c8258c27afea07 schema:familyName Thalheim
66 schema:givenName Bernhard
67 rdf:type schema:Person
68 N5b8028f7794c4cf4acd8d04cf3a2a807 schema:name dimensions_id
69 schema:value pub.1014157585
70 rdf:type schema:PropertyValue
71 N6d5db2ff458941d0beb2e4a2d386d959 rdf:first N9928abba9c9945b4b32cff563a9f40fe
72 rdf:rest N4bc3c48371964b5c8484b7166492d446
73 N803f8a2ea63c4a66b170675925599f5a schema:name Springer Nature
74 rdf:type schema:Organisation
75 N988e9d4dcab34aedae52bfd2ec279e32 rdf:first sg:person.013100561643.19
76 rdf:rest rdf:nil
77 N9928abba9c9945b4b32cff563a9f40fe schema:familyName Schewe
78 schema:givenName Klaus-Dieter
79 rdf:type schema:Person
80 N9d7295503c654742ac8863c592f48c91 schema:isbn 978-3-540-88593-1
81 978-3-540-88594-8
82 schema:name Semantics in Data and Knowledge Bases
83 rdf:type schema:Book
84 Ne58d9403e16c4258a9e51ba3ced01a28 rdf:first sg:person.013656450361.35
85 rdf:rest Nf02ff0ef94784e559b02fd101478a330
86 Nf02ff0ef94784e559b02fd101478a330 rdf:first sg:person.07401076267.36
87 rdf:rest N988e9d4dcab34aedae52bfd2ec279e32
88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
89 schema:name Information and Computing Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information Systems
93 rdf:type schema:DefinedTerm
94 sg:person.013100561643.19 schema:affiliation grid-institutes:grid.4991.5
95 schema:familyName Horrocks
96 schema:givenName Ian
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013100561643.19
98 rdf:type schema:Person
99 sg:person.013656450361.35 schema:affiliation grid-institutes:grid.4991.5
100 schema:familyName Pérez-Urbina
101 schema:givenName Héctor
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013656450361.35
103 rdf:type schema:Person
104 sg:person.07401076267.36 schema:affiliation grid-institutes:grid.4991.5
105 schema:familyName Motik
106 schema:givenName Boris
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401076267.36
108 rdf:type schema:Person
109 grid-institutes:grid.4991.5 schema:alternateName Computing Laboratory, University of Oxford, Oxford, UK
110 schema:name Computing Laboratory, University of Oxford, Oxford, UK
111 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...