On Decidability and Complexity of Description Logics with Uniqueness Constraints View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-10-12

AUTHORS

Vitaliy L. Khizder , David Toman , Grant Weddell

ABSTRACT

We establish the equivalence of: (1) the logical implication problem for a description logic dialect called DLClass that includes a concept constructor for expressing uniqueness constraints, (2) the logical implication problem for path functional dependencies (PFDs), and (3) the problem of answering queries in deductive databases with limited use of successor functions. As a consequence, we settle an open problem concerning lower bounds for the PFD logical implication problem and show that a regularity condition for DLClass that ensures low order polynomial time decidability for its logical implication problem is tight. More... »

PAGES

54-67

Book

TITLE

Database Theory — ICDT 2001

ISBN

978-3-540-41456-8
978-3-540-44503-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44503-x_4

DOI

http://dx.doi.org/10.1007/3-540-44503-x_4

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Khizder", 
        "givenName": "Vitaliy L.", 
        "id": "sg:person.013343722041.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013343722041.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Toman", 
        "givenName": "David", 
        "id": "sg:person.011644611743.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weddell", 
        "givenName": "Grant", 
        "id": "sg:person.01111756132.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-10-12", 
    "datePublishedReg": "2001-10-12", 
    "description": "We establish the equivalence of: (1) the logical implication problem for a description logic dialect called DLClass that includes a concept constructor for expressing uniqueness constraints, (2) the logical implication problem for path functional dependencies (PFDs), and (3) the problem of answering queries in deductive databases with limited use of successor functions. As a consequence, we settle an open problem concerning lower bounds for the PFD logical implication problem and show that a regularity condition for DLClass that ensures low order polynomial time decidability for its logical implication problem is tight.", 
    "editor": [
      {
        "familyName": "Van den Bussche", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Vianu", 
        "givenName": "Victor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44503-x_4", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41456-8", 
        "978-3-540-44503-6"
      ], 
      "name": "Database Theory \u2014 ICDT 2001", 
      "type": "Book"
    }, 
    "keywords": [
      "logical implication problem", 
      "path functional dependencies", 
      "implication problem", 
      "uniqueness constraints", 
      "description logic dialect", 
      "deductive databases", 
      "description logics", 
      "concept constructors", 
      "functional dependencies", 
      "open problem", 
      "lower bounds", 
      "queries", 
      "constraints", 
      "decidability", 
      "complexity", 
      "logic", 
      "constructors", 
      "database", 
      "successor function", 
      "bounds", 
      "dependency", 
      "limited use", 
      "dialects", 
      "equivalence", 
      "use", 
      "function", 
      "regularity conditions", 
      "conditions", 
      "consequences", 
      "problem", 
      "logic dialect", 
      "DLClass", 
      "PFD logical implication problem", 
      "low order polynomial time decidability", 
      "order polynomial time decidability", 
      "polynomial time decidability", 
      "time decidability"
    ], 
    "name": "On Decidability and Complexity of Description Logics with Uniqueness Constraints", 
    "pagination": "54-67", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045586843"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44503-x_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44503-x_4", 
      "https://app.dimensions.ai/details/publication/pub.1045586843"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_163.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44503-x_4"
  }
]
 

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/3-540-44503-x_4'

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/3-540-44503-x_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44503-x_4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44503-x_4'


 

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

116 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44503-x_4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N33da2a8f4cba48ffbe19cd6d4c8d9952
4 schema:datePublished 2001-10-12
5 schema:datePublishedReg 2001-10-12
6 schema:description We establish the equivalence of: (1) the logical implication problem for a description logic dialect called DLClass that includes a concept constructor for expressing uniqueness constraints, (2) the logical implication problem for path functional dependencies (PFDs), and (3) the problem of answering queries in deductive databases with limited use of successor functions. As a consequence, we settle an open problem concerning lower bounds for the PFD logical implication problem and show that a regularity condition for DLClass that ensures low order polynomial time decidability for its logical implication problem is tight.
7 schema:editor N7bc7bf379a4e4a74b93697d96c55928f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8659e2116fe44f12a239391691799f53
12 schema:keywords DLClass
13 PFD logical implication problem
14 bounds
15 complexity
16 concept constructors
17 conditions
18 consequences
19 constraints
20 constructors
21 database
22 decidability
23 deductive databases
24 dependency
25 description logic dialect
26 description logics
27 dialects
28 equivalence
29 function
30 functional dependencies
31 implication problem
32 limited use
33 logic
34 logic dialect
35 logical implication problem
36 low order polynomial time decidability
37 lower bounds
38 open problem
39 order polynomial time decidability
40 path functional dependencies
41 polynomial time decidability
42 problem
43 queries
44 regularity conditions
45 successor function
46 time decidability
47 uniqueness constraints
48 use
49 schema:name On Decidability and Complexity of Description Logics with Uniqueness Constraints
50 schema:pagination 54-67
51 schema:productId N65aaa2baebef43e88d19218fbbed5944
52 Nf32c9b1394444cc49741ebf67beada24
53 schema:publisher N9817409e2ab64b07ba23879dd00e10e8
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045586843
55 https://doi.org/10.1007/3-540-44503-x_4
56 schema:sdDatePublished 2021-12-01T19:58
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N601301ea4dba426d9578d0b979beaea7
59 schema:url https://doi.org/10.1007/3-540-44503-x_4
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N33da2a8f4cba48ffbe19cd6d4c8d9952 rdf:first sg:person.013343722041.76
64 rdf:rest N51a7c59d140b45a8920b8dcbbb48ec88
65 N51a7c59d140b45a8920b8dcbbb48ec88 rdf:first sg:person.011644611743.11
66 rdf:rest N8b030ac950264970a9aaf3a049e9defb
67 N601301ea4dba426d9578d0b979beaea7 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N65aaa2baebef43e88d19218fbbed5944 schema:name doi
70 schema:value 10.1007/3-540-44503-x_4
71 rdf:type schema:PropertyValue
72 N7bc7bf379a4e4a74b93697d96c55928f rdf:first Nf50a34127eee4c69ae632605572aa6a5
73 rdf:rest Nb5d0fac5fc0c4b15accb128f2880800d
74 N8659e2116fe44f12a239391691799f53 schema:isbn 978-3-540-41456-8
75 978-3-540-44503-6
76 schema:name Database Theory — ICDT 2001
77 rdf:type schema:Book
78 N8b030ac950264970a9aaf3a049e9defb rdf:first sg:person.01111756132.29
79 rdf:rest rdf:nil
80 N9817409e2ab64b07ba23879dd00e10e8 schema:name Springer Nature
81 rdf:type schema:Organisation
82 Nb5d0fac5fc0c4b15accb128f2880800d rdf:first Nbab228a9cf834108a704779cec03030b
83 rdf:rest rdf:nil
84 Nbab228a9cf834108a704779cec03030b schema:familyName Vianu
85 schema:givenName Victor
86 rdf:type schema:Person
87 Nf32c9b1394444cc49741ebf67beada24 schema:name dimensions_id
88 schema:value pub.1045586843
89 rdf:type schema:PropertyValue
90 Nf50a34127eee4c69ae632605572aa6a5 schema:familyName Van den Bussche
91 schema:givenName Jan
92 rdf:type schema:Person
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
97 schema:name Computation Theory and Mathematics
98 rdf:type schema:DefinedTerm
99 sg:person.01111756132.29 schema:affiliation grid-institutes:grid.46078.3d
100 schema:familyName Weddell
101 schema:givenName Grant
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29
103 rdf:type schema:Person
104 sg:person.011644611743.11 schema:affiliation grid-institutes:grid.46078.3d
105 schema:familyName Toman
106 schema:givenName David
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11
108 rdf:type schema:Person
109 sg:person.013343722041.76 schema:affiliation grid-institutes:grid.46078.3d
110 schema:familyName Khizder
111 schema:givenName Vitaliy L.
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013343722041.76
113 rdf:type schema:Person
114 grid-institutes:grid.46078.3d schema:alternateName Department of Computer Science, University of Waterloo, Canada
115 schema:name Department of Computer Science, University of Waterloo, Canada
116 rdf:type schema:Organization
 




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


...