Query answering in circumscribed OWL2 profiles View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2021-08-31

AUTHORS

Piero A. Bonatti

ABSTRACT

This paper partially bridges a gap in the literature on Circumscription in Description Logics by investigating the tractability of conjunctive query answering in OWL2’s profiles. It turns out that the data complexity of conjunctive query answering is coNP-hard in circumscribed EL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {E}{\mathscr{L}}$\end{document} and DL-lite, while in circumscribed OWL2-RL conjunctive queries retain their classical semantics. In an attempt to capture nonclassical inferences in OWL2-RL, we consider conjunctive queries with safe negation. They can detect some of the nonclassical consequences of circumscribed knowledge bases, but data complexity becomes coNP-hard. In circumscribed EL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {E}{\mathscr{L}}$\end{document}, answering queries with safe negation is undecidable. More... »

PAGES

1155-1173

References to SciGraph publications

  • 2015. Decidability of Circumscribed Description Logics Revisited in ADVANCES IN KNOWLEDGE REPRESENTATION, LOGIC PROGRAMMING, AND ABSTRACT ARGUMENTATION
  • 1995-02. Priorities on defaults with prerequisites, and their application in treating specificity in terminological default logic in JOURNAL OF AUTOMATED REASONING
  • 1995-02. Embedding defaults into terminological knowledge representation formalisms in JOURNAL OF AUTOMATED REASONING
  • 2016-08-26. Revisiting Grounded Circumscription in Description Logics in WEB REASONING AND RULE SYSTEMS
  • 2011. Local Closed World Semantics: Grounded Circumscription for Description Logics in WEB REASONING AND RULE SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10472-021-09770-2

    DOI

    http://dx.doi.org/10.1007/s10472-021-09770-2

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Universit\u00e0 di Napoli Federico II, Napoli, Italy", 
              "id": "http://www.grid.ac/institutes/grid.4691.a", 
              "name": [
                "Universit\u00e0 di Napoli Federico II, Napoli, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bonatti", 
            "givenName": "Piero A.", 
            "id": "sg:person.011766255474.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011766255474.79"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-23580-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004950933", 
              "https://doi.org/10.1007/978-3-642-23580-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00881830", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003771115", 
              "https://doi.org/10.1007/bf00881830"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-45276-0_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007049978", 
              "https://doi.org/10.1007/978-3-319-45276-0_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-14726-0_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014829987", 
              "https://doi.org/10.1007/978-3-319-14726-0_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00883932", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011973855", 
              "https://doi.org/10.1007/bf00883932"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-08-31", 
        "datePublishedReg": "2021-08-31", 
        "description": "This paper partially bridges a gap in the literature on Circumscription in Description Logics by investigating the tractability of conjunctive query answering in OWL2\u2019s profiles. It turns out that the data complexity of conjunctive query answering is coNP-hard in circumscribed EL\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal {E}{\\mathscr{L}}$\\end{document} and DL-lite, while in circumscribed OWL2-RL conjunctive queries retain their classical semantics. In an attempt to capture nonclassical inferences in OWL2-RL, we consider conjunctive queries with safe negation. They can detect some of the nonclassical consequences of circumscribed knowledge bases, but data complexity becomes coNP-hard. In circumscribed EL\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal {E}{\\mathscr{L}}$\\end{document}, answering queries with safe negation is undecidable.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10472-021-09770-2", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1043955", 
            "issn": [
              "1012-2443", 
              "1573-7470"
            ], 
            "name": "Annals of Mathematics and Artificial Intelligence", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "12", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "89"
          }
        ], 
        "keywords": [
          "conjunctive queries", 
          "safe negation", 
          "data complexity", 
          "Conjunctive Query Answering", 
          "query answering", 
          "knowledge bases", 
          "description logics", 
          "queries", 
          "DL-Lite", 
          "classical semantics", 
          "complexity", 
          "answering", 
          "semantics", 
          "logic", 
          "negation", 
          "tractability", 
          "inference", 
          "gap", 
          "basis", 
          "literature", 
          "attempt", 
          "profile", 
          "circumscription", 
          "consequences", 
          "paper", 
          "OWL2\u2019s profiles", 
          "OWL2-RL conjunctive queries", 
          "nonclassical inferences", 
          "OWL2-RL", 
          "nonclassical consequences"
        ], 
        "name": "Query answering in circumscribed OWL2 profiles", 
        "pagination": "1155-1173", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1140776801"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10472-021-09770-2"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10472-021-09770-2", 
          "https://app.dimensions.ai/details/publication/pub.1140776801"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:58", 
        "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/article/article_875.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10472-021-09770-2"
      }
    ]
     

    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/s10472-021-09770-2'

    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/s10472-021-09770-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09770-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09770-2'


     

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

    108 TRIPLES      22 PREDICATES      60 URIs      47 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10472-021-09770-2 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N4c6b931dba774b1081d42fdee0128422
    4 schema:citation sg:pub.10.1007/978-3-319-14726-0_8
    5 sg:pub.10.1007/978-3-319-45276-0_5
    6 sg:pub.10.1007/978-3-642-23580-1_22
    7 sg:pub.10.1007/bf00881830
    8 sg:pub.10.1007/bf00883932
    9 schema:datePublished 2021-08-31
    10 schema:datePublishedReg 2021-08-31
    11 schema:description This paper partially bridges a gap in the literature on Circumscription in Description Logics by investigating the tractability of conjunctive query answering in OWL2’s profiles. It turns out that the data complexity of conjunctive query answering is coNP-hard in circumscribed EL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {E}{\mathscr{L}}$\end{document} and DL-lite, while in circumscribed OWL2-RL conjunctive queries retain their classical semantics. In an attempt to capture nonclassical inferences in OWL2-RL, we consider conjunctive queries with safe negation. They can detect some of the nonclassical consequences of circumscribed knowledge bases, but data complexity becomes coNP-hard. In circumscribed EL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {E}{\mathscr{L}}$\end{document}, answering queries with safe negation is undecidable.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf N2d184d6d7ce04a5baf62d75707151885
    16 Nce4b5c3b3112485c8de33be2c2cbde3b
    17 sg:journal.1043955
    18 schema:keywords Conjunctive Query Answering
    19 DL-Lite
    20 OWL2-RL
    21 OWL2-RL conjunctive queries
    22 OWL2’s profiles
    23 answering
    24 attempt
    25 basis
    26 circumscription
    27 classical semantics
    28 complexity
    29 conjunctive queries
    30 consequences
    31 data complexity
    32 description logics
    33 gap
    34 inference
    35 knowledge bases
    36 literature
    37 logic
    38 negation
    39 nonclassical consequences
    40 nonclassical inferences
    41 paper
    42 profile
    43 queries
    44 query answering
    45 safe negation
    46 semantics
    47 tractability
    48 schema:name Query answering in circumscribed OWL2 profiles
    49 schema:pagination 1155-1173
    50 schema:productId N6e686100e24f4f918f9f5459dedb470c
    51 Nf1711447106e40f0bfed738744436208
    52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140776801
    53 https://doi.org/10.1007/s10472-021-09770-2
    54 schema:sdDatePublished 2022-01-01T18:58
    55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    56 schema:sdPublisher N311067f007944b53a9bf02104f95539b
    57 schema:url https://doi.org/10.1007/s10472-021-09770-2
    58 sgo:license sg:explorer/license/
    59 sgo:sdDataset articles
    60 rdf:type schema:ScholarlyArticle
    61 N2d184d6d7ce04a5baf62d75707151885 schema:issueNumber 12
    62 rdf:type schema:PublicationIssue
    63 N311067f007944b53a9bf02104f95539b schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 N4c6b931dba774b1081d42fdee0128422 rdf:first sg:person.011766255474.79
    66 rdf:rest rdf:nil
    67 N6e686100e24f4f918f9f5459dedb470c schema:name doi
    68 schema:value 10.1007/s10472-021-09770-2
    69 rdf:type schema:PropertyValue
    70 Nce4b5c3b3112485c8de33be2c2cbde3b schema:volumeNumber 89
    71 rdf:type schema:PublicationVolume
    72 Nf1711447106e40f0bfed738744436208 schema:name dimensions_id
    73 schema:value pub.1140776801
    74 rdf:type schema:PropertyValue
    75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Information and Computing Sciences
    77 rdf:type schema:DefinedTerm
    78 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Data Format
    80 rdf:type schema:DefinedTerm
    81 sg:journal.1043955 schema:issn 1012-2443
    82 1573-7470
    83 schema:name Annals of Mathematics and Artificial Intelligence
    84 schema:publisher Springer Nature
    85 rdf:type schema:Periodical
    86 sg:person.011766255474.79 schema:affiliation grid-institutes:grid.4691.a
    87 schema:familyName Bonatti
    88 schema:givenName Piero A.
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011766255474.79
    90 rdf:type schema:Person
    91 sg:pub.10.1007/978-3-319-14726-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014829987
    92 https://doi.org/10.1007/978-3-319-14726-0_8
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-319-45276-0_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007049978
    95 https://doi.org/10.1007/978-3-319-45276-0_5
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-642-23580-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004950933
    98 https://doi.org/10.1007/978-3-642-23580-1_22
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf00881830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003771115
    101 https://doi.org/10.1007/bf00881830
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/bf00883932 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011973855
    104 https://doi.org/10.1007/bf00883932
    105 rdf:type schema:CreativeWork
    106 grid-institutes:grid.4691.a schema:alternateName Università di Napoli Federico II, Napoli, Italy
    107 schema:name Università di Napoli Federico II, Napoli, Italy
    108 rdf:type schema:Organization
     




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


    ...