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/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"
          }, 
          {
            "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/bf00881830", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003771115", 
              "https://doi.org/10.1007/bf00881830"
            ], 
            "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", 
          "data complexity", 
          "safe negation", 
          "conjunctive query answering", 
          "query answering", 
          "description logics", 
          "queries", 
          "OWL2 RL", 
          "knowledge bases", 
          "DL-Lite", 
          "classical semantics", 
          "complexity", 
          "Answering", 
          "semantics", 
          "logic", 
          "negation", 
          "tractability", 
          "inference", 
          "gap", 
          "basis", 
          "literature", 
          "attempt", 
          "profile", 
          "circumscription", 
          "consequences", 
          "paper"
        ], 
        "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-05-20T07:38", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_883.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.

    104 TRIPLES      22 PREDICATES      56 URIs      43 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 N97ed05ab26c54cada07d9d529f850e88
    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 N27edb2c0c25f4d29ac14c4e29ba50ee2
    16 Nd991957606d249b6b78c165bbb226804
    17 sg:journal.1043955
    18 schema:keywords Answering
    19 DL-Lite
    20 OWL2 RL
    21 attempt
    22 basis
    23 circumscription
    24 classical semantics
    25 complexity
    26 conjunctive queries
    27 conjunctive query answering
    28 consequences
    29 data complexity
    30 description logics
    31 gap
    32 inference
    33 knowledge bases
    34 literature
    35 logic
    36 negation
    37 paper
    38 profile
    39 queries
    40 query answering
    41 safe negation
    42 semantics
    43 tractability
    44 schema:name Query answering in circumscribed OWL2 profiles
    45 schema:pagination 1155-1173
    46 schema:productId N7b3cd460d546494b9ba004929087becf
    47 Nc21d845ad60a4532beebcc5348206488
    48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140776801
    49 https://doi.org/10.1007/s10472-021-09770-2
    50 schema:sdDatePublished 2022-05-20T07:38
    51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    52 schema:sdPublisher Ncb08b3ac8c4948b4b926a54036aa786f
    53 schema:url https://doi.org/10.1007/s10472-021-09770-2
    54 sgo:license sg:explorer/license/
    55 sgo:sdDataset articles
    56 rdf:type schema:ScholarlyArticle
    57 N27edb2c0c25f4d29ac14c4e29ba50ee2 schema:volumeNumber 89
    58 rdf:type schema:PublicationVolume
    59 N7b3cd460d546494b9ba004929087becf schema:name doi
    60 schema:value 10.1007/s10472-021-09770-2
    61 rdf:type schema:PropertyValue
    62 N97ed05ab26c54cada07d9d529f850e88 rdf:first sg:person.011766255474.79
    63 rdf:rest rdf:nil
    64 Nc21d845ad60a4532beebcc5348206488 schema:name dimensions_id
    65 schema:value pub.1140776801
    66 rdf:type schema:PropertyValue
    67 Ncb08b3ac8c4948b4b926a54036aa786f schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Nd991957606d249b6b78c165bbb226804 schema:issueNumber 12
    70 rdf:type schema:PublicationIssue
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Data Format
    76 rdf:type schema:DefinedTerm
    77 sg:journal.1043955 schema:issn 1012-2443
    78 1573-7470
    79 schema:name Annals of Mathematics and Artificial Intelligence
    80 schema:publisher Springer Nature
    81 rdf:type schema:Periodical
    82 sg:person.011766255474.79 schema:affiliation grid-institutes:grid.4691.a
    83 schema:familyName Bonatti
    84 schema:givenName Piero A.
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011766255474.79
    86 rdf:type schema:Person
    87 sg:pub.10.1007/978-3-319-14726-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014829987
    88 https://doi.org/10.1007/978-3-319-14726-0_8
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/978-3-319-45276-0_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007049978
    91 https://doi.org/10.1007/978-3-319-45276-0_5
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/978-3-642-23580-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004950933
    94 https://doi.org/10.1007/978-3-642-23580-1_22
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/bf00881830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003771115
    97 https://doi.org/10.1007/bf00881830
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/bf00883932 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011973855
    100 https://doi.org/10.1007/bf00883932
    101 rdf:type schema:CreativeWork
    102 grid-institutes:grid.4691.a schema:alternateName Università di Napoli Federico II, Napoli, Italy
    103 schema:name Università di Napoli Federico II, Napoli, Italy
    104 rdf:type schema:Organization
     




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


    ...