Cost Based Query Ordering over OWL Ontologies View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Ilianna Kollia , Birte Glimm

ABSTRACT

The paper presents an approach for cost-based query planning for SPARQL queries issued over an OWL ontology using the OWL Direct Semantics entailment regime of SPARQL 1.1. The costs are based on information about the instances of classes and properties that are extracted from a model abstraction built by an OWL reasoner. A static and a dynamic algorithm are presented which use these costs to find optimal or near optimal execution orders for the atoms of a query. For the dynamic case, we improve the performance by exploiting an individual clustering approach that allows for computing the cost functions based on one individual sample from a cluster. Our experimental study shows that the static ordering usually outperforms the dynamic one when accurate statistics are available. This changes, however, when the statistics are less accurate, e.g., due to non-deterministic reasoning decisions. More... »

PAGES

231-246

References to SciGraph publications

  • 2007-10. Optimizing Terminological Reasoning for Expressive Description Logics in JOURNAL OF AUTOMATED REASONING
  • 2006. Towards a Complete OWL Ontology Benchmark in THE SEMANTIC WEB: RESEARCH AND APPLICATIONS
  • 2008-08. On the Scalability of Description Logic Instance Retrieval in JOURNAL OF AUTOMATED REASONING
  • 1997-08. Heuristic and randomized optimization for the join ordering problem in THE VLDB JOURNAL
  • 2011. SPARQL Query Answering over OWL Ontologies in THE SEMANTIC WEB: RESEARCH AND APPLICATIONS
  • Book

    TITLE

    The Semantic Web – ISWC 2012

    ISBN

    978-3-642-35175-4
    978-3-642-35176-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-35176-1_15

    DOI

    http://dx.doi.org/10.1007/978-3-642-35176-1_15

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Ulm", 
              "id": "https://www.grid.ac/institutes/grid.6582.9", 
              "name": [
                "University of Ulm, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kollia", 
            "givenName": "Ilianna", 
            "id": "sg:person.016127671631.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016127671631.79"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Ulm", 
              "id": "https://www.grid.ac/institutes/grid.6582.9", 
              "name": [
                "University of Ulm, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Glimm", 
            "givenName": "Birte", 
            "id": "sg:person.015234565343.35", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015234565343.35"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.websem.2011.12.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000078513"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10817-007-9077-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001221517", 
              "https://doi.org/10.1007/s10817-007-9077-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10817-007-9077-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001221517", 
              "https://doi.org/10.1007/s10817-007-9077-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.websem.2007.03.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013524367"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1367497.1367578", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017249930"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21034-1_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027871510", 
              "https://doi.org/10.1007/978-3-642-21034-1_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21034-1_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027871510", 
              "https://doi.org/10.1007/978-3-642-21034-1_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10817-008-9104-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032965985", 
              "https://doi.org/10.1007/s10817-008-9104-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10817-008-9104-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032965985", 
              "https://doi.org/10.1007/s10817-008-9104-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s007780050040", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033408714", 
              "https://doi.org/10.1007/s007780050040"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11762256_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043896869", 
              "https://doi.org/10.1007/11762256_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11762256_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043896869", 
              "https://doi.org/10.1007/11762256_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.websem.2005.06.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045471388"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012", 
        "datePublishedReg": "2012-01-01", 
        "description": "The paper presents an approach for cost-based query planning for SPARQL queries issued over an OWL ontology using the OWL Direct Semantics entailment regime of SPARQL 1.1. The costs are based on information about the instances of classes and properties that are extracted from a model abstraction built by an OWL reasoner. A static and a dynamic algorithm are presented which use these costs to find optimal or near optimal execution orders for the atoms of a query. For the dynamic case, we improve the performance by exploiting an individual clustering approach that allows for computing the cost functions based on one individual sample from a cluster. Our experimental study shows that the static ordering usually outperforms the dynamic one when accurate statistics are available. This changes, however, when the statistics are less accurate, e.g., due to non-deterministic reasoning decisions.", 
        "editor": [
          {
            "familyName": "Cudr\u00e9-Mauroux", 
            "givenName": "Philippe", 
            "type": "Person"
          }, 
          {
            "familyName": "Heflin", 
            "givenName": "Jeff", 
            "type": "Person"
          }, 
          {
            "familyName": "Sirin", 
            "givenName": "Evren", 
            "type": "Person"
          }, 
          {
            "familyName": "Tudorache", 
            "givenName": "Tania", 
            "type": "Person"
          }, 
          {
            "familyName": "Euzenat", 
            "givenName": "J\u00e9r\u00f4me", 
            "type": "Person"
          }, 
          {
            "familyName": "Hauswirth", 
            "givenName": "Manfred", 
            "type": "Person"
          }, 
          {
            "familyName": "Parreira", 
            "givenName": "Josiane Xavier", 
            "type": "Person"
          }, 
          {
            "familyName": "Hendler", 
            "givenName": "Jim", 
            "type": "Person"
          }, 
          {
            "familyName": "Schreiber", 
            "givenName": "Guus", 
            "type": "Person"
          }, 
          {
            "familyName": "Bernstein", 
            "givenName": "Abraham", 
            "type": "Person"
          }, 
          {
            "familyName": "Blomqvist", 
            "givenName": "Eva", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-35176-1_15", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-35175-4", 
            "978-3-642-35176-1"
          ], 
          "name": "The Semantic Web \u2013 ISWC 2012", 
          "type": "Book"
        }, 
        "name": "Cost Based Query Ordering over OWL Ontologies", 
        "pagination": "231-246", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-35176-1_15"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "933e252831a06dfb90fc62f63cd676afdac8eff23c810e1ef5a2617daca9b5ec"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1030908178"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-35176-1_15", 
          "https://app.dimensions.ai/details/publication/pub.1030908178"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T18:11", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8681_00000262.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-35176-1_15"
      }
    ]
     

    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-642-35176-1_15'

    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-642-35176-1_15'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35176-1_15'

    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-642-35176-1_15'


     

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

    154 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-35176-1_15 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N420d621e65a34db19fe5ab68a138f7b8
    4 schema:citation sg:pub.10.1007/11762256_12
    5 sg:pub.10.1007/978-3-642-21034-1_26
    6 sg:pub.10.1007/s007780050040
    7 sg:pub.10.1007/s10817-007-9077-y
    8 sg:pub.10.1007/s10817-008-9104-7
    9 https://doi.org/10.1016/j.websem.2005.06.005
    10 https://doi.org/10.1016/j.websem.2007.03.004
    11 https://doi.org/10.1016/j.websem.2011.12.007
    12 https://doi.org/10.1145/1367497.1367578
    13 schema:datePublished 2012
    14 schema:datePublishedReg 2012-01-01
    15 schema:description The paper presents an approach for cost-based query planning for SPARQL queries issued over an OWL ontology using the OWL Direct Semantics entailment regime of SPARQL 1.1. The costs are based on information about the instances of classes and properties that are extracted from a model abstraction built by an OWL reasoner. A static and a dynamic algorithm are presented which use these costs to find optimal or near optimal execution orders for the atoms of a query. For the dynamic case, we improve the performance by exploiting an individual clustering approach that allows for computing the cost functions based on one individual sample from a cluster. Our experimental study shows that the static ordering usually outperforms the dynamic one when accurate statistics are available. This changes, however, when the statistics are less accurate, e.g., due to non-deterministic reasoning decisions.
    16 schema:editor Ne04f4ff5fdd84533bd6cc9cdf482d74b
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N8c3b30f81ed74ac3bcaf632bac354b53
    21 schema:name Cost Based Query Ordering over OWL Ontologies
    22 schema:pagination 231-246
    23 schema:productId N5e6f1d330d294b7f91095fb7d12cb827
    24 Nb6f3eed4e9954d4fb9285bf36b94f1d0
    25 Nf4af77602e16419dbb325b79703ee196
    26 schema:publisher N1ebac86ef9514a079ae9cf2a76df3988
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030908178
    28 https://doi.org/10.1007/978-3-642-35176-1_15
    29 schema:sdDatePublished 2019-04-15T18:11
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N9fce532900b34d6a8ce93c1493a93612
    32 schema:url http://link.springer.com/10.1007/978-3-642-35176-1_15
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N00d2d3f1297d45a0b3771b8bef36cbb1 rdf:first N0e5dc9e53acb49e7a442cc4c125e520e
    37 rdf:rest N7d7af009475942be9fe40e352bfba277
    38 N03e6151530bf4208b3fc69bdf1b05b9c rdf:first Na0d01f62fe494276994c32fba2364179
    39 rdf:rest N0fa3db0d78b6434c9a16d2f75850cab8
    40 N0866135d16a24f8aacbfd3aded6b80a1 rdf:first N94535d9b6ca64607a36d37631c9a341f
    41 rdf:rest Nbc8acf7bafe444faaa9f6019366cada1
    42 N0e5dc9e53acb49e7a442cc4c125e520e schema:familyName Hauswirth
    43 schema:givenName Manfred
    44 rdf:type schema:Person
    45 N0fa3db0d78b6434c9a16d2f75850cab8 rdf:first N9905b42a19864e25bde4f6286c99a842
    46 rdf:rest N65808854e6c64123b121ccc0eb7aae65
    47 N1ebac86ef9514a079ae9cf2a76df3988 schema:location Berlin, Heidelberg
    48 schema:name Springer Berlin Heidelberg
    49 rdf:type schema:Organisation
    50 N31eb997faf964a89b6ed308bedf97b12 rdf:first Nb9cff9ccd1ff4c3a96352c4bcdfe241f
    51 rdf:rest N00d2d3f1297d45a0b3771b8bef36cbb1
    52 N420d621e65a34db19fe5ab68a138f7b8 rdf:first sg:person.016127671631.79
    53 rdf:rest Ned54e36ab7c24f958e04d2ee5309eeea
    54 N4285728153fe44fa8ce6d2750e886c88 rdf:first Nf9820348a474492f9b392cdabeb82552
    55 rdf:rest N03e6151530bf4208b3fc69bdf1b05b9c
    56 N5e6f1d330d294b7f91095fb7d12cb827 schema:name doi
    57 schema:value 10.1007/978-3-642-35176-1_15
    58 rdf:type schema:PropertyValue
    59 N65808854e6c64123b121ccc0eb7aae65 rdf:first Nb5fdd5be91434b7dab5390db15666664
    60 rdf:rest rdf:nil
    61 N7d7af009475942be9fe40e352bfba277 rdf:first Na5068e8007b54b01a24084c56bf74aa0
    62 rdf:rest N4285728153fe44fa8ce6d2750e886c88
    63 N8c3b30f81ed74ac3bcaf632bac354b53 schema:isbn 978-3-642-35175-4
    64 978-3-642-35176-1
    65 schema:name The Semantic Web – ISWC 2012
    66 rdf:type schema:Book
    67 N9100761f69c5485d8f3282b49d22202b rdf:first Nc3350c7bcf37495a83298cfb6990a670
    68 rdf:rest N31eb997faf964a89b6ed308bedf97b12
    69 N94535d9b6ca64607a36d37631c9a341f schema:familyName Heflin
    70 schema:givenName Jeff
    71 rdf:type schema:Person
    72 N9905b42a19864e25bde4f6286c99a842 schema:familyName Bernstein
    73 schema:givenName Abraham
    74 rdf:type schema:Person
    75 N9fce532900b34d6a8ce93c1493a93612 schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 Na0d01f62fe494276994c32fba2364179 schema:familyName Schreiber
    78 schema:givenName Guus
    79 rdf:type schema:Person
    80 Na5068e8007b54b01a24084c56bf74aa0 schema:familyName Parreira
    81 schema:givenName Josiane Xavier
    82 rdf:type schema:Person
    83 Nb5fdd5be91434b7dab5390db15666664 schema:familyName Blomqvist
    84 schema:givenName Eva
    85 rdf:type schema:Person
    86 Nb6f3eed4e9954d4fb9285bf36b94f1d0 schema:name dimensions_id
    87 schema:value pub.1030908178
    88 rdf:type schema:PropertyValue
    89 Nb9cff9ccd1ff4c3a96352c4bcdfe241f schema:familyName Euzenat
    90 schema:givenName Jérôme
    91 rdf:type schema:Person
    92 Nbc8acf7bafe444faaa9f6019366cada1 rdf:first Ndee9a7864e374652a065f7421a5e4d4b
    93 rdf:rest N9100761f69c5485d8f3282b49d22202b
    94 Nc3350c7bcf37495a83298cfb6990a670 schema:familyName Tudorache
    95 schema:givenName Tania
    96 rdf:type schema:Person
    97 Ndee9a7864e374652a065f7421a5e4d4b schema:familyName Sirin
    98 schema:givenName Evren
    99 rdf:type schema:Person
    100 Ne04f4ff5fdd84533bd6cc9cdf482d74b rdf:first Ne489a185ee67498ea84213f22bf31113
    101 rdf:rest N0866135d16a24f8aacbfd3aded6b80a1
    102 Ne489a185ee67498ea84213f22bf31113 schema:familyName Cudré-Mauroux
    103 schema:givenName Philippe
    104 rdf:type schema:Person
    105 Ned54e36ab7c24f958e04d2ee5309eeea rdf:first sg:person.015234565343.35
    106 rdf:rest rdf:nil
    107 Nf4af77602e16419dbb325b79703ee196 schema:name readcube_id
    108 schema:value 933e252831a06dfb90fc62f63cd676afdac8eff23c810e1ef5a2617daca9b5ec
    109 rdf:type schema:PropertyValue
    110 Nf9820348a474492f9b392cdabeb82552 schema:familyName Hendler
    111 schema:givenName Jim
    112 rdf:type schema:Person
    113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    114 schema:name Information and Computing Sciences
    115 rdf:type schema:DefinedTerm
    116 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    117 schema:name Information Systems
    118 rdf:type schema:DefinedTerm
    119 sg:person.015234565343.35 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
    120 schema:familyName Glimm
    121 schema:givenName Birte
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015234565343.35
    123 rdf:type schema:Person
    124 sg:person.016127671631.79 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
    125 schema:familyName Kollia
    126 schema:givenName Ilianna
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016127671631.79
    128 rdf:type schema:Person
    129 sg:pub.10.1007/11762256_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043896869
    130 https://doi.org/10.1007/11762256_12
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/978-3-642-21034-1_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027871510
    133 https://doi.org/10.1007/978-3-642-21034-1_26
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/s007780050040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033408714
    136 https://doi.org/10.1007/s007780050040
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/s10817-007-9077-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1001221517
    139 https://doi.org/10.1007/s10817-007-9077-y
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s10817-008-9104-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032965985
    142 https://doi.org/10.1007/s10817-008-9104-7
    143 rdf:type schema:CreativeWork
    144 https://doi.org/10.1016/j.websem.2005.06.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045471388
    145 rdf:type schema:CreativeWork
    146 https://doi.org/10.1016/j.websem.2007.03.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013524367
    147 rdf:type schema:CreativeWork
    148 https://doi.org/10.1016/j.websem.2011.12.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000078513
    149 rdf:type schema:CreativeWork
    150 https://doi.org/10.1145/1367497.1367578 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017249930
    151 rdf:type schema:CreativeWork
    152 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
    153 schema:name University of Ulm, Germany
    154 rdf:type schema:Organization
     




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


    ...