On Enumerating Query Plans Using Analytic Tableau View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015

AUTHORS

Alexander Hudek , David Toman , Grant Weddell

ABSTRACT

We consider how the method of analytic tableau coupled with interpolant extraction can be adapted to enumerate possible query plans for a given user query in the context of a first order theory that defines a relational database schema. In standard analytic tableau calculi, the sub-formula property of proofs limits the variety of interpolants and consequently of plans that can be generated for the given query. To overcome this limitation, we present a two-phase adaptation of a tableau calculus that ensures all plans logically equivalent to the query with respect to the schema, that correctly implement the user query, are indeed found. We also show how this separation allows us to avoid backtracking when reasoning about consequences of the schema. More... »

PAGES

339-354

References to SciGraph publications

Book

TITLE

Automated Reasoning with Analytic Tableaux and Related Methods

ISBN

978-3-319-24311-5
978-3-319-24312-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-24312-2_23

DOI

http://dx.doi.org/10.1007/978-3-319-24312-2_23

DIMENSIONS

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


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 Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Cheriton School of Computer Science, University of Waterloo"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hudek", 
        "givenName": "Alexander", 
        "id": "sg:person.0702641766.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0702641766.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Cheriton School of Computer Science, University of Waterloo"
          ], 
          "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": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Cheriton School of Computer Science, University of Waterloo"
          ], 
          "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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/543613.543644", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001189931"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1265530.1265534", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007319289"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s1385-7258(53)50042-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009222222"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/362384.362685", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014251677"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/275487.275492", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014593173"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/320083.320091", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017321132"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/234313.234367", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018960477"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-2360-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019518848", 
          "https://doi.org/10.1007/978-1-4612-2360-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-2360-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019518848", 
          "https://doi.org/10.1007/978-1-4612-2360-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-73005-4_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023673389", 
          "https://doi.org/10.1007/978-3-642-73005-4_24"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2594538.2594550", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024867807"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01201353", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026582422", 
          "https://doi.org/10.1007/bf01201353"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/582095.582099", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037544469"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2963594", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037672500"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/320107.320115", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053687153"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2200/s00363ed1v01y201105dtm018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069288245"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "We consider how the method of analytic tableau coupled with interpolant extraction can be adapted to enumerate possible query plans for a given user query in the context of a first order theory that defines a relational database schema. In standard analytic tableau calculi, the sub-formula property of proofs limits the variety of interpolants and consequently of plans that can be generated for the given query. To overcome this limitation, we present a two-phase adaptation of a tableau calculus that ensures all plans logically equivalent to the query with respect to the schema, that correctly implement the user query, are indeed found. We also show how this separation allows us to avoid backtracking when reasoning about consequences of the schema.", 
    "editor": [
      {
        "familyName": "De Nivelle", 
        "givenName": "Hans", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-24312-2_23", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-24311-5", 
        "978-3-319-24312-2"
      ], 
      "name": "Automated Reasoning with Analytic Tableaux and Related Methods", 
      "type": "Book"
    }, 
    "name": "On Enumerating Query Plans Using Analytic Tableau", 
    "pagination": "339-354", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-24312-2_23"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ef4222a72f069c8cb0edcec2be82ab9e6762c6f16f3695dcf39f4b548f3105ca"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050225268"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-24312-2_23", 
      "https://app.dimensions.ai/details/publication/pub.1050225268"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T16:20", 
    "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_8675_00000274.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-24312-2_23"
  }
]
 

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-319-24312-2_23'

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-319-24312-2_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-24312-2_23'

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-319-24312-2_23'


 

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

127 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-24312-2_23 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N67ea746200474964b2e273994e302970
4 schema:citation sg:pub.10.1007/978-1-4612-2360-3
5 sg:pub.10.1007/978-3-642-73005-4_24
6 sg:pub.10.1007/bf01201353
7 https://doi.org/10.1016/s1385-7258(53)50042-3
8 https://doi.org/10.1145/1265530.1265534
9 https://doi.org/10.1145/234313.234367
10 https://doi.org/10.1145/2594538.2594550
11 https://doi.org/10.1145/275487.275492
12 https://doi.org/10.1145/320083.320091
13 https://doi.org/10.1145/320107.320115
14 https://doi.org/10.1145/362384.362685
15 https://doi.org/10.1145/543613.543644
16 https://doi.org/10.1145/582095.582099
17 https://doi.org/10.2200/s00363ed1v01y201105dtm018
18 https://doi.org/10.2307/2963594
19 schema:datePublished 2015
20 schema:datePublishedReg 2015-01-01
21 schema:description We consider how the method of analytic tableau coupled with interpolant extraction can be adapted to enumerate possible query plans for a given user query in the context of a first order theory that defines a relational database schema. In standard analytic tableau calculi, the sub-formula property of proofs limits the variety of interpolants and consequently of plans that can be generated for the given query. To overcome this limitation, we present a two-phase adaptation of a tableau calculus that ensures all plans logically equivalent to the query with respect to the schema, that correctly implement the user query, are indeed found. We also show how this separation allows us to avoid backtracking when reasoning about consequences of the schema.
22 schema:editor N6f03dcd5be2e4d808c4548cad26b9e83
23 schema:genre chapter
24 schema:inLanguage en
25 schema:isAccessibleForFree false
26 schema:isPartOf N85a5cf34f79b42d59b07709c96ee60e4
27 schema:name On Enumerating Query Plans Using Analytic Tableau
28 schema:pagination 339-354
29 schema:productId N6d051693ddd949b8b22f325b4399c2f7
30 Nc1a6be1cdb4e4e568192e918522c9324
31 Nc2b0d16e48964a3e90b06a6c971e166f
32 schema:publisher Ncc1f224782c5462b9e2c0484de74c9c2
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050225268
34 https://doi.org/10.1007/978-3-319-24312-2_23
35 schema:sdDatePublished 2019-04-15T16:20
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher Ndab8073927da410682dbdb17a6599b56
38 schema:url http://link.springer.com/10.1007/978-3-319-24312-2_23
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N1332d44609f94348855f0944a20da007 schema:familyName De Nivelle
43 schema:givenName Hans
44 rdf:type schema:Person
45 N67ea746200474964b2e273994e302970 rdf:first sg:person.0702641766.21
46 rdf:rest Nf8a63da094644723ac322fed75cbbc0a
47 N6d051693ddd949b8b22f325b4399c2f7 schema:name readcube_id
48 schema:value ef4222a72f069c8cb0edcec2be82ab9e6762c6f16f3695dcf39f4b548f3105ca
49 rdf:type schema:PropertyValue
50 N6f03dcd5be2e4d808c4548cad26b9e83 rdf:first N1332d44609f94348855f0944a20da007
51 rdf:rest rdf:nil
52 N7a0a131304f94836b1401c1c2e88a679 rdf:first sg:person.01111756132.29
53 rdf:rest rdf:nil
54 N85a5cf34f79b42d59b07709c96ee60e4 schema:isbn 978-3-319-24311-5
55 978-3-319-24312-2
56 schema:name Automated Reasoning with Analytic Tableaux and Related Methods
57 rdf:type schema:Book
58 Nc1a6be1cdb4e4e568192e918522c9324 schema:name dimensions_id
59 schema:value pub.1050225268
60 rdf:type schema:PropertyValue
61 Nc2b0d16e48964a3e90b06a6c971e166f schema:name doi
62 schema:value 10.1007/978-3-319-24312-2_23
63 rdf:type schema:PropertyValue
64 Ncc1f224782c5462b9e2c0484de74c9c2 schema:location Cham
65 schema:name Springer International Publishing
66 rdf:type schema:Organisation
67 Ndab8073927da410682dbdb17a6599b56 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 Nf8a63da094644723ac322fed75cbbc0a rdf:first sg:person.011644611743.11
70 rdf:rest N7a0a131304f94836b1401c1c2e88a679
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information Systems
76 rdf:type schema:DefinedTerm
77 sg:person.01111756132.29 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
78 schema:familyName Weddell
79 schema:givenName Grant
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29
81 rdf:type schema:Person
82 sg:person.011644611743.11 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
83 schema:familyName Toman
84 schema:givenName David
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11
86 rdf:type schema:Person
87 sg:person.0702641766.21 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
88 schema:familyName Hudek
89 schema:givenName Alexander
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0702641766.21
91 rdf:type schema:Person
92 sg:pub.10.1007/978-1-4612-2360-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019518848
93 https://doi.org/10.1007/978-1-4612-2360-3
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/978-3-642-73005-4_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023673389
96 https://doi.org/10.1007/978-3-642-73005-4_24
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/bf01201353 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026582422
99 https://doi.org/10.1007/bf01201353
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/s1385-7258(53)50042-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009222222
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1145/1265530.1265534 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007319289
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1145/234313.234367 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018960477
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1145/2594538.2594550 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024867807
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1145/275487.275492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014593173
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1145/320083.320091 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017321132
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/320107.320115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053687153
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/362384.362685 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014251677
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/543613.543644 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001189931
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/582095.582099 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037544469
120 rdf:type schema:CreativeWork
121 https://doi.org/10.2200/s00363ed1v01y201105dtm018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069288245
122 rdf:type schema:CreativeWork
123 https://doi.org/10.2307/2963594 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037672500
124 rdf:type schema:CreativeWork
125 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
126 schema:name Cheriton School of Computer Science, University of Waterloo
127 rdf:type schema:Organization
 




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


...